Olivier Langlois's blog

Mr. Sutter's books biggest strength to my opinion is that they bring together a bunch of original advanced C++ topics that you cannot find anywhere else. This book has its share of very original content but I feel like the ratio original content vs topics that you can find in other books is lower in this book than with the other books of the serie. The most interesting section in this book in my opinion is the one on exception safety and the less original section is the one on generic programming and STL as you can find much of the information contained in this section in other books such as Effective STL from Scott Meyer or C++ Template from David Vandervoorde and Nicolai M. Josuttis.

In item 24 of the book Effective STL, Scott Meyers explains to be careful about using the overloaded subscript operator (std::map::operator[]) when efficiency is important. The reason behind this advice being that when that operator is used to refer to an item that is not yet in the container, it will insert a new pair in the map by using the default constructor of the value part and then usually an assignation will be performed on the value reference returned by the operator. For non-trivial constructors and assignment operators, this can result to unnecessary overhead.

He then proceeds to present a function called efficientAddOrUpdate() that calls std::map::lower_bound() then performs some tests on the returned iterator to make sure that it is not equal to end() iterator and if the key pointed by the iterator is equivalent to the key used with lower_bound(). If the test is successful, then the value pointed by the iterator is updated or else std::map::insert() is called with the std::map::lower_bound() returned iterator as hint for the insertion point.

Few days ago, I had to recreate the efficientAddOrUpdate() function without my copy of Efficient STL book available and I have being struggling for a good half an hour to an hour trying to recall the implementation details or find them back by doing searches on the Internet. I have finally come to the following realization by giving up searching the Internet and looking at the <map> header file source code:

Scott Meyers efficientAddOrUpdate() function code is almost identical to the operator[] member source code function minus minor modifications

Here is the source code operator[]:

mapped_type& operator[](const key_type& _Keyval)
{   
    // find element matching _Keyval or
    // insert with default mapped
    iterator _Where = this->lower_bound(_Keyval);
    if (_Where == this->end() || 
        this->comp(_Keyval, this->_Key(_Where._Mynode())))
    _Where = this->insert(_Where,
            value_type(_Keyval, mapped_type()));
    return ((*_Where).second);
}

and efficientAddOrUpdate() code derived from it would be:

iterator efficientAddOrUpdate(map &m,
         const key_type& _Keyval,const val_type& _Val)
{
    iterator _Where = m.lower_bound(_Keyval);
    if (_Where == m.end() ||
        m.key_comp()(_Keyval, _Where->first)))
    {
        return m.insert(_Where,value_type(_Keyval, _Val));
    }
    else
    {
        _Where->second = _Val;
        return _Where;
    }
}