Efficient STL Insertion Tip of the Month

Oftentimes, there are multiple ways to accomplish what you want when using the C++ Standard Template Library. Usually we choose what we used last time or what we read in a book or what we copied from somewhere else in the code. But it’s always valuable to understand the differences, particularly when performance matters. Consider the case of copying items from one container to the end of another, when the container is a vector, deque or list. You might write:

copy( first, last, back_inserter( container ) );

That would be entirely correct. All of the elements from first up to (but not including) last would be inserted at the end of container. The back_inserter method repeatedly calls push_back() to add the new items.

Now consider this snippet:

container.insert( container.end(), first, last );

This code is also correct. All of the elements from first up to (but not including) last are inserted at the end of container. Now, which performs better?

The back_inserter calls push_back() multiple times. Therefore, it can trigger multiple vector reallocations. That’s bad. The insert sequence method will perform at most one vector reallocation. That’s good. There are also benefits for deque. Hence, the second code snippet will always perform at least as well, if not better, than the first snippet.

Rule of thumb: when container is a vector, deque or list, always write

container.insert( container.end(), first, last );

to add a list of elements to container. Thanks to STL for the tip. Happy coding!

This entry was posted in C++, Game Programming. Bookmark the permalink.

2 Responses to Efficient STL Insertion Tip of the Month

  1. (there might be stupid errors in the code below, but you get the point, don’t you? :))

    Other possible comparisons are:

    // one alloc, no default ctor call but…
    container.reserve(container.size() + std::distance(first, last));
    // … we still push_back elements ; calls copy-ctor with placement new (hopefully)
    std::copy(first, last, back_inserter(container));

    Which then compare to

    // one alloc, will call the default constructor for each object
    container.resize(container.size() + std::distance(first, last));
    // does not need to call push_back ; calls operator=
    std::copy(first, last, container.end());
    // this is very bad: default ctor + operator= is far inferior to a single call to copy-ctor

    Which finally compare to :

    // no default ctor call, one alloc, copy-ctor called N times with placement new (hopefully)
    container.insert(container.end(), first, last);

    A priori, the insert() will outperform the other alternatives – even when the complexity of the operation is the same, although the first alternative should give results that are quite similar to insert() when used on small data sets.

    insert() does the following:

    oldsize = size
    size = newsize
    p = grow (p, size)
    f = p + oldsize
    while (first < last)
    new (f)(*first)

    (of course, I don't add the necessary exception resistance code).

    reserve+copy+back_inserter does the following

    size = newsize
    p = grow (p, size)
    while (first size // effect on cache?
    new (f)(*first)
    // leave push_back

    This is a bit different, and probably a bit less performant than the insert() alternative.

    Anyway, back_inserter is not very useful to add a list of known size as – you noted it – it will repeatedly call push_back and might trigger unecessary sequence realloc. It’s kind of useful when dealing with stream iterators but should be avoided in nearly all other cases as there is probably a far better alternative.

    As always in C++, there are many ways to get the same result, but some are better than others.

  2. Oh, by the way: your article was ripped (withour proper credit) here: http://realcoding.tk/efficient-stl-insertion-tip-of-the-month/, which is just some kind of c++ programmer honeypot (redirects to some ad server a few seconds after you land on the page).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s