In the C++0x standard there will be unordered_map, how does this compare to boosts unordered_map?

Question

Which is more efficient? Are there any good benchmarks out?

Answer 1

C++11's std::unordered_map specification is similar to boost::unordered_map which is based on tr1::unordered_map. That being said, there are some small differences. The addition of rvalue references in C++11 result in the addition of the emplace and emplace_hint functions that may be useful for performance.

C++11 is now widely implemented and so you should be able to use std::unordered_map out of the box. C++14 does not change it significantly and C++17 will (probably) add the insert_or_assign and try_emplace member functions.

Answer 2

In the c++0x latest standard draft n3225, there's a section 23.6.1 class template unordered_map.

So it is already there.

C++0x unordered_map is proposed based on boost one. Boost library itself also has a namespace tr1::unordered_map, which shares the implementation of its own boost::unordered_map.

If you want to compare (of course you don't need to compare boost with boost), I think several other compilers, including microsoft visual studio 2010, and gcc, do have their own unordered_map implementation. You can use them by assuming they are under namespace tr1.

#include <unordered_map>
...
std::tr1::unordered_map<...>

I didn't know any benchmark yet but I think at this early time, any benchmarking doesn't make sense because the compiler implementer will definitely optimize their own implementations when the real standard is finalized and more people are going to use the library.

Answer 3

One minor point not yet mentioned, the std::hash function is only required to be able to compute hashes of builtin types and strings (and a few other types). The boost::hash function can compute hashes of more complex objects such as pair and tuple. Also boost has a hash_combine function to assist in creating hashes for user-defined types.

This means that std::unordered_set< pair<int, int> > won't compile, but boost::unordered_set< pair<int, int> > will.

You can use boost::hash with std::unordered_* if needed.

(Reference: Item 6.18 in the Library Extension Technical Report Issues List.)

Answer 4

It depends on the implementation and the data set in question. When I was playing around with unordered_map for a blog post I found that VS10's std::unordered_map perfromed much worse than boost::unordered_map for the input I used (I didn't build a thorough benchmark). In theory thought there shouldn't be a difference.