Saturday, December 20, 2008




Let’s say you have two STL std::maps with identical types, and you want to copy all the elements from one to the other. The easiest way to do this is to use map::insert():

typedef std::map map_t;

map_t map1;
map_t map2;

// Copy all elements from map1 to map2
map2.insert(map1.begin(), map1.end());

Alternatively, you could use the STL std::copy algorithm:

// Copy all elements from map1 to map2.
std::copy(map1.begin(), map1.end(), std::inserter(map2, map2.begin()));

Both methods’ performance should be an amortized O(n) because they insert records in sorted order and use the hinting form of map::insert.

Note that because both methods ultimately call map::insert they will not overwrite a preexisting key’s associated value. In other words, if map1 has the value V1 associated with key K and map2 the value V2 associated with the same key K, V2 will remain in map2 after the copy operation.

Let’s say you want to perform the copy but have map1’s values overwrite map2’s for identical keys. The first way to solve this problem that entered my mind was to write my own OutputIterator which performs an overwriting assignment and pass it to std::copy. However, there’s a far simpler approach. You can copy map2’s values into map1, relying on the fact that map2’s values won’t overwrite map1’s, and then swap the results:

map1.insert(map2.begin(), map2.end());

Thanks, Sam, for helping me figure all this out.

No comments: