boost::unordered_map maintains order of insertion?

Question

I am looking for a container which provides std::map like interface but maintains the order in which elements are inserted. Since there will not be too many elements in the map, the lookup performance is not a big issue. Will boost::unordered_map work in this case? i.e. does it maintain the order of insertion. I am new to boost library and hence want to know what exactly meant by 'unordered' ?

Answer 1

unordered_map doesn't maintain the order of insertion. Unordered in this case means that the observable order of elements (i.e. when you enumerate them) is unspecified and arbitrary. In fact, I would expect that the order of elements in an unordered_map can change during the lifetime of the map, due to rehashing when resizing the map (that's implementation dependent though)

Answer 2

Read about Boost.Multiindex. It gives you an opportunity to create a container that has both access to data by key (like std::map) and sequenced acess to data (like std::list).

This is an example.

Answer 3

When I needed this last time, I used a std::vector< std::pair<const Key, Value> >. I didn't need much of the std::map interface so I didn't bother with is, but it seems it should be fairly easy to slap a map-like interface around this.

Also, be sure to look at the answers to this question.