Tessil / ordered-map

C++ hash map and hash set which preserve the order of insertion
MIT License
517 stars 67 forks source link

Add support for large maps/sets (more than 2^32 - 1 elements) through an extra class template parameter (#16) #18

Closed Tessil closed 6 years ago

Tessil commented 6 years ago

Add support for large maps/sets (more than 2^32 - 1 elements) through the IndexType class template parameter. The parameter allows us to configure the index type that is used in bucket_entry.

By default a bucket_entry has a 32 bits integer index to map an element with its position in m_values and a 32 bits hash. Each bucket_entry entry takes thus 8 bytes and the map can only contains 2^32 - 1 elements (-1 due to a reserved value).

Setting the IndexType to a 64 bits integer allows the map to contain more elements but each bucket_entry will take 16 bytes.

tsl::ordered_map<int, int, std::hash<int>, std::equal_to<int>, 
                 std::allocator<std::pair<int, int>>, 
                 std::vector<std::pair<int, int>>, std::uint64_t> map;