c++: std::map iterative ordering for numeric ids - cross-compiler

Question

Quick question: using numeric id's and STL maps, will C++ always iterate over the pairs in the order of the numeric id? Could this change depending on the compiler or is it guaranteed by the STL spec?

Example:

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

int main(int argc, char **argv)
{
    std::map<int, std::string> testmap;

    testmap.insert(std::map<int, std::string>::value_type(0, "bob"));
    testmap.insert(std::map<int, std::string>::value_type(1, "jean"));
    testmap.insert(std::map<int, std::string>::value_type(2, "melissa"));
    testmap.insert(std::map<int, std::string>::value_type(3, "george"));
    testmap.insert(std::map<int, std::string>::value_type(4, "dave"));
    testmap.insert(std::map<int, std::string>::value_type(5, "sally"));
    testmap.insert(std::map<int, std::string>::value_type(6, "jessica"));
    testmap.insert(std::map<int, std::string>::value_type(7, "sandy"));
    testmap.insert(std::map<int, std::string>::value_type(8, "winston"));
    testmap.insert(std::map<int, std::string>::value_type(9, "pete"));
    testmap.insert(std::map<int, std::string>::value_type(10, "maxx"));

    for (std::map<int, std::string>::iterator map_item = testmap.begin(); map_item != testmap.end(); map_item++)
    {
        std::cout << map_item->second << std::endl;
    }

    std::cin.get();

    return 0;
}

It doesn't matter which order I add the pairs in, they will always come out in numeric order in G++. Will this be the same across compilers?

Secondly, given the small size of the map, would it make any conceivable difference to performance if I were iterating over a std::string array[11] instead of a map? Scenario being iterating over the map 60 times per second with various other stuff going on.

EDIT: Thanks to Drino I have the answer, however testing has shown that in the case scenario where a map has fewer elements than the array, it may perform much better dependent on the number of elements. Please see the test code used below to achieve this, and apologies in advance for the SDL code, it was faster than hand-scripting my own milliseconds function in C++. Compiled using mingw, g++ 4.8, -O2:

    std::map<int, std::string> testmap;
    std::string testarray[11];

    testmap.insert(std::map<int, std::string>::value_type(0, "bob"));
//    testmap.insert(std::map<int, std::string>::value_type(1, "jean"));
//    testmap.insert(std::map<int, std::string>::value_type(2, "melissa"));
//    testmap.insert(std::map<int, std::string>::value_type(3, "george"));
//    testmap.insert(std::map<int, std::string>::value_type(4, "dave"));
//    testmap.insert(std::map<int, std::string>::value_type(5, "sally"));
    testmap.insert(std::map<int, std::string>::value_type(6, "jessica"));
    testmap.insert(std::map<int, std::string>::value_type(7, "sandy"));
    testmap.insert(std::map<int, std::string>::value_type(8, "winston"));
    testmap.insert(std::map<int, std::string>::value_type(9, "pete"));
    testmap.insert(std::map<int, std::string>::value_type(10, "maxx"));

    testarray[0] = "bob";
    testarray[1] = "jean";
    testarray[2] = "melissa";
    testarray[3] = "george";
    testarray[4] = "dave";
    testarray[5] = "sally";
    testarray[6] = "jessica";
    testarray[7] = "sandy";
    testarray[8] = "winston";
    testarray[9] = "pete";
    testarray[10] = "maxx";

    SDL_Delay(2000); // Delay introduced to negate background effects of window creation and executable overhead

    Uint32 sdltime = SDL_GetTicks();
    unsigned int counter = 0;


    for (unsigned int looper = 0; looper != 100000; looper++)
    {
        for (unsigned int arrpos = 0; arrpos != 11; arrpos++)
        {
            if (testarray[arrpos] == "maxx")
            {
                counter++; // Included so the compiler doesn't optimise the loop out of existence.
            }
        }

    }

    std::cout << "num milliseconds array:" << SDL_GetTicks() - sdltime << std::endl;

    SDL_Delay(2000);  // Delay introduced to negate background effects of buffer out

    sdltime = SDL_GetTicks();
    counter = 0;


    for (unsigned int looper = 0; looper != 100000; looper++)
    {
        for (std::map<int, std::string>::iterator map_item = testmap.begin(); map_item != testmap.end(); map_item++)
        {
            if (map_item->second == "maxx")
            {
                counter++; // Included so the compiler doesn't optimise the loop out of existence.
            }
        }

    }

    std::cout << "num milliseconds map:" << SDL_GetTicks() - sdltime  << std::endl;

On this machine this routinely gives the output: num milliseconds array:14 num milliseconds map:11

Reversing the order of tests makes no difference. Removing the commented-out map insertions changes the results to the following: num milliseconds array:14 num milliseconds map:16

So, in the scenario where the number of map elements is variable or may not reach even half the maximum amount allowed, it may make more performant sense to use map instead of array, as the overhead of iterating the map is minor when the maximum is reached, but the benefits when the maximum is not reached are greater.

score 2 · Answer 1 · answered Apr 09 '14 at 00:47

2

You're using a map to store linear indices as keys. Just use a vector or an array. You shouldn't be concerned about the order a map stores items, it's always going to do it in the most efficient way possible, and you shouldn't have to assume anything about that.

You can also insert to the map like this:

testmap[0] = "bob";

Or like this:

testmap.insert(std::make_pair(1, "bob"));

answered Apr 09 '14 at 00:47

Aesthete

18,622
6
36
45

In this case it would be an array, as the vector iterators become too easily invalidated. Please see the following for reasons why the above insertions you've suggested are less performant: http://stackoverflow.com/questions/4286670/how-do-i-insert-into-a-map Also, you did not answer either of my questions, and please don't assume you know the reasons behind my asking them. If I explained them, the question would be much longer and without purpose. – metamorphosis Apr 09 '14 at 04:58
Don't get too far ahead of yourself. You didn't answer the question, and you might have learned something from my comment. Goodbye. – metamorphosis Apr 09 '14 at 05:35

score 2 · Accepted Answer · edited Apr 09 '14 at 05:23

Yes, the order will be the same. std::map uses order of keys to store the data (in C++11 there is unordered_map, which ignores order), so when you iterate over it smaller goes first.
For such small dataset an array (or vector, or list) will be much faster than a map.

[EDIT: Except in the case where the map has fewer elements (benchmarked). Depending on the number of elements present, the program may iterate over the map much faster than the array.]

c++: std::map iterative ordering for numeric ids - cross-compiler

2 Answers2