c++ - 初始化 C++ vector 的大小

Question

初始化 C++ vector 和其他容器的大小有什么优点(如果有的话)？有什么理由不只使用默认的无参数构造函数吗？

基本上，两者之间是否存在显着的性能差异

vector<Entry> phone_book;

和

vector<Entry> phone_book(1000);

这些示例来自 Bjarne Stroustrup 的 The C++ Programming Language Third Edition。如果这些容器应该总是用一个大小来初始化，有没有一个好方法来确定一个好的开始大小是多少？

Answer 1

有几种方法可以创建 vector与 n元素，当您事先不知道元素的数量时，我什至会展示一些填充 vector 的方法。
但首先
什么不该做

std::vector<Entry> phone_book;
for (std::size_t i = 0; i < n; ++i)
{
    phone_book[i] = entry; // <-- !! Undefined Behaviour !!
}

默认构造的 vector ，如上例所示，创建一个空 vector 。访问 vector 范围之外的元素是未定义行为。并且不要期望得到一个很好的异常(exception)。未定义的行为意味着任何事情都可能发生:程序可能会崩溃，或者看起来可以工作，或者可能以一种不稳定的方式工作。请注意使用 reserve不会改变 vector 的实际大小，即你不能访问 vector 大小之外的元素，即使你为它们保留。
现在分析了一些选项
默认构造函数 + push_back (次优)

std::vector<Entry> phone_book;
for (std::size_t i = 0; i < n; ++i)
{
    phone_book.push_back(entry);
}

这有一个缺点，即在您推回元素时会发生重新分配。这意味着内存分配、元素移动(或复制，如果它们不可移动，或对于 pre c++11)和内存释放(带有对象销毁)。对于 n，这很可能会发生不止一次。相当大。值得注意的是，它保证了 push_back的“摊销常数”。这意味着它不会在每个 push_back 之后进行重新分配.每次重新分配都会以几何方式增加大小。进一步阅读: std::vector and std::string reallocation strategy
当您事先不知道尺寸并且您甚至没有估计尺寸时，请使用此选项。
“计数默认插入的 T 实例” ctor 稍后分配(不推荐)

std::vector<Entry> phone_book(n);
for (auto& elem : phone_book)
{
    elem = entry;
}

这不会导致任何重新分配，而是所有 n元素最初将被默认构造，然后在每次推送时复制。这是一个很大的缺点，对性能的影响很可能是可以衡量的。 (这对于基本类型不太明显)。
不要使用它，因为几乎每种情况都有更好的替代方案。
“计算元素的拷贝数”ctor(推荐)

std::vector<Entry> phone_book(n, entry);

这是最好的使用方法。当您在构造函数中提供所需的所有信息时，它将进行最有效的分配 + 赋值。这有可能导致无分支代码，如果 Entry 带有用于赋值的矢量化指令有一个简单的复制构造函数。
默认构造函数 + reserve + push_back (情景推荐)

vector<Entry> phone_book;
phone_book.reserve(m);

while (some_condition)
{
     phone_book.push_back(entry);
}

// optional
phone_book.shrink_to_fit();

不会发生重新分配，并且对象只会构造一次，直到超出保留容量。 push_back的更好选择可以 emplace_back .
如果您对尺寸有一个粗略的估计，请使用它。
储备值(value)没有神奇的公式。针对您的特定场景使用不同的值进行测试，以获得应用程序的最佳性能。最后你可以使用 shrink_to_fit .
默认构造函数 + std::fill_n和 std::back_inserter (情景推荐)

#include <algorithm>
#include <iterator>

std::vector<Entry> phone_book;

// at a later time
// phone_book could be non-empty at this time
std::fill_n(std::back_inserter(phone_book), n, entry);

如果您需要在创建后向 vector 填充或添加元素，请使用此选项。
默认构造函数 + std::generate_n和 std::back_inserter (对于不同的 entry 对象)

Entry entry_generator();

std::vector<Entry> phone_book;
std::generate_n(std::back_inserter(phone_book), n, [] { return entry_generator(); });

如果每个 entry，您都可以使用它是不同的并且从生成器获得
初始化列表(奖励)
由于这已经成为一个如此重要的答案，除了所问的问题之外，如果我没有提到初始化列表构造函数，我将被解雇:

std::vector<Entry> phone_book{entry0, entry1, entry2, entry3};

在大多数情况下，当您有一小部分用于填充 vector 的初始值时，这应该是默认的首选构造函数。

一些资源:
std::vector::vector (constructor)
std::vector::insert
standard algorithm library (与 std::generate std::generate_n std::fill std::fill_n 等)
std::back_inserter