26

are STL maps ordered?

Specifically I need to know if std::map is ordered. So if I iterate over it, it will iterate with the first insert string first.

So will the below iterate A, C then B consistantly?

std::map<string,string> str_map;

str_map.insert(std::make_pair("A","Data"));
str_map.insert(std::make_pair("C","Data"));
str_map.insert(std::make_pair("B","Data"));
Ciro Santilli OurBigBook.com
  • 347,512
  • 102
  • 1,199
  • 985
CodingHero
  • 2,865
  • 6
  • 29
  • 42
  • 5
    Yes, you can actually pass in your own compare function so you can have it ordered however you want. http://www.cplusplus.com/reference/stl/map/ – leetNightshade Jun 30 '12 at 14:45
  • 4
    CodingQuant: Actually your example is not very good, since it doesn't distinguish between two meanings of "ordered": insertion order, and lexicographical order. std::map preserves *lexicographical* order, not insertion order. – j_random_hacker Jun 30 '12 at 14:48
  • 3
    @j_random_hacker: To be pedantic, std::map preserves lexicographical order only if your comparison predicate is based on a lexicographical comparison. – Oliver Charlesworth Jun 30 '12 at 14:56
  • 4
    Possible duplicate of [A std::map that keep track of the order of insertion?](http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion), 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:14

2 Answers2

55

are STL maps ordered?

Yes, a std::map<K,V> is ordered based on the key, K, using std::less<K> to compare objects, by default.

So if I iterate over it, it will iterate with the first insert string first?

No. It will iterate based on the sorted order, not the order that you inserted elements. In the case of std::string, it sorts in lexicographic order (alphabetic order).

If you want to iterate based on the insertion order, you're better off using a sequence container, such as a std::vector or a std::list.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
5

std::maps are sorted using either the given type's operator< or using a custom comparison function/functor if one is supplied as an argument to the constructor.

So no, when you iterate over the map, the first item you get won't be the one you inserted first - it will be the one that comes first alphabetically.

Of course for your sample code that doesn't make a difference because "A" is the first key you inserted and also the first one alphabetically.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • 1
    By default std::map uses `std::less`. How this works depends on the type Key but for normal STL types it is usually `operator<` – Martin York Jun 30 '12 at 16:08