将一个 std::vector 附加到另一个 std::vector 的末尾的最有效方法是什么？

问题描述 投票：0回答：6

设v1为目标向量，v2需要附加到其后面。

我现在正在做：

v1.reserve(v1.size() + v2.size()); 
copy(v2.begin(), v2.end(), back_inserter(v1));

这是最有效的方法吗？或者可以通过复制一块内存来完成吗？ 谢谢！

c++ performance stl vector
6个回答
92
投票

经过多次争论（以及 Matthieu M. 和 villintehaspam 的合理评论），我将更改我的建议为

v1.insert( v1.end(), v2.begin(), v2.end() );

我将保留之前的建议：

v1.reserve( v1.size() + v2.size() ); 
v1.insert( v1.end(), v2.begin(), v2.end() );

采用后一种方式是有一些理由的，尽管这些理由都不够充分：

  • 无法保证向量将被重新分配到什么大小——例如如果总大小为 1025，则可能会重新分配到 2048——具体取决于实现。对于 
    reserve
    也没有这样的保证，但对于特定的实现来说它可能是正确的。如果寻找瓶颈，检查一下可能是合理的。
  • reserve 清楚地表明了我们的意图——在这种情况下优化可能会更有效（reserve 可以在某些顶级实现中准备缓存）。
  • 此外，使用 
    reserve
    ，我们有一个 C++ 标准保证，只会进行一次重新分配，而 
    insert
    可能实现效率低下，并进行多次重新分配（也可以使用特定实现进行测试）。
30
投票

我只是使用以下代码进行了快速性能测量，并且

v1.insert( v1.end(), v2.begin(), v2.end() );

似乎是正确的选择（如上所述）。 尽管如此，您还是会发现下面报告的性能。

测试代码：

#include <vector>
#include <string>

#include <boost/timer/timer.hpp>

//==============================================================================
// 
//==============================================================================

/// Returns a vector containing the sequence [ 0, ... , n-1 ].
inline std::vector<int> _range(const int n)
{
    std::vector<int> tmp(n);
    for(int i=0; i<n; i++)
        tmp[i] = i;
    return tmp;
}

void test_perf_vector_append()
{
    const vector<int> testdata1 = _range(100000000);
    const vector<int> testdata2 = _range(100000000);

    vector<int> testdata;

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  push_back()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;
        for(size_t i=0; i<testdata2.size(); i++)
        {
            testdata.push_back(testdata2[i]);
        }
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + push_back()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;
        testdata.reserve(testdata.size() + testdata2.size());
        for(size_t i=0; i<testdata2.size(); i++)
        {
            testdata.push_back(testdata2[i]);
        }
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  insert()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.insert( testdata.end(), testdata2.begin(), testdata2.end() );
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + insert()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve( testdata.size() + testdata.size() ); 
        testdata.insert( testdata.end(), testdata2.begin(), testdata2.end() );
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  copy() + back_inserter()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve(testdata.size() + testdata2.size()); 
        copy(testdata2.begin(), testdata2.end(), back_inserter(testdata));
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + copy() + back_inserter()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve(testdata.size() + testdata2.size()); 
        copy(testdata2.begin(), testdata2.end(), back_inserter(testdata));
    }

}

使用 Visual Studio 2008 SP1、x64、Release 模式、/O2 /LTCG 输出如下：

--------------------------------------------------------------
 METHOD:  push_back()
--------------------------------------------------------------
 0.933077s wall, 0.577204s user + 0.343202s system = 0.920406s CPU (98.6%)

--------------------------------------------------------------
 METHOD:  reserve() + push_back()
--------------------------------------------------------------
 0.612753s wall, 0.452403s user + 0.171601s system = 0.624004s CPU (101.8%)

--------------------------------------------------------------
 METHOD:  insert()
--------------------------------------------------------------
 0.424065s wall, 0.280802s user + 0.140401s system = 0.421203s CPU (99.3%)

--------------------------------------------------------------
 METHOD:  reserve() + insert()
--------------------------------------------------------------
 0.637081s wall, 0.421203s user + 0.218401s system = 0.639604s CPU (100.4%)

--------------------------------------------------------------
 METHOD:  copy() + back_inserter()
--------------------------------------------------------------
 0.743658s wall, 0.639604s user + 0.109201s system = 0.748805s CPU (100.7%)

--------------------------------------------------------------
 METHOD:  reserve() + copy() + back_inserter()
--------------------------------------------------------------
 0.748560s wall, 0.624004s user + 0.124801s system = 0.748805s CPU (100.0%)
26
投票

使用专用方法可能更好、更简单：vector.insert

v1.insert(v1.end(), v2.begin(), v2.end());

正如 Michael 提到的，除非迭代器是输入迭代器，否则向量将计算出所需的大小并以线性复杂度一次性复制附加数据。

7
投票

如果您碰巧使用 Boost，您可以从 Boost Vault 下载 RangeEx 库的开发版本。这个库。不久前已被 Boost 接受，但到目前为止它尚未与主要发行版集成。在其中，您会发现一种新的基于范围的算法，它完全可以满足您的需求：

boost::push_back(v1, v2);
在内部它的工作方式类似于UncleBens给出的答案，但代码更简洁和可读。

3
投票
如果你有一个 pod 类型的向量，并且你确实需要性能，你可以使用 memcpy，它应该比 vector<>.insert(...) 更快：

v2.resize(v1.size() + v2.size()); memcpy((void*)&v1.front(), (void*)&v2[v1.size()], sizeof(v1.front())*v1.size());
更新： 虽然我只会在确实需要性能时才使用它，但代码对于 Pod 类型来说是安全的。

我知道 - 这是复活一个旧线程 - 但这是第一个搜索结果，所以我想更新答案。

对于 C++23，有一个更简单的解决方案：使用
0
投票
v1.append_range(v2);

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.