Sign in to follow this  
Ryan_001

C++, unordered_vector

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
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
Erasing an element from a vector is O(n), but if you do the swap and pop trick, it's O(1)

// Erase element at iterator
vec.swap(iter, vec.end()-1);
vec.pop_back();


If you post all the requirements of the container then we can tell you what to use.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
much like 'unordered_set' is a bit of a misnomer (as sets in stl are defined to be sorted).


You misunderstand.

First off, we are not talking about "the STL"; that has not been relevant for many years. We are talking about the standard C++ library containers.

Set-ness has nothing to do with unordered-ness. The fundamental nature of a set is that it does not contain any duplicate elements. The C++ language specification does not define what a set is; set theory does. C++ simply tries to model the concept.

The standard library class std::set is documented as being ordered because it is ordered. It is ordered because that is required for efficient implementation of certain set operations. (It prevents efficient implementation of some other operations. That's life. Trade-offs everywhere.)

unordered_set is called unordered_set because it's unordered. We don't call std::set 'ordered_set' because it was there first: being ordered is default for set implementations in the language.

Containers become ordered because their implementation puts in effort to keep them ordered. std::vector does no such thing. It is unordered (except by coincidence).

There do exist implementations of 'sorted_vector' which wrap the a std::vector and keep its contents sorted, and perhaps even unique. This allows for faster iteration than a std::set, and the same kind of O(lg N) searching, probably with lower constant factors (because using a single contiguous memory block improves cache behaviour). The trade-off, of course, is slower insertion, since inserting into the middle of a std::vector is O(N) (everything must be shifted to make room) whereas inserting anywhere in a std::set is O(lg N) (the insert position must be found, and the tree may require rebalancing; both of these are O(lg N)).

In general, it is a better idea, when you are asking people to find a class for you, to describe what you want it to do, rather than what you think it would be named. We are not Google.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this