Efficient update of stl containers

I have seen dozens of times code like this to update an entry in a map:

typedef std::map<std::string, int> Items;
Items items;	
	
Items::iterator it = items.find("counter");

if(it == items.end())
{
   items.insert(std::make_pair("counter", 1));
}
else
{
   it->second++;
}

The problem with this code is that you are traversing the map two times if the item is not found in the map, one for the first find and one more for the insert.

You can improve the code with something like this:

std::pair<Items::iterator, bool> res = items.insert(std::make_pair("counter", 1));

if(!res.second)
{
   (*res.first).second++;
}

This is notably better. You only traverse the map one time. But there is still a problem with this code: you are creating the pair even when you do not need it. In this case the pair is simple and its creation is not a problem, but imagine a pair with more complex objects hard to create. You can avoid the creation with a code like this:

Items::iterator lowerBound = items.lower_bound("counter");

if(lowerBound != items.end() && !(items.key_comp()("counter", lowerBound->first)))
{
   lowerBound->second++;
}
else
{
   items.insert(lowerBound, std::make_pair("counter", 1));
}

Although being more efficient, this code is more obscure, so in case you do not need those nanoseconds you can live with the more clear second option.

Happy coding,
http://entland.homelinux.com/blog/

Nice post

Well, I know that operator[] supplies a default constructed value if the item is not in the map. With VC8, this one line does the same thing as your example:

++items["count"];

Of course, this is just a special (trivial) case and I'm not sure if all compilers will initialize an int to zero. The lower_bound usage seems much safer.

EDIT: I looked at the source code for operator[] and it uses lower_bound as in your example.

Originally Posted by monjardin

Of course, this is just a special (trivial) case and I'm not sure if all compilers will initialize an int to zero.

Actually they should if they are compliant. Explicitely default-constructed primitives always initialize to 0, and std::map default-constructs all it's new nodes (as all containers do btw).

But to return to the topicstart, I don't see how a map.insert() would return a complex pair, it's just an iterator and a boolean, and the iterator is usually just a pointer to a node in the tree. Also, who is to say that supplying the lower_bound to the insert operation is actually a [i]good[/] hint? If a specific map implementation only stores it's values in leaf nodes, in the worst case scenario it has to traverse all the way up the root to come down again on the other side to insert the node there.

monjardin, the problem with operator[] is that it is not efficient when the item is not found in the map. In that case, first the item is created with the default constructor and later your value to be inserted is copied over. This is described is Scott Meyer's Book I think.

.oisyn, lower_bound is the best hint you can give to insert. Iteration from begin to end in associative containers is guarantee to be ordered. An implementation like the one you are describing would be a really bad implementation, for example, you couln't iterate from begin to end in O(n) time.

Agreed, but it sure saves a hell of a lot of typing.
Also, the increment operation is the only additional overhead in this case. I'd take a single increment (on first use) over the additional lines of code almost any day.

a big problem with all three methods is that you doing a string compare. Every entry in the map have to be checked per character, easy with some int-constants, COUNTER instead of "counter", just use a id generator. Much faster...

What if you are getting the string from user input? Is it still faster to generate an integer for comparison rather than a simple string compare? Besides, the OP's points seem applicable even to integer key maps.

In a map, you will compare the string O(log n) times. Probably you will want to use a hash_map.

But the point of the code works with all the types you use for indexing your map, hash, etc...

String searches aren't that inefficient, as comparisons of unequal strings will frequently terminate after just a couple of characters. You only pay the full cost of the comparison when you have found what you are looking for.