哪个更好：保留向量容量、预分配大小或在循环中推回？
What is better: reserve vector capacity, preallocate to size or push back in loop?
我有一个函数将指向 char 数组和段大小的指针作为输入参数，并调用另一个需要 std::array<std::string> 的函数。思路是将输入的char数组"sectioned"等分，组成string数组
输入字符数组格式是几个确定大小的较小数组（或字符串）连接在一起。这些不是假定的零终止，尽管它们可能是。段大小 5 和元素数 10 的示例：
char k[] = "1234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]0";
char m[] = "1234[=10=]067890987654321[=10=]0234567809876[=10=]05432[=10=]0[=10=]0[=10=]03456789098";
char n[] = "12345678909876543211234567890987654321123456789098";
所有char数组的长度为51（段*元素+1）。我的目标是使函数有效地使用资源，最重要的是执行时间。
因为给猫剥皮的方法有很多种，我有两种（或三种）方法来解决这个问题，问题是，哪种是"better"？我的意思是更快，更少的资源浪费。我不是专业人士，请耐心等待。
这里，values是预分配的，然后每个字符串赋值。
void myfnc_1(void *a_src, uint32_t a_segment) {
// a_segment = 5 for example
size_t nSize = GetSize(); // another method, gets 10
std::vector<std::string> values(nSize);
char* v = a_src; // take k, n or m for example
for (size_t i = 0; i < nSize; ++i) {
values.at(i).assign(v, a_segment);
v += a_segment;
}
}
这里没有分配向量，但是每次迭代都会添加一个新的字符串。
void myfnc_1(void *a_src, uint32_t a_segment) {
size_t nSize = GetSize();
std::vector<std::string> values();
char* v = a_src;
for (size_t i = 0; i < nSize; ++i) {
values.push_back("");
values.back().assign(v, a_segment);
v += a_segment;
}
}
可能还有第三种方法，那更好。我对矢量不是很有经验，所以我不太清楚。如果段长度和元素数量通常较大 (5, 10) 或较小 (100, 10000)，它们是否会有所不同？
第一个post，大粉丝:)
做任何更容易阅读和维护的事情。通常，它是最快的解决方案。
即使它不是最快的，谁在乎呢？也许您的应用会慢 1%。
避免动态重新分配会达到更好的性能，因此请尝试让向量内存足够大以容纳所有元素。
您的第一个解决方案会更有效，因为如果 nSize 大于默认向量容量，则第二个解决方案将需要重新分配才能存储所有元素。
正如 Melkon 所说，reserve 更好：
void myfnc_1(void *a_src, uint32_t a_segment) {
size_t nSize = GetSize();
std::vector<std::string> values;
values.reserve( nSize );
char* v = a_src;
for (size_t i = 0; i < nSize; ++i) {
values.push_back( std::string( v, a_segment ) );
v += a_segment;
}
}
Do not use parentheses to invoke the default constructor.
push_back 每次超出容量时都需要额外的重新分配。因此，可以通过保留足够的 space 来避免重新分配来改进选项 2。直接压入字符串也比压入一个空字符串然后再重新分配更有效。 std::string 有一个构造函数，非常适合您的需求：from sequence (5)
string (const char* s, size_t n);
关于选项 1：预分配整个向量需要构造每个元素一次以进行初始化，再构造一次以进行赋值。最好保留而不构建元素，直接 push_back 你真正想要的。
这是使用这些改进的代码：
void myfnc_1(void *a_src, uint32_t a_segment)
{
std::vector<std::string> values;
size_t nSize = GetSize( );
values.reserve(nSize);
char* v = static_cast<char*> ( a_src );
for (size_t i = 0; i < nSize; ++i)
{
values.push_back( std::string( v, a_segment) );
v += a_segment;
}
}
向向量添加元素
有几种方法可以将数据添加到向量中：
- 创建一个空向量，
push_back() 个元素放入其中。
- 创建一个空向量，用
reserve() 分配一些容量，然后将 push_back() 个元素放入其中。
- 创建一个包含
n 个元素的向量，使用索引和复制赋值。
- 创建一个空向量，
emplace_back() 个元素放入其中。
- 创建一个空向量，用
reserve() 分配一些容量，然后将 emplace_back() 个元素放入其中。
还有其他方法，例如使用一对迭代器创建容器，或通过标准库算法填充它。我不会在这里考虑这些。
一般注意事项
以下两个注意事项对于以下分析很重要：
- 避免（重新）分配： 内存分配很慢。重新分配通常涉及将容器中已有的所有内容复制到新位置。
- 避免不必要的工作：构造你想要的元素比默认构造然后赋值更好。最好在你想要的地方构造一个元素，而不是在其他地方构造它，然后复制。
其他因素也会影响所选解决方案的效率，但这些都是我们可以直接控制的重要因素。通过分析您的代码，其他因素可能会变得明显。
push_back()
每个 push_back() 从参数到 push_back() 调用复制构建向量中的一个元素。如果向量 size() == capacity()，将执行重新分配。这通常（但可能不总是）使容量翻倍，并可能导致将 所有 现有元素复制到新存储中。
push_back() 预分配
使用reserve() 在我们开始之前为元素分配足够的内存。如果您知道（或有一个合理的猜测）元素的数量，那么这样做总是值得的。如果你在猜测，高估总比低估好。
push_back() 调用仍将使用元素类型的复制构造函数，但不应该有任何分配，因为已经提供了 space。您只需在 reserve() 调用期间支付单次分配的费用。如果您对现有容量执行 运行，push_back() 将重新分配，通常会使容量翻倍。这就是为什么高估尺寸更好；您不太可能获得重新分配，而如果低估，您不仅可能会重新分配，而且您将浪费内存分配几乎是您需要的两倍！
请注意，"doubling capacity" 行为未由标准指定，但它是一种常见的实现，旨在减少使用 push_back() 未知大小的数据集时的重新分配频率。
索引和元素赋值
在这里，我们创建了一个由正确数量的默认构造元素组成的向量，然后使用复制赋值运算符将它们替换为我们想要的元素。这只有一个分配，但如果复制分配做任何复杂的事情可能会很慢。这对于未知（或仅猜测）大小的数据集并不适用；仅当您知道索引永远不会超过 size() 时，元素索引才是安全的，如果您需要更多，则必须求助于 push_back() 或调整大小。这不是一个好的通用解决方案，但有时它可以工作。
emplace_back()
emplace_back() 使用 emplace_back() 调用的参数就地构造元素。这通常比等效的 push_back() 更快（但并非总是如此）。它仍然以与 push_back() 相同的模式分配，保留一些容量，填充它，然后在需要更多时重新分配。许多相同的论点都适用，但您可以从构造方法中获得一些收益。
emplace_back() 预分配
这应该是 C++11 或更高版本代码库的首选策略。您获得 emplace_back() 效率（如果可能）并避免重复分配。在列出的机制中，这在大多数情况下预计是最快的。
关于效率的说明
效率可以通过多种方式衡量。执行时间是一种常见的衡量标准，但并不总是最相关的。关于使用哪种策略的一般建议是基于经验和本质上 "averages" 各种效果，以提供一些关于首先做什么的合理陈述。与往常一样，如果任何类型的效率对您的应用程序至关重要，那么确保优化正确位置的唯一方法是 分析 您的代码，进行更改，然后 profile 再次证明更改已达到预期效果。不同的数据类型、硬件、I/O 要求等都会影响这种时序，在您 profile 之前，您永远不会知道这些影响如何结合到您的特定应用程序中.
例子
实例：http://coliru.stacked-crooked.com/a/83d23c2d0dcee2ff
在这个例子中，我使用上面列出的每种方法用 10,000 个字符串填充一个向量。我对每一个计时并打印结果。
这与您的问题类似，但不完全相同；你的结果会有所不同！
注意 emplace_back() 和 reserve() 是最快的，但是这里的索引和赋值也很快。这可能是因为 std::string 有一个高效的 swap()，并且它的默认构造函数没有做太多事情。其他方法要慢一个数量级。
#include <chrono>
#include <iostream>
#include <vector>
using Clock = std::chrono::high_resolution_clock;
using time_point = std::chrono::time_point<Clock>;
std::vector<std::string> strings = {"one", "two", "three", "four", "five"};
std::chrono::duration<double> vector_push_back(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
for (size_t i = 0; i < n; ++i) {
v.push_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_push_back_with_reserve(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i) {
v.push_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_element_assignment(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v(n);
for (size_t i = 0; i < n; ++i) {
v[i] = strings[i % strings.size()];
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_emplace_back(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
for (size_t i = 0; i < n; ++i) {
v.emplace_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_emplace_back_with_reserve(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i) {
v.emplace_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
int main() {
const size_t n = 10000;
std::cout << "vector push_back: " << vector_push_back(n).count() << "\n";
std::cout << "vector push_back with reserve: " << vector_push_back(n).count() << "\n";
std::cout << "vector element assignment: " << vector_element_assignment(n).count() << "\n";
std::cout << "vector emplace_back: " << vector_emplace_back(n).count() << "\n";
std::cout << "vector emplace_back with reserve: " << vector_emplace_back_with_reserve(n).count() << "\n";
}
结果：
vector push_back: 0.00205563
vector push_back with reserve: 0.00152464
vector element assignment: 0.000610934
vector emplace_back: 0.00125141
vector emplace_back with reserve: 0.000545451
结论
对于大多数新代码，使用 reserve() 和 emplace_back()（或对旧代码使用 push_back()）应该会给您一个很好的效率近似值。如果还不够，分析它并找出瓶颈在哪里。它可能不会像你想象的那样。
我有一个函数将指向 char 数组和段大小的指针作为输入参数，并调用另一个需要 std::array<std::string> 的函数。思路是将输入的char数组"sectioned"等分，组成string数组
输入字符数组格式是几个确定大小的较小数组（或字符串）连接在一起。这些不是假定的零终止，尽管它们可能是。段大小 5 和元素数 10 的示例：
char k[] = "1234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]01234[=10=]0";
char m[] = "1234[=10=]067890987654321[=10=]0234567809876[=10=]05432[=10=]0[=10=]0[=10=]03456789098";
char n[] = "12345678909876543211234567890987654321123456789098";
所有char数组的长度为51（段*元素+1）。我的目标是使函数有效地使用资源，最重要的是执行时间。
因为给猫剥皮的方法有很多种，我有两种（或三种）方法来解决这个问题，问题是，哪种是"better"？我的意思是更快，更少的资源浪费。我不是专业人士，请耐心等待。
这里，values是预分配的，然后每个字符串赋值。
void myfnc_1(void *a_src, uint32_t a_segment) {
// a_segment = 5 for example
size_t nSize = GetSize(); // another method, gets 10
std::vector<std::string> values(nSize);
char* v = a_src; // take k, n or m for example
for (size_t i = 0; i < nSize; ++i) {
values.at(i).assign(v, a_segment);
v += a_segment;
}
}
这里没有分配向量，但是每次迭代都会添加一个新的字符串。
void myfnc_1(void *a_src, uint32_t a_segment) {
size_t nSize = GetSize();
std::vector<std::string> values();
char* v = a_src;
for (size_t i = 0; i < nSize; ++i) {
values.push_back("");
values.back().assign(v, a_segment);
v += a_segment;
}
}
可能还有第三种方法，那更好。我对矢量不是很有经验，所以我不太清楚。如果段长度和元素数量通常较大 (5, 10) 或较小 (100, 10000)，它们是否会有所不同？
第一个post，大粉丝:)
做任何更容易阅读和维护的事情。通常，它是最快的解决方案。
即使它不是最快的，谁在乎呢？也许您的应用会慢 1%。
避免动态重新分配会达到更好的性能，因此请尝试让向量内存足够大以容纳所有元素。
您的第一个解决方案会更有效，因为如果 nSize 大于默认向量容量，则第二个解决方案将需要重新分配才能存储所有元素。
正如 Melkon 所说，reserve 更好：
void myfnc_1(void *a_src, uint32_t a_segment) {
size_t nSize = GetSize();
std::vector<std::string> values;
values.reserve( nSize );
char* v = a_src;
for (size_t i = 0; i < nSize; ++i) {
values.push_back( std::string( v, a_segment ) );
v += a_segment;
}
}
Do not use parentheses to invoke the default constructor.
push_back 每次超出容量时都需要额外的重新分配。因此，可以通过保留足够的 space 来避免重新分配来改进选项 2。直接压入字符串也比压入一个空字符串然后再重新分配更有效。 std::string 有一个构造函数，非常适合您的需求：from sequence (5)
string (const char* s, size_t n);
关于选项 1：预分配整个向量需要构造每个元素一次以进行初始化，再构造一次以进行赋值。最好保留而不构建元素，直接 push_back 你真正想要的。
这是使用这些改进的代码：
void myfnc_1(void *a_src, uint32_t a_segment)
{
std::vector<std::string> values;
size_t nSize = GetSize( );
values.reserve(nSize);
char* v = static_cast<char*> ( a_src );
for (size_t i = 0; i < nSize; ++i)
{
values.push_back( std::string( v, a_segment) );
v += a_segment;
}
}
向向量添加元素
有几种方法可以将数据添加到向量中：
- 创建一个空向量，
push_back()个元素放入其中。 - 创建一个空向量，用
reserve()分配一些容量，然后将push_back()个元素放入其中。 - 创建一个包含
n个元素的向量，使用索引和复制赋值。 - 创建一个空向量，
emplace_back()个元素放入其中。 - 创建一个空向量，用
reserve()分配一些容量，然后将emplace_back()个元素放入其中。
还有其他方法，例如使用一对迭代器创建容器，或通过标准库算法填充它。我不会在这里考虑这些。
一般注意事项
以下两个注意事项对于以下分析很重要：
- 避免（重新）分配： 内存分配很慢。重新分配通常涉及将容器中已有的所有内容复制到新位置。
- 避免不必要的工作：构造你想要的元素比默认构造然后赋值更好。最好在你想要的地方构造一个元素，而不是在其他地方构造它，然后复制。
其他因素也会影响所选解决方案的效率，但这些都是我们可以直接控制的重要因素。通过分析您的代码，其他因素可能会变得明显。
push_back()
每个 push_back() 从参数到 push_back() 调用复制构建向量中的一个元素。如果向量 size() == capacity()，将执行重新分配。这通常（但可能不总是）使容量翻倍，并可能导致将 所有 现有元素复制到新存储中。
push_back() 预分配
使用reserve() 在我们开始之前为元素分配足够的内存。如果您知道（或有一个合理的猜测）元素的数量，那么这样做总是值得的。如果你在猜测，高估总比低估好。
push_back() 调用仍将使用元素类型的复制构造函数，但不应该有任何分配，因为已经提供了 space。您只需在 reserve() 调用期间支付单次分配的费用。如果您对现有容量执行 运行，push_back() 将重新分配，通常会使容量翻倍。这就是为什么高估尺寸更好；您不太可能获得重新分配，而如果低估，您不仅可能会重新分配，而且您将浪费内存分配几乎是您需要的两倍！
请注意，"doubling capacity" 行为未由标准指定，但它是一种常见的实现，旨在减少使用 push_back() 未知大小的数据集时的重新分配频率。
索引和元素赋值
在这里，我们创建了一个由正确数量的默认构造元素组成的向量，然后使用复制赋值运算符将它们替换为我们想要的元素。这只有一个分配，但如果复制分配做任何复杂的事情可能会很慢。这对于未知（或仅猜测）大小的数据集并不适用；仅当您知道索引永远不会超过 size() 时，元素索引才是安全的，如果您需要更多，则必须求助于 push_back() 或调整大小。这不是一个好的通用解决方案，但有时它可以工作。
emplace_back()
emplace_back() 使用 emplace_back() 调用的参数就地构造元素。这通常比等效的 push_back() 更快（但并非总是如此）。它仍然以与 push_back() 相同的模式分配，保留一些容量，填充它，然后在需要更多时重新分配。许多相同的论点都适用，但您可以从构造方法中获得一些收益。
emplace_back() 预分配
这应该是 C++11 或更高版本代码库的首选策略。您获得 emplace_back() 效率（如果可能）并避免重复分配。在列出的机制中，这在大多数情况下预计是最快的。
关于效率的说明
效率可以通过多种方式衡量。执行时间是一种常见的衡量标准，但并不总是最相关的。关于使用哪种策略的一般建议是基于经验和本质上 "averages" 各种效果，以提供一些关于首先做什么的合理陈述。与往常一样，如果任何类型的效率对您的应用程序至关重要，那么确保优化正确位置的唯一方法是 分析 您的代码，进行更改，然后 profile 再次证明更改已达到预期效果。不同的数据类型、硬件、I/O 要求等都会影响这种时序，在您 profile 之前，您永远不会知道这些影响如何结合到您的特定应用程序中.
例子
实例：http://coliru.stacked-crooked.com/a/83d23c2d0dcee2ff
在这个例子中，我使用上面列出的每种方法用 10,000 个字符串填充一个向量。我对每一个计时并打印结果。
这与您的问题类似，但不完全相同；你的结果会有所不同！
注意 emplace_back() 和 reserve() 是最快的，但是这里的索引和赋值也很快。这可能是因为 std::string 有一个高效的 swap()，并且它的默认构造函数没有做太多事情。其他方法要慢一个数量级。
#include <chrono>
#include <iostream>
#include <vector>
using Clock = std::chrono::high_resolution_clock;
using time_point = std::chrono::time_point<Clock>;
std::vector<std::string> strings = {"one", "two", "three", "four", "five"};
std::chrono::duration<double> vector_push_back(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
for (size_t i = 0; i < n; ++i) {
v.push_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_push_back_with_reserve(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i) {
v.push_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_element_assignment(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v(n);
for (size_t i = 0; i < n; ++i) {
v[i] = strings[i % strings.size()];
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_emplace_back(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
for (size_t i = 0; i < n; ++i) {
v.emplace_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
std::chrono::duration<double> vector_emplace_back_with_reserve(const size_t n) {
time_point start, end;
start = Clock::now();
std::vector<std::string> v;
v.reserve(n);
for (size_t i = 0; i < n; ++i) {
v.emplace_back(strings[i % strings.size()]);
}
end = Clock::now();
return end - start;
}
int main() {
const size_t n = 10000;
std::cout << "vector push_back: " << vector_push_back(n).count() << "\n";
std::cout << "vector push_back with reserve: " << vector_push_back(n).count() << "\n";
std::cout << "vector element assignment: " << vector_element_assignment(n).count() << "\n";
std::cout << "vector emplace_back: " << vector_emplace_back(n).count() << "\n";
std::cout << "vector emplace_back with reserve: " << vector_emplace_back_with_reserve(n).count() << "\n";
}
结果：
vector push_back: 0.00205563
vector push_back with reserve: 0.00152464
vector element assignment: 0.000610934
vector emplace_back: 0.00125141
vector emplace_back with reserve: 0.000545451
结论
对于大多数新代码，使用 reserve() 和 emplace_back()（或对旧代码使用 push_back()）应该会给您一个很好的效率近似值。如果还不够，分析它并找出瓶颈在哪里。它可能不会像你想象的那样。