Efficient update of stl containers

May 17, 2006 @ 23:08 | In CodeGems, Programming | 6 Comments |

Update: Fixed some bugs in the sample code.
Update: Note added in the third option about the hint.

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. Apart from being more obscure, the hint is only that, a hint. The implementation can ignore it. As noted by Steven in the comments below, Visual Studio ignores it for the hash_map and hast_set containers.

TrackBack URI

Hola Jesús.

Me surge una duda. En el tercer modo ¿no se recorre también dos veces el mapa? En el primero se recorre, según dices, en el find y en el insert. Entonces, ¿no se hace también en el tercero con el método lower_bound y con el insert?

P.D.- Saluda de mi parte a los compañeros. Me acuerdo mucho de vosotros.

Comment by Fran Cadaval
May 18, 2006 @ 11:14 #
Que tal fran, ¿todo bien?

En el tercer modo se usa la versior de insert que recibe un iterador como primer parametro. Este iterador es una ayuda a la insercion. Si el iterador es correcto la inserción se garantiza en tiempo constante.

Comment by ent
May 18, 2006 @ 20:53 #
Pues la verda es que sí, me van muy bien las cosas, a ver si un día me doy una vuelta por “Los Madriles” y os hago una visita.

Respecto a la respuesta pues no me había fijado en ese detalle. Muchas gracias, ha sido muy interesante.

Comment by Fran Cadaval
May 19, 2006 @ 9:10 #
Hola Yisus

aja…aja…si…si…lo entiendo…si…si…

…

…

…

…

Está muy bien la canción, eres un gran cantautor.

…

…

JAJAJA

Comment by Juan
May 19, 2006 @ 18:28 #
Just a little note – the third variant will be fast as predicted for set and map, but not for hash_map and hash_set, because the VC2005 implementation of insert(iterator,value) method of these containers simply ignores the hint iterator.

Although you can find the following text for hash_map and hash_set in MSDN,

“Insertion can occur in amortized constant time for the hint version of insert, instead of logarithmic time, if the insertion point immediately follows _Where.”

It is not true…

Comment by Steven
July 5, 2007 @ 10:55 #
Yes, Steve, good point. I have just checked that with Visual Studio 2005 SP1.

iterator insert(iterator, const value_type& _Val)
{ // try to insert node with value _Val, ignore hint
return (insert(_Val).first);
}

Anyway, insertions in the hash_ containers are O(1), so it is not as serious as it could be in the sorted containers (map, set, etc).

Option 2 seems to be the better option for this containers then.

Thanks,

Comment by ent
July 5, 2007 @ 13:29 #