Popularity
2.4
Growing
Activity
7.4
Growing
78
8
6

Description

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    

Recently added ordered-map resources

Do you know of a usefull tutorial, book or news relevant to ordered-map?
Be the first to add one!

ordered-map Recommendations

There are no recommendations yet. Be the first to promote ordered-map!

Have you used ordered-map? Share your experience. Write a short recommendation and ordered-map, you and your project will be promoted on Awesome C++.
Recommend ordered-map

Add another 'Data Structures' Library