Hi Codeforces!

I wrote hand-rolled Red-Black and AVL trees in C++ and benchmarked them against std::set, std::map and std::unordered_set with 10M inserts, 10M searches and 10M removes per structure (plus a 1M random preload). My first write-up concluded that "my RBTree beats std::set by ~2.5x".

Then I noticed my Makefile had CXXFLAGS = -Wall -std=c++17 — no -O2. Codeforces compiles with -O2, so those numbers said almost nothing about contest performance. Here's the corrected comparison, plus a small anti-hash experiment, since that's where unordered_map really bites in contests.

Setup

• 1,000,000 random int keys preloaded from a file, then

$ inserts,

$ finds and

$ erases with sorted keys (k * 13). - Single-threaded, std::chrono wall time, GCC 13, -std=c++17. - Code: github.com/marouaneMJH/cpp-software-design

Results (ms, int keys)

(An unbalanced BST degenerates into a linked list on sorted input and didn't finish in reasonable time. No surprises there.)

What changed with -O2

1. The STL gains the most. std::set::erase went from 6334 ms to 1419 ms (4.5x). At -O0, every tiny inline helper (iterators, comparators, allocator traits) is a real function call. Hand-written code with fewer abstraction layers suffers less from that, which made my tree look better than it is.
2. "RBTree beats std::set" shrinks to a near tie on insert/remove. Search is still faster in my tree, but my RBTree doesn't track size, doesn't support iterators, doesn't use an allocator, etc. It isn't a fair fight and I wouldn't use it in a contest.
3. AVL gives the fastest tree lookups (868 ms), as you'd expect from its stricter height bound, but pays for it with rotations on insert/remove.
4. unordered_set is ~14x faster than std::set on search, as long as nobody attacks your hash...

...which on Codeforces, they will

libstdc++ hashes integers with the identity function, and the bucket index is key % bucket_count. If all keys are multiples of a bucket-count prime, they land in one bucket and every operation becomes

$.

I inserted and then looked up

$ keys of the form i * P (GCC 13, -O2):

Same container, same

$, but 5 ms vs 40 seconds. That's how solutions get hacked or fail system tests.

The fix is the well-known randomized splitmix64 hash (credit to neal's classic blog):

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<long long, int, custom_hash> cnt;

It's about 6x slower than the identity hash on friendly input, but its cost is flat and it can't be targeted.

My takeaways for contests

• Always benchmark with the judge's flags. -O0 numbers can reverse your conclusions.
• Frequency counts / membership: unordered_map + custom_hash, and reserve() if you know

$. - Need order, lower_bound, or a guaranteed worst case: std::map / std::set. At -O2 they're decent. - **Keys in a small dense range (

$):** a plain array beats everything above. - Don't hand-roll a balanced tree for speed. Write one to learn how it works (I'm glad I did), not to win milliseconds.

I wrote longer versions of both topics on my blog if you want the details:

• Benchmarking C++ Trees and Hash Tables at 60 Million Ops
• Hash Maps in C++ for Competitive Programming: unordered_map Explained

Feedback is welcome, especially if you spot another methodology mistake. I'd rather learn it here than in a contest :)