Map or unordered map?

[volang]

I have a map where the order never matters. The only important thing is that I get direct / fast access to the value of the specified key.

Maintaining the order after removal of elements is also not desirable (eg automatically rearranging all elements after removal)

Is unordered_maps (or something else) better for my needs?

[malibor]

None of the 2 will give you what you want, the solution is to use vector of pairs.

ex:
std::vector<std::pair<KEY_TYPE, VALUE_TYPE>>;

Another solution is to write your own container for the purpose, ie. to have some specialized functionality.

EDIT:

Maintaining the order after removal of elements is also not desirable (eg automatically rearranging all elements after removal)

If that means you do not want to keep the order, then unordered_map is the way to go, in any case both the map and unordered_map do not quarantee configurable order. they just store elements by using different algorithms.

as for speed unordered_map is faster to access elements but slower to iterate based on order, while for map the oposite is true.

[jonnin]

to me it would be vector or unordered map, depending on what *else* you are doing. Are you inserting and deleting a lot or is it a 'read a file once, lookup lots' type problem, etc...

[dhayden]

None of the 2 will give you what you want, the solution is to use vector of pairs.

I don't see how a vector of pairs will provide fast access by key. Won't that actually be a linear search?

Hash tables like std::unordered_map are usually faster than trees like std::map but there are a few possible gotchya's:
- You have to examine the entire hash key to generate the key value. In contrast, when comparing keys, you might have to examine only a small fraction. So if the keys are large, then a map may be faster.
- It's essential that you have an appropriate number of hash buckets. Too many buckets and you're wasting space. Too few and you're spending all your time traversing the items in a bucket, which gets slower than a map. I usually go for an average of 4 items per bucket.
- It's also essential that you have a good hash function. You don't want all your items in just a few buckets.

Finally, is the speedup worth the hassle and possible gotchya's? Maps are pretty quick already.

[malibor]

I don't see how a vector of pairs will provide fast access by key. Won't that actually be a linear search?

That's true (except if you don't need access by key), but it looks like the OP doesn't want a container which would "automatically rearrange all elements after removal"

performance wise, unordered_map is the best choice IMO for random access which is what the OP wants.

Definitely worth writing own container if performance is really that important.

[helios]

What's the type of the key and the distribution of existing keys in the space of possible keys?

[kbw]

It's looking like an unordered_map to me, provided a suitable number of buckets and hash is used.

[dhayden]

That's true (except if you don't need access by key)

The OP specifically said he/she needed "direct / fast access to the value of the specified key."

but it looks like the OP doesn't want a container which would "automatically rearrange all elements after removal"

I think you've misinterpreted the post. I interpret that paragraph to mean "Maintaining the order after removal of elements is also not required, (eg automatically rearranging all elements after removal is okay)" So I think they meant they don't care if the items get rearranged.

Hopefully the OP will respond to clear these things up.