You are right to say that such functionality can be provided, but there is a cost to it. For example, a vector (or deque) of map iterators could be used to provide efficient access by sequential index. It does not make sense to add this along with std::map and std::multimap because not every use of maps and multimaps needs such functionality and hence should not automatically incur such a cost (and this would also change the time complexity of operations such as removing elements), but there is nothing stopping you from building on these containers for a container that meets your exact requirements, within what is computationally possible.Originally Posted by Programmer_P