Home
Fractals
Tutorials
Books
My blog
My LinkedIn Profile

BOOKS i'm reading

Napoleon Hill Keys to Success: The 17 Principles of Personal Achievement, Napoleon Hill, ISBN: 978-0452272811
The 4-Hour Workweek: Escape 9-5, Live Anywhere, and Join the New Rich (Expanded and Updated), Timothy Ferriss, ISBN: 978-0307465351
The Fountainhead, Ayn Rand, ISBN: 0452273331
Web Hosting Canada

mailto:olivier@olivierlanglois.net

Archives for: July 2007, 31

07/31/07

Permalink 09:54:07 pm, by lano1106, 126 words, 2350 views   English (CA)
Categories: C++, C++

More Exceptional C++

More Exceptional C++, Herb Sutter, ISBN: 020170434X

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.

Permalink 09:35:48 pm, by lano1106, 386 words, 4313 views   English (CA)
Categories: C++

How to efficiently add or update an item in a C++ STL map

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;
    }
}

Olivier Langlois's blog

I want you to find in this blog informations about C++ programming that I had a hard time to find in the first place on the web.

July 2007
Sun Mon Tue Wed Thu Fri Sat
 << < Current> >>
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Search

Custom Search

Misc

XML Feeds

What is RSS?

Who's Online?

  • Guest Users: 6

powered by
b2evolution