使用back_inserter()或inserter()提高std::copy()的效率

Question

使用back_inserter()或inserter()提高std::copy()的效率

c++inserter

6

back_inserter和insert_iterator非常方便，但它们也非常低效！

例如，当你添加char时，每个元素在进行copy操作时都有很多开销，而在许多情况下，实际上并不需要这样。

有没有办法使它们更有效率？

- user541686

@SteveJessop：嗯，你期望它是什么？我得到了5倍的差异。将此处与此处进行比较。 - user541686

我没有特别的期望，只是感到震惊和愤怒，因为你声称进行了优化，却没有提供基准数据；-）ideone使用哪些优化标志？在我的机器上，使用“-O3”时，你的两个程序之间的差异略微减小，但仍然是3倍。我还没有运行过使用你实际版本的“copy”的任何代码。 - Steve Jessop

@SteveJessop：FYI，我在VC++上使用我的答案也得到了60ms的结果，所以它与调用“reserve”完全相同——提高了10倍。 - user541686

嘿，我想关键在于如果有人向我销售优化服务，我想知道它是否真的是令人印象深刻的，而不仅仅是一些垃圾10%。正如你所期望的那样，在你的基准测试中，y.insert(y.end(), x.begin(), x.end()) 对我来说与快速方法表现相同。我怀疑只有当你有一个调用 copy 的通用函数并使用 insert_iterator 调用 copy 的性能时，你才会关心这个问题，因为你通常不会故意这样做。既然你的代码真正体现了两者之间的差异，那就没问题了。 - Steve Jessop

@SteveJessop：“你通常不会故意这样做”...什么？我肯定是这样做的。我调用了一个函数并传递了一个输出迭代器。它在内部调用了std::copy。这大概是我能想象到的最“正常”的代码了。 - user541686

显示剩余14条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user541686 · Accepted Answer

是的，您可以定义一个新版本的std::copy，它可以劫持可优化的调用。 :)

以下是Visual C++和GCC的示例（或者如果您更喜欢看到半杯空的杯子，则为“hack”）。

在我的个人电脑上（我使用VC++ 2010），下面的代码使调用快了十倍！
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);
    }
}