Jump to content
  • Advertisement
Sign in to follow this  
Ryan_001

C++, unordered_vector

This topic is 2804 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
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.
You won't find any.


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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
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.
The standard library already has an unordered vector class; it's called vector. So, I doubt there's any need to create one from scratch.

What behavior are you looking for exactly?

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!