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 iterating over the map, the values will be returned in the same order as they were inserted.
The values are stored contiguously in an underlying structure, no holes in-between values even after an erase operation. By default a std::deque is used for this structure, but it's also possible to use a std::vector. This structure is directly accessible through the values_container() method and if the structure is a std::vector, a data() method is also provided to easily interact with C APIs.
To resolve collisions on hashes, the library uses robin hood probing with backward shift deletion.
The library provides a behaviour similar to a std::deque/std::vector with unique values but with an average search complexity of O(1). This comes at the price of a little higher memory footprint (8 bytes per entry if the load factor is 1, around 16 bytes per entry for a 0.5 load factor).
Two classes are provided: tsl::ordered_map and tsl::ordered_set.
ordered-map alternatives and similar libraries
Based on the "Data Structures" category
Do you think we are missing an alternative of ordered-map or a related project?