No, they have an *average* complexity of O(1) i.e. assuming random input. Their worst case complexity is O(N) for some important operations.

Oh?

To expand on @sebastian’s answer, I *think* the following creates a valid testcase:

```
#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
#include <cassert>
using namespace std;
const int N = 2e5;
int main() {
// On my system, an unordered_map will eventually grow to have p buckets.
const auto p = 26267;
const auto maxCoordVal = 1'000'000'000;
const auto maxCoordMultiplier = maxCoordVal / p;
struct Vertex
{
int x = -1;
int y = -1;
bool operator<(const Vertex& other) const
{
if (x != other.x)
return x < other.x;
return y < other.y;
}
};
struct Rectangle
{
Vertex vertices[4];
};
vector<Rectangle> rectangles;
set<Vertex> vertices;
// Should generate valid rectangles with distinct vertices, where each vertex coord in a multiple of
// p, and does not exceed maxCoordVal.
// Since all coordinates are multiples of p, when the unordered_map grows to have p buckets,
// the coordinates will all end up in the same bucket.
for (int i = 0 ; i < maxCoordMultiplier / 2; i += 2)
{
for (int j = 0; j < maxCoordMultiplier / 2; j += 2)
{
// Should be a non-degenerate rectangle.
const Vertex topLeft = {(i * 2) * p, (j * 2) * p};
const Vertex topRight = {(i * 2 + 1) * p, (j * 2) * p};
const Vertex bottomLeft = {(i * 2) * p, (j * 2 + 1) * p};
const Vertex bottomRight = {(i * 2 + 1) * p, (j * 2 + 1) * p};
Rectangle rectangle { topLeft, topRight, bottomLeft, bottomRight };
rectangles.push_back(rectangle);
}
if (rectangles.size() > 2e5)
break;
}
while (rectangles.size() > 2e5)
rectangles.pop_back();
const int numRectangles = rectangles.size();
// Verify coords are unique.
for (const auto& rectangle : rectangles)
{
for (const auto& vertex : rectangle.vertices)
{
assert(vertices.find(vertex) == vertices.end());
vertices.insert(vertex);
}
}
// Mark one random vertex as not-to-be-printed.
auto& vertexToOmit = rectangles[rand() % rectangles.size()].vertices[rand() % 4];
cerr << "Will omit the vertex: " << vertexToOmit.x << " " << vertexToOmit.y << endl;
vertexToOmit.x = -1;
vertexToOmit.y = -1;
cout << 1 << endl;
cout << numRectangles << endl;
for (const auto& rectangle : rectangles)
{
for (const auto& vertex : rectangle.vertices)
{
if (vertex.x == -1 && vertex.y == -1)
continue;
cout << vertex.x << " " << vertex.y << endl;
}
}
}
```

(The setter’s solution handles the generated testcase in about .25 secs on my machine; yours … doesn’t ;))