Improving efficiency of std::copy() with back_inserter() or inserter()

Question

back_inserter and insert_iterator are very handy, but they're also very inefficient!

When you're appending chars, for example, there is a great deal of overhead for every element when you're copying, when in many situations, there really doesn't need to be.

Is there a way to make them more efficient?

Answer 1

Yes, you can define a new version of std::copy which can hijack optimizable calls. :)

Below is an example (or "hack", if you prefer to see the glass half-empty) for Visual C++ and GCC.

On my personal computer (I use VC++ 2010), the code below makes calls ten times faster!
A benchmark for GCC's is also here, showing a 5x difference: old version against new version

But before you use it:

Note that this code assumes the container provides a vector-like interface.

As currently written, this only works for C++11, because it uses the type_traits header's metaprogramming capabilities to only optimize those situations in which the copy operation would stay exception-safe.

If you don't need the exception safety (though you should think twice before actually doing this), or if you have another way of checking for such data types, then you can change

typename enable_if<..., typename insert_iterator<C> >::type

to:

insert_iterator<C>

and the rest of the code should work for C++03 as well.

namespace std
{
    template<class FwdIt, class C>
    back_insert_iterator<C> copy(
        FwdIt begin, FwdIt end, back_insert_iterator<C> it,
        forward_iterator_tag * =
          static_cast<typename iterator_traits<FwdIt>::iterator_category *>(0))
    {
        struct It : public back_insert_iterator<C>
        {
            using back_insert_iterator<C>::container;
            static C &deref(C &c) { return  c; }
            static C &deref(C *c) { return *c; }
        };
        copy(begin, end, inserter(It::deref(static_cast<It &>(it).container),
                      It::deref(static_cast<It &>(it).container).end()));
        return it;
    }

    template<class FwdIt, class C>
    typename enable_if<  // Only do this if it would be exception-safe!
        is_nothrow_copy_constructible<typename C::value_type>::value &&
        is_nothrow_copy_assignable<typename C::value_type>::value,
        insert_iterator<C>
    >::type copy(
        FwdIt const &begin, FwdIt const &end,
        insert_iterator<C> output,
        forward_iterator_tag * =                  // only forward iterators
          static_cast<typename iterator_traits<FwdIt>::iterator_category *>(0))
    {
        struct It : public insert_iterator<C>
        {
            using insert_iterator<C>::container;  // protected -> public
            using insert_iterator<C>::iter;       // protected -> public
            static C &deref(C &c) { return  c; }
            static C &deref(C *c) { return *c; }
        };
        It &it(static_cast<It &>(output));
        typename C::iterator it_iter_end(It::deref(it.container).end());
        {
            // Convert iterators to offsets
            typename C::size_type const iter_end_off =
                std::distance(It::deref(it.container).begin(), it_iter_end);
            typename iterator_traits<typename C::iterator>::difference_type off
                = std::distance(It::deref(it.container).begin(), it.iter);

            // Resize container
            It::deref(it.container).resize(
                It::deref(it.container).size() +
                static_cast<typename C::size_type>(std::distance(begin, end)));
            
            // Renormalize, in case invalidated
            it.iter = It::deref(it.container).begin();
            std::advance(it.iter, off);
            it_iter_end = It::deref(it.container).begin();
            std::advance(it_iter_end, iter_end_off);
        }
        typename C::iterator result
          = copy_backward(it.iter, it_iter_end, It::deref(it.container).end());
        copy_backward(begin, end, result);
        return inserter(It::deref(it.container), result);
    }
}