5

我对 boost 向量和 std 向量做了一个有趣的测试，如下所示

int N = 10000;
{
    boost::timer::auto_cpu_timer t;
    std::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

{
    boost::timer::auto_cpu_timer t;
    boost::container::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

win32发布，vc2010编译，/O2 /Oy-

对于 N = 10000

对于标准向量：0.140849s 墙，0.140401s 用户 + 0.000000s 系统 = 0.140401s CPU (99.7%)

f 提升向量：0.056174s 墙，0.062400s 用户 + 0.000000s 系统 = 0.062400s CPU (111.1%)

对于 N = 100,000

标准：14.050757s 墙，14.055690s 用户 + 0.000000s 系统 = 14.055690s CPU (100.0%)

提升：5.585048s 墙，5.584836s 用户 + 0.000000s 系统 = 5.584836s CPU (100.0%)

将 Reserve(N) 添加到两者时，CPU 时间几乎没有变化。

他们之间有什么区别吗？Boost比std快得多，为什么？谢谢。

检查 sizeof()，std::vector 16，而 boost::container::vector 12。

4

2 回答 2

6

请记住，所有代码的速度会因编译器和编译器版本而异。标准库提供的代码可以在平台之间移植，但很难保证速度。

如果您只是在自己的机器上运行此代码，那么您应该选择更快的选项，如果这是您想要的。如果你问这个问题是因为你想做出一个普遍更快的选择，那么我认为没有办法知道测试它的不足之处。

自然地，当一个人以一般的方式想知道速度时，就像你看起来的那样，你会想要评估插入许多不同数量的对象，运行许多重复测试，并使用各种对象（类，双打，字符等）。您也可以选择使用不同数量的可用堆栈空间来完成所有这些操作。如果您不考虑所有因素，那么默认情况下您的问题会变成“为什么在我的特定情况下会存在速度差异？” 通常很难说。

一个更好的问题可能是，“我在各种测试条件下观察到这两个功能相似的代码之间的速度差异。它们之间是否存在一些架构差异可以解释这一点？” 答案是也许。

cplusplus.com 在 std::vector 上

在内部，向量使用动态分配的数组来存储它们的元素。当插入新元素时，可能需要重新分配该数组以增加大小，这意味着分配一个新数组并将所有元素移至该数组。就处理时间而言，这是一项相对昂贵的任务，因此，向量不会在每次将元素添加到容器时重新分配。

相反，向量容器可能会分配一些额外的存储空间以适应可能的增长，因此容器的实际容量可能大于包含其元素所严格需要的存储空间（即其大小）。库可以实施不同的增长策略来平衡内存使用和重新分配，但无论如何，重新分配应该只发生在对数增长的大小间隔上，以便可以为向量末尾的单个元素插入提供摊销常数时间复杂性（参见 push_back）。

从这里我们看到，您看到的行为取决于您使用的特定版本的 STL 库，并且增长应该是对数的，并且增长通常需要大量复制。双端队列不需要大量复制，因此它可以在您的测试中更好地扩展。

据推测，boost::container功能类似。我不知道，因为我找不到关于它的文章。但我确实找到了这个：

Boost.Container 提供的所有容器都实现了放置插入，这意味着可以从用户参数直接将对象构建到容器中，而无需创建任何临时对象。对于不支持可变参数模板的编译器，最多可以模拟有限 (10) 个参数的位置插入。

如果 std::vector 不使用类似的架构而是创建一个临时对象，这可能会导致运行时的差异。但这可能不适用于int类型。也许其他人可以找到不同的架构差异。

于 2013-01-02T20:08:32.853 回答
0

boost::container 中的容器类大量使用了扩展分配器，它们不仅允许分配和解除分配、构造和解构，而且如果可能的话还可以扩展分配的内存块。这意味着在许多情况下复制更少，并且本质上与您在 c 中可以做的 c++ 等效：

char * data;
char * newdata = malloc(newdatasize);
memcpy(newdata,data,datasize);
swap(data,newdata);
free(newdata);

https://www.boost.org/doc/libs/1_68_0/doc/html/container/extended_allocators.html 当插入 int 时，没有任何“放置插入”优化是相关的，因为 int 的构造很简单。

于 2018-10-26T23:36:20.697 回答