ordered-map keeps insertion order and gives up fast erase

Insertion order as a property of the map, not a wrapper

The ordered-map library provides a hash map and a hash set which preserve the order of insertion, in a way similar to Python's `OrderedDict`. When you iterate over the map, the values come back in the same order they were inserted. The important part is that this is not an index bolted onto the side of an unordered container. The values are stored contiguously in an underlying structure, with no holes in between even after an erase operation, and that structure is directly reachable through the `values_container()` method. So if you need the ordered view, you get it without maintaining a second container, and if you need raw access to the values, the `values_container()` call hands you the thing itself. The default underlying structure is a `std::deque`, and a `std::vector` is also possible, in which case a `data()` method is provided so the buffer can be handed to C APIs directly. The two classes provided are `tsl::ordered_map` and `tsl::ordered_set`.

Where the O(1) comes from and where it stops

The performance characteristics follow from the structure. The library provides a behaviour similar to a `std::deque` or `std::vector` with unique values, but with an average time complexity of O(1) for lookups and an amortised time complexity of O(1) for insertions. The cost is a little higher memory footprint, 8 bytes per bucket by default. Collisions are resolved with linear robin hood probing with backward shift deletion, which is what keeps the load factor distribution tight without tombstones. The one operation that breaks the pattern is erase. The documentation is direct that fast iteration comes with the drawback of an O(bucket_count) erase operation, and it recommends another data structure if ordered erase is often used. Two cheaper alternatives exist. `pop_back()` is O(1), and `unordered_erase()` is O(1) too, but it breaks the insertion order. That is the shape of the trade: a map where removing an element in the middle costs a scan of the bucket array, in exchange for the fact that everything else is a hash operation.

The API is unordered_map with a handful of sharp edges

The library tries to have an interface similar to `std::unordered_map`, and the README lists the differences precisely enough to plan around. The iterators are `RandomAccessIterator`, and iterator invalidation behaves more like `std::vector` and `std::deque` than like the unordered containers, which means an insert can invalidate iterators unless you `reserve()` when using `std::vector` as the value container. The equality operators are order dependent, so two maps with the same values inserted in a different order do not compare equal, and that is a genuine surprise for code that uses maps as set-like values. The iterator dereference returns a reference to `const std::pair<Key, T>` rather than `std::pair<const Key, T>`, so the mapped value is not modifiable through the iterator and you have to call `value()` to get a mutable reference.

tsl::ordered_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};
for(auto it = map.begin(); it != map.end(); ++it) {
    //it->second = 2; // Illegal
    it.value() = 2; // Ok
}

Two more limits: some bucket related methods such as `bucket_size` and `bucket` are not supported, and by default the map holds at most 2^32 - 1 values, which can be raised through the `IndexType` class template parameter.

Installing it means adding an include directory

There is nothing to compile. To use ordered-map, you add the `include` directory to your include path, and it is a header-only library. If you use CMake, the README says you can also use the `tsl::ordered_map` exported target from the `CMakeLists.txt`, and the build section is cut off mid-sentence at the point where the `target_link_libraries` call would have been shown, so the exact incantation is worth checking in the file rather than guessing. The repository layout is small and conventional for a header-only project: an `include/` directory holding the headers, a `src/` directory, a `tests/` directory, a `cmake/` directory, and the `CMakeLists.txt`. There is a `doxygen.conf` for the API documentation, a `tsl-ordered-map.natvis` file for the Visual Studio debugger, and a `.codecov.yml` alongside a CI workflow. The licence is MIT.

Features that only matter in specific codebases

Several of the key features are worth knowing about because they apply to a narrower set of code than the headline suggests. Heterogeneous lookups let you call `find` with a type different from `Key`, so a map keyed by `std::unique_ptr<foo>` can be searched with a `foo*` or a `std::uintptr_t` without constructing a `unique_ptr` first, which avoids an allocation on every probe. If you already know the hash before the lookup, you can pass it as a parameter to speed the lookup up, via the `precalculated_hash` parameter. Serialization and deserialisation are supported through the `serialize` and `deserialize` methods, and the README links to an example of it. The library can be used with exceptions disabled, through `-fno-exceptions` on Clang and GCC, without an `/EH` option on MSVC, or simply by defining `TSL_NO_EXCEPTIONS`, in which case `std::terminate` replaces the `throw` instruction. Support for C++ modules requires C++20 or later. The thread-safety guarantee is the same as `std::unordered_map`, meaning multiple concurrent readers are fine with no writer.

The exception guarantee has a precondition you can trip over

The library documents its exception guarantees the way a careful library does, and the conditions are worth reading before you rely on them. Unless stated otherwise, functions have the strong exception guarantee, and the guarantee holds only if `ValueContainer::emplace_back` has the strong exception guarantee itself. That is true for `std::vector` and `std::deque` as long as the type is not a move-only type with a move constructor that may throw, which is a narrower condition than it first appears and a realistic one for types that own resources. The `erase_if` functions on both the map and the set only have the guarantee under the preconditions listed in their own documentation. The second practical detail is the bucket array. The library uses a power of two for the size of its buckets array to take advantage of fast modulo, and for good performance it requires the hash table to have a well-distributed hash function. The README tells you what to do when performance disappoints: check your hash function. That is a real trap for people who use a pointer or an id with poor mixing, because a poor hash does not produce wrong results, it produces a map that has quietly become linear.

Editorial conclusion

Adopt ordered-map when you need hash lookup speed and stable insertion order at the same time, and your workload erases rarely. Skip it if removal is common and order matters, because the ordered erase is O(bucket_count) and the documentation says another data structure is recommended in that case, and skip it if a plain `std::unordered_map` with your own ordering vector would do. Before you commit, check that your hash function distributes well, since the bucket array is a power of two and the documentation asks you to look there first if performance disappoints.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. README
4. Releases
5. Tessil/ordered-map on GitHub