假设我有
std::vector<T1> vec1 {/* filled with T1's */};
std::vector<T2> vec2 {/* filled with T2's */};
和一些功能T1 f(T2)这当然可以是 lambda。连接的最佳方式是什么vec1 and vec2申请时f每一个T2 in vec2?
显而易见的解决方案是std::transform, i.e.
vec1.reserve(vec1.size() + vec2.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(vec1), f);
但我说这是not最优为std::back_inserter必须进行不必要的容量检查每个插入的元素。最好的办法是这样的
vec1.insert(vec1.end(), vec2.begin(), vec2.end(), f);
只需进行一次容量检查即可。遗憾的是这不是有效的 C++。本质上这就是同样的原因std::vector::insert是向量串联的最佳选择，请参阅this https://stackoverflow.com/questions/201718/concatenating-two-stl-vectors?lq=1问题和评论this https://stackoverflow.com/questions/28528626/why-does-stdvectorinsert-need-to-copy-assign/28528872?noredirect=1#comment45373435_28528872就这一点进行进一步讨论的问题。
So:
- Is
std::transform使用STL的最佳方法？
- 如果是这样，我们可以做得更好吗？
- 是否有充分的理由
insertSTL 中省略了上述函数吗？
UPDATE
我尝试验证多次容量检查是否确实有任何明显的成本。为此，我基本上只是传递 id 函数（f(x) = x）到std::transform and push_back答案中讨论的方法。完整代码是：
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstdint>
#include <chrono>
#include <numeric>
#include <random>
using std::size_t;
std::vector<int> generate_random_ints(size_t n)
{
std::default_random_engine generator;
auto seed1 = std::chrono::system_clock::now().time_since_epoch().count();
generator.seed((unsigned) seed1);
std::uniform_int_distribution<int> uniform {};
std::vector<int> v(n);
std::generate_n(v.begin(), n, [&] () { return uniform(generator); });
return v;
}
template <typename D=std::chrono::nanoseconds, typename F>
D benchmark(F f, unsigned num_tests)
{
D total {0};
for (unsigned i = 0; i < num_tests; ++i) {
auto start = std::chrono::system_clock::now();
f();
auto end = std::chrono::system_clock::now();
total += std::chrono::duration_cast<D>(end - start);
}
return D {total / num_tests};
}
template <typename T>
void std_insert(std::vector<T> vec1, const std::vector<T> &vec2)
{
vec1.insert(vec1.end(), vec2.begin(), vec2.end());
}
template <typename T1, typename T2, typename UnaryOperation>
void push_back_concat(std::vector<T1> vec1, const std::vector<T2> &vec2, UnaryOperation op)
{
vec1.reserve(vec1.size() + vec2.size());
for (const auto& x : vec2) {
vec1.push_back(op(x));
}
}
template <typename T1, typename T2, typename UnaryOperation>
void transform_concat(std::vector<T1> vec1, const std::vector<T2> &vec2, UnaryOperation op)
{
vec1.reserve(vec1.size() + vec2.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(vec1), op);
}
int main(int argc, char **argv)
{
unsigned num_tests {1000};
size_t vec1_size {10000000};
size_t vec2_size {10000000};
auto vec1 = generate_random_ints(vec1_size);
auto vec2 = generate_random_ints(vec1_size);
auto f_std_insert = [&vec1, &vec2] () {
std_insert(vec1, vec2);
};
auto f_push_back_id = [&vec1, &vec2] () {
push_back_concat(vec1, vec2, [] (int i) { return i; });
};
auto f_transform_id = [&vec1, &vec2] () {
transform_concat(vec1, vec2, [] (int i) { return i; });
};
auto std_insert_time = benchmark<std::chrono::milliseconds>(f_std_insert, num_tests).count();
auto push_back_id_time = benchmark<std::chrono::milliseconds>(f_push_back_id, num_tests).count();
auto transform_id_time = benchmark<std::chrono::milliseconds>(f_transform_id, num_tests).count();
std::cout << "std_insert: " << std_insert_time << "ms" << std::endl;
std::cout << "push_back_id: " << push_back_id_time << "ms" << std::endl;
std::cout << "transform_id: " << transform_id_time << "ms" << std::endl;
return 0;
}
编译为：
g++ vector_insert_demo.cpp -std=c++11 -O3 -o vector_insert_demo
Output:
std_insert: 44ms
push_back_id: 61ms
transform_id: 61ms
编译器将内联 lambda，这样就可以安全地降低成本。除非其他人对这些结果有可行的解释（或者愿意检查组件），否则我认为可以合理地得出多次容量检查的成本显着的结论。
