How to ensure that a std::map is ordered?

Question

Using a std::map<int, ...> how can I ensure at inserting time that iterating over it will take place in ascending order of the integer key?

Answer 1

You don't have to do anything. The map will be in ascending order according to the values of the key.

Internally, the map performs a comparison between keys to order its elements. By default, it uses std::less<KEY>, which is equivalent to bool operator<(int, int) for integers. For user defined types, you have to options:

1. Implement a bool operator<(const MyType&, const MyType&) implementing a strict weak ordering comparison between your user defined types. Use this if your type has a natural ordering

2. Provide a binary functor that implements strict weak ordering, which you can pass as the 3rd template parameter to the map. Use this if your type does not have a natural ordering, or if you want to build the map with an ordering different to that used by std::less<Key> via the bool operator<(...) from point 1.

What typically happens behind the scenes is that the map is implemented as a self-balancing binary tree, and the strict weak ordering is used to place new elements in the map, and to determine whether two elements are equal. As an aside, the same logic applies to std::set, where the key and value are one and the same.

Answer 2

std::map does that itself. You don't have to do anything.

By default it sorts the keys in the increasing order. If you want it to do sorting in decreasing order, then pass std::greater<T> as third template argument to std::map.

std::map<int, X>  m1;                    //sorts key in increasing order
std::map<int, X, std::greater<int>>  m2; //sorts key in decreasing order
std::map<int, X, std::less<int>> m3;     //sorts key in increasing order

The default argument for third template parameter is std::less<T>, so above m1 and m3 are same types!

Demo:

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::cout << "\nkeys are in increasing order: \n";
    std::map<int, std::string> m1;
    m1[5] = "first insertion but higher key";
    m1[1] = "second insertion but lower key";
    for(auto const & item : m1) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";

    std::cout << "\nkeys are in decreasing order: \n";   
    std::map<int, std::string, std::greater<int> > m2;
    m2[1] = "first insertion but lower key";
    m2[2] = "second insertion but higher key";
    for(auto const & item : m2) 
       std::cout << "{" << item.first  <<"," << item.second << "}\n";
}

Output:

keys are in increasing order: 
{1,second insertion but lower key}
{5,first insertion but higher key}

keys are in decreasing order: 
{2,second insertion but higher key}
{1,first insertion but lower key}

Notice that in both cases the items are ordered as specified by the third template argument of std::map. The output doesn't depend on the order of insertion, rather the order of the keys!

Live demo

There is also std::unordered_map which doesn't sort elements.

Answer 3

map is usually implemented as a binary search tree, therefore iterators would give you sorted keys already.

If you don't care about the order you may use unordered_map (from c++11 or boost) which would give you some speed in trade of the order.