c++ - back_inserter() または inserter() による std::copy() の効率の改善

Question

back_inserter非常にinsert_iterator便利ですが、非常に非効率的でもあります!

たとえば、s を追加する場合、多くの場合、実際にはその必要がないchar場合でも、すべての要素に大量のオーバーヘッドが発生します。copy

それらをより効率的にする方法はありますか？

Answer 1

はい、std::copy最適化可能な呼び出しをハイジャックできる新しいバージョンを定義できます。:)

以下は、Visual C++ と GCC の例です (ガラスが半分空になっているのが好きな場合は「ハック」)。

私のパーソナル コンピューター (VC++ 2010 を使用) では、以下のコードを使用すると、呼び出しが10 倍速くなります。
GCC のベンチマークもここにあり、5 倍の違いを示しています:古いバージョンと新しいバージョン

ただし、使用する前に：

このコードは、コンテナが のvectorようなインターフェースを提供していると想定していることに注意してください。

現在書かれているように、これは C++11 でのみ機能します。これは、type_traitsヘッダーのメタプログラミング機能を使用して、コピー操作が例外セーフのままである状況のみを最適化するためです。

例外の安全性が必要ない場合 (ただし、実際にこれを行う前によく考える必要があります)、またはそのようなデータ型をチェックする別の方法がある場合は、変更できます。

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

に：

insert_iterator<C>

残りのコードは C++03 でも機能するはずです。

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