ordered hashmap recommendation
Does anyone know ordered hashmap libraries similar to boost/container/flat_map? I couldnt find proper libraries for ordered hashmaps on the internet. Thanks in advance!
What exactly do you mean by "hashmap"?
In what sense is flat_map a "hashmap"?
It's certainly not a hashtable, so I'm not sure what the word "hash" means here.
Hashtables are unordered by design.
std::map is ordered. Why is it not sufficient?
And if you really want something like flat_map, why not use flat_map?
In what sense is flat_map a "hashmap"?
It's certainly not a hashtable, so I'm not sure what the word "hash" means here.
Hashtables are unordered by design.
std::map is ordered. Why is it not sufficient?
And if you really want something like flat_map, why not use flat_map?
There are many unordered hash table libraries like bytell::hashmap, ska::flat_hashmap,absl:.flat_hashmap rather than std::unordered_map.
I am actually doing a research for fast hash tables since std unordered_map or std::map is not sufficient enough in terms of speed for my case. However when i try to find ordered hash tables like boost's library that is boost::container::flat_map(it is a ordered hash map), i cant find a proper ordered hash maps. To sum up i found many unordered hashmaps but i need to find faster ordered hashmaps than boost's if there is any.
I am sorry if i talk nonsense since i am not an expert.
I am actually doing a research for fast hash tables since std unordered_map or std::map is not sufficient enough in terms of speed for my case. However when i try to find ordered hash tables like boost's library that is boost::container::flat_map(it is a ordered hash map), i cant find a proper ordered hash maps. To sum up i found many unordered hashmaps but i need to find faster ordered hashmaps than boost's if there is any.
I am sorry if i talk nonsense since i am not an expert.
Last edited on
| boost::container::flat_map(it is a ordered hash map) |
No it isn't.
How can a hash table be ordered?
closed account (z05DSL3A)
| flat_map is similar to std::map but it's implemented by as an ordered sequence container. The underlying sequence container is by default vector but it can also work user-provided vector-like SequenceContainers (like static_vector or small_vector). |
What i mean by ordered is when you insert a new element into that hash table its inserted for example according to a price value in an order less to more.
as far as i know boost container flat map was an ordered hashmap.
as far as i know boost container flat map was an ordered hashmap.
| as far as i know boost container flat map was an ordered hashmap |
It is ordered, yes.
But is is not a hashtable.
That is where you are confused.
if unordered map isn't fast enough, something is possibly wrong with your approach.
are you using reserve? emplace? Maybe, your own hash function is better (faster or more entropy)?
and, on that note, what is it that you want 'ordered' ? do you need to iterate the whole blob of data and process it in some sort of sorted order? Is the data changing (if so, how frequently?!) or static? Tell us what you can in broad terms .. how much data (# of records), and what the end goal is (I want to print it out in order, or I want to access record # 2718281828 instantly)
this is the sort of thing that if you can't get the c++ tools to work, writing your own special snowflake code to do the job is likely going to beat any third party stuff out there.
are you using reserve? emplace? Maybe, your own hash function is better (faster or more entropy)?
and, on that note, what is it that you want 'ordered' ? do you need to iterate the whole blob of data and process it in some sort of sorted order? Is the data changing (if so, how frequently?!) or static? Tell us what you can in broad terms .. how much data (# of records), and what the end goal is (I want to print it out in order, or I want to access record # 2718281828 instantly)
this is the sort of thing that if you can't get the c++ tools to work, writing your own special snowflake code to do the job is likely going to beat any third party stuff out there.
Last edited on
What do you find inefficient about boost's flat_map? Inserting items? Retrieving items?
Is your data ordered or random? Do you have all the data in advance, or is the data coming in in a real time feed?
I'm not familiar with flat_map's implementation, but from the boost documentation, we see the following:
To me, this implies a few things. 1) Inserting anywhere but at the end is going to be expensive. The flat_map will have to be searched to find the insertion point (if you don't supply an insertion iterator). If not inserting at the end, all the elements past the insertion point have to be moved. 2) The second implication is that a (probably bisecting) search has to be to locate an element by a key. 3) Like a std::vector, the data area has to be reallocated and copied periodically unless sufficient space is reserved in advance. See flat_map::reserve().
Is your data ordered or random? Do you have all the data in advance, or is the data coming in in a real time feed?
I'm not familiar with flat_map's implementation, but from the boost documentation, we see the following:
| flat_map is similar to std::map but it's implemented like an ordered vector |
To me, this implies a few things. 1) Inserting anywhere but at the end is going to be expensive. The flat_map will have to be searched to find the insertion point (if you don't supply an insertion iterator). If not inserting at the end, all the elements past the insertion point have to be moved. 2) The second implication is that a (probably bisecting) search has to be to locate an element by a key. 3) Like a std::vector, the data area has to be reallocated and copied periodically unless sufficient space is reserved in advance. See flat_map::reserve().
Last edited on
Topic archived. No new replies allowed.