> BTW, for very small numbers of items the most efficient solution is often a plain std::vector + linear search.

This is why flat_map is a great solution. It's basically an ordered vector with a map-like interface, but without the memory allocation (and cache locality issues) for each node. Until you start getting into thousands of elements it is probably the best choice of container.