C++, unordered_vector
Author
Much like an unordered_set and unordered_map, I would like to have an unordered_vector. I couldn't find anything in boost and a quick search on google didn't yield anything of value. So before I go and write my own I thought I'd bring it up and here and see if anyone had heard of an stl compliant unordered_vector container.
How would you expect an unordered vector to be any different from a regular vector?
I'm no STL pro but it would seem that vectors are unordered by definition, whereas typical sets and maps sort their items on insertion, hence they also have "unordered" versions.
I'm no STL pro but it would seem that vectors are unordered by definition, whereas typical sets and maps sort their items on insertion, hence they also have "unordered" versions.
Quote:Original post by Ryan_001You won't find any.
Much like an unordered_set and unordered_map, I would like to have an unordered_vector. I couldn't find anything in boost and a quick search on google didn't yield anything of value. So before I go and write my own I thought I'd bring it up and here and see if anyone had heard of an stl compliant unordered_vector container.
This is simply the nature of the data structures involved.
The sequential containers (vector, list, deque) are unsorted. They are based on the basic data structures of the same names. Adding items will keep them in the order you specify. You can insert at specific places, modify arbitrary values, and remove values.
The associative containers (map/multimap, set/multiset) are based on a sorted heap or tree (depending on implementation). They are self-sorting. Just like a sorted heap or tree data structure, you cannot modify the key without destabilizing the structure; you similarly cannot insert an item to a specific location without destabilizing it.
Use the right tool for the job. Associative containers are very different than sequential containers. They have very different performance characteristics, and are made for different uses.
Quote:Original post by Ryan_001
I would like to have an unordered_vector.
std::vector<>.
Wasn't that easy.
Quote:Original post by Ryan_001The standard library already has an unordered vector class; it's called vector. So, I doubt there's any need to create one from scratch.
Much like an unordered_set and unordered_map, I would like to have an unordered_vector. I couldn't find anything in boost and a quick search on google didn't yield anything of value. So before I go and write my own I thought I'd bring it up and here and see if anyone had heard of an stl compliant unordered_vector container.
What behavior are you looking for exactly?
Author
I understand that 'unordered_vector' is a bit of a misnomer, much like 'unordered_set' is a bit of a misnomer (as sets in stl are defined to be sorted).
I was looking for a hash based container that doesn't store its data as a linked list/tree but rather as a single continuous block of memory. Constant time lookups, amortized constant insertions, ect...
I was looking for a hash based container that doesn't store its data as a linked list/tree but rather as a single continuous block of memory. Constant time lookups, amortized constant insertions, ect...
well, you can use a vector for that. Just insert the new element at hash value position
vector.reserve(max_size);
int hash = hash_this( whatever);
vector[hash] = whatever you want to store;
Of course, it's only a simple example
vector.reserve(max_size);
int hash = hash_this( whatever);
vector[hash] = whatever you want to store;
Of course, it's only a simple example
Author
Quote:Original post by Juanxo
well, you can use a vector for that. Just insert the new element at hash value position
vector.reserve(max_size);
int hash = hash_this( whatever);
vector[hash] = whatever you want to store;
Of course, it's only a simple example
And that's quite similar to what I usually do. I was just wondering if there was a standard one floating around that I was unaware of. Maybe buried deep in boost somewhere I forgot to look, or perhaps some non standard extensions that been around for a while (like the old SGI hash_map and hash_set).
Quote:Original post by Ryan_001
I understand that 'unordered_vector' is a bit of a misnomer, much like 'unordered_set' is a bit of a misnomer (as sets in stl are defined to be sorted).
I was looking for a hash based container that doesn't store its data as a linked list/tree but rather as a single continuous block of memory. Constant time lookups, amortized constant insertions, ect...
That sounds a lot like unordered_set, actually.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
