push_back 的更快替代方案（大小已知）

Question

我有一个浮点向量。当我处理某些数据时，我推送它 back.I 在声明向量时总是知道大小是多少。

最大的情况是172,490,752个浮点数。 push_back 一切都需要大约 11 秒。

是否有更快的替代方案，例如不同的数据结构或其他？

Answer 1

如果您知道最终大小，那么 reserve() 声明向量后的大小。这样它只需要分配一次内存。

此外，您可以尝试使用 emplace_back()，尽管我怀疑它会对 float 的向量产生任何影响。但是尝试一下并对其进行基准测试（当然是优化构建 - 你使用优化构建 - 对吧？）。

Answer 2

::boost::container::stable_vector 请注意，分配一个 172 *4 MB 的连续块可能很容易失败，并且需要大量的页面移动。稳定向量本质上是一个较小的向量列表或合理大小的数组。您可能还想并行填充它。

Answer 3

我有两个答案给你：

正如前面的答案所指出的，使用 reserve 预先分配存储空间会很有帮助，但是：
push_back（或emplace_back）本身有性能损失，因为在每次调用期间，它们必须检查是否必须重新分配向量。如果您已经知道要插入的元素数量，则可以通过使用访问运算符 []

所以我推荐的最有效的方法是：

用'fill'构造函数初始化向量：

std::vector<float> values(172490752, 0.0f);

直接使用访问运算符设置条目：
```
values[i] = some_float;
++i;
```

Answer 4

当您事先知道大小时，加速 vector 的常用方法是在使用 push_back 之前对其调用 reserve。这消除了每次填充前一个容量时重新分配内存和复制数据的开销。

有时对于要求非常苛刻的应用程序，这还不够。 push_back虽然不会reallocate，但是每次还是要检查capacity。如果不进行基准测试，就无法知道这有多糟糕，因为现代处理器在 always/never 采用分支时效率惊人。

您可以尝试 resize 而不是 reserve 并使用数组索引，但是 resize 强制对每个元素进行默认初始化；如果你知道你无论如何都要为每个元素设置一个新值，那就太浪费了。

另一种方法是使用 std::unique_ptr<float[]> 并自行分配存储空间。

Answer 5

之所以push_back慢是因为随着vector的增长，它需要多次复制所有数据，即使不需要复制数据也需要检查。向量增长得足够快，这种情况不会经常发生，但它仍然会发生。一个粗略的经验法则是每个元素平均需要复制一到两次；较早的元素将需要复制更多，但几乎一半的元素根本不需要复制。

您可以通过在创建向量时调用 reserve 来避免复制，但不能避免检查，确保它有足够的 space。您可以通过从一开始就以正确的大小创建它来避免复制和检查，方法是将元素的数量提供给向量构造函数，然后使用索引作为插入；不幸的是，这也需要额外的时间来初始化所有内容。

如果您在编译时知道浮点数，而不仅仅是运行时，您可以使用 std::array, which avoids all these problems. If you only know the number at runtime, I would second to go with std::unique_ptr<float[]>。您将使用

创建它

size_t size = /* Number of floats */;
auto floats = unique_ptr<float[]>{new float[size]};

您无需执行任何特殊操作即可删除它；当它超出范围时，它将释放内存。在大多数情况下，您可以像使用矢量一样使用它，但它不会自动调整大小。

Answer 6

您可以使用自定义分配器来避免所有元素的默认初始化，如 this answer 中所讨论的，结合普通元素访问：

const size_t N = 172490752;
std::vector<float, uninitialised_allocator<float> > vec(N);
for(size_t i=0; i!=N; ++i)
    vec[i] = the_value_for(i);

这避免了 (i) 默认初始化所有元素，(ii) 在每次推送时检查容量，以及 (iii) 重新分配，但同时保留了使用 std::vector 的所有便利（而不是std::unique_ptr<float[]>)。但是，allocator 模板参数不常见，因此您需要使用通用代码而不是 std::vector 特定代码。

push_back 的更快替代方案（大小已知）

Faster alternative to push_back(size is known)

c++

performance

vector

push-back