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.

Code Quality Rank: L4
Programming language: C++
Tags: Containers     Data Structures     Ordered Map     Map     Set     Utilities    

ordered-map alternatives and similar libraries

Based on the "Data Structures" category

  • libsrt

    libsrt is a C library for writing fast and safe C code, faster. It provides string, vector, bit set, set, map, hash set, and hash map handling. Suitable for soft and hard real-time. Allows both heap and stack allocation.
  • MDAL

    Mesh Data Abstraction Library
  • Ygg

    An intrusive C++11 implementation of a Red-Black-Tree, an Interval Tree and an Interval Map.

Do you think we are missing an alternative of ordered-map or a related project?

Add another 'Data Structures' Library