15

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?

danijar
  • 32,406
  • 45
  • 166
  • 297
  • 2
    The order you insert it is lost (unless you insert it exactly in sorted order already), if that's what you're asking. – GManNickG Jan 22 '13 at 16:55
  • 2
    Possible duplicate of [Is the order of iterating through std::map known (and guaranteed by the standard)?](http://stackoverflow.com/questions/7648756/is-the-order-of-iterating-through-stdmap-known-and-guaranteed-by-the-standard) – Ciro Santilli OurBigBook.com Jan 02 '17 at 10:15

3 Answers3

31

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.

user1146657
  • 194
  • 3
  • 15
juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • I do not understand how the map does that. For integer keys that is quite easy but what happens if I would use a class as key? – danijar Jan 22 '13 at 16:56
  • 2
    @sharethis: `std::less` (at least by default) is what happens. –  Jan 22 '13 at 16:58
  • 1
    @sharethis You have to provide an ordering function (or functional object) for `std::map`. If not, it defaults to `std::less`, which in turn uses `<` by default. Unless there is a natural ordering for your class (such that `<`, `>` etc. make sense in general), providing an ordering operator is the best solution. – James Kanze Jan 22 '13 at 16:58
  • @Fanael, JamesKanze. Now I understand how a `std::map` works. It makes sense now, thanks! – danijar Jan 22 '13 at 16:59
17

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.

Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • Small optimization, which is also part of clang-tidy modernize checks: you should define them transparently ;) `std::map>` – jaques-sam Apr 28 '21 at 09:11
2

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.

none
  • 11,793
  • 9
  • 51
  • 87
  • 1
    It doesn't have to be implemented as a tree. It just has to be ordered, and meet certain complexity restrictions. A search tree will do that, and so will various other data structures. – Mike Seymour Jan 22 '13 at 17:03
  • This still implies that whether or not elements are sorted by key may depend on the mode of implementation, which is false; sorting by keys is a requirement, not just a detail of the (most common) implementation. – underscore_d Dec 10 '17 at 12:22