c++ - boost::container::vector 比 std::vector 快吗？为什么？

Question

我对 boost vector 和 std vector 做了一个有趣的测试如下

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

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

f boost vector :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%)

boost :5.585048s 墙，5.584836s 用户 + 0.000000s 系统 = 5.584836s CPU (100.0%)

将 reserve(N) 添加到两者时，CPU 时间变化很小。

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

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

Answer 1

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

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

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

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

cplusplus.com on std::vector

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity (see push_back).

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

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

All containers offered by Boost.Container implement placement insertion, which means that objects can be built directly into the container from user arguments without creating any temporary object. For compilers without variadic templates support placement insertion is emulated up to a finite (10) number of arguments.

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