Saturday, May 24, 2014

Iterate a map in added order, not key order, using C++11

I’m loving C++11. Most of the things only save you a few keystrokes. But C++ was a verbose language, and those saved keystrokes mean the code becomes more readable and more maintainable.
Here is a quick example refactor. I had some key-value pairs, and was using a std::map (I’ve shown the value type as T to avoid cluttering this example):
std::map< std::string, T> data;
...
data [ key ] = value;
...
for(const auto &entry : data){
    std::cout<<"Label:" << entry.first << "\n";
    std::cout<< entry.second.something << "\n";
    }
You can see I’m already using a C++11-ism, with the range-based for loop, and auto. That is so much nicer that I’m not even going to show you the old way it would’ve been done.
The problem was I didn’t want to iterate through the map in key order, I wanted to iterate through in the order the items was added. My first idea was to switch to using two vectors, one for the keys, one for the values. But parallel data structures are a nasty code smell.
Then I thought of using std::pair. And the above code became this:
std::vector< std::pair<std::string, T> > data;
...
data.push_back( {key,value} );
...
(as above)
First thing to observe is that even though the data structure is now completely different, my for(){...} loop is completely the same. This was partly luck: a std::map iterator has first and second elements, and so does a std::pair. But we also need to give a big thanks to auto: it saved us having to even think about what the new iterator type is.
Did you spot the second C++11-ism? It slipped by so naturally it might not even have registered. Here it is: {key,value}
In earlier versions of C++ I would have had to write:
data.push_back( std::make_pair(key,value) );
Only 14 keystrokes saved, but those 14 were pure distraction, and won’t be missed.
(This refactor is the correct approach in older versions of C++ too, by the way. All C++11 brings to the party is that it is now easier to do.)
Written with StackEdit.