在转换一个向量的元素的同时连接两个向量的最佳方法是什么？

Question

假设我有

std::vector<T1> vec1 {/* filled with T1's */};
std::vector<T2> vec2 {/* filled with T2's */};

以及一些T1 f(T2)当然可以成为lambda的功能.连接vec1和vec2应用于f每个T2中的最佳方法是什么vec2？

显而易见的解决方案是std::transform,即

vec1.reserve(vec1.size() + vec2.size());
std::transform(vec2.begin(), vec2.end(), std::back_inserter(vec1), f);

但我说这不是最佳的,因为std::back_inserter必须对每个插入的元素进行不必要的容量检查.什么是最优的是类似的东西

vec1.insert(vec1.end(), vec2.begin(), vec2.end(), f);

这可能会导致单一容量检查.遗憾的是,这不是有效的C++.本质上,这是一样的道理,为什么std::vector::insert是最佳的载体串联,看到这个问题,并在评论这对于在这一点上进一步讨论的问题.

所以:

1. 是std::transform使用STL的最佳方法是什么？
2. 如果是这样,我们可以做得更好吗？
3. 是否有充分的理由insert将上述功能排除在STL之外？

UPDATE

我已经开始验证多个容量检查是否确实有任何明显的成本.为此,我基本上只将id函数(f(x) = x)传递给答案中讨论的std::transform和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

输出:

std_insert: 44ms
push_back_id: 61ms
transform_id: 61ms

编译器将内联lambda,因此可以安全地降低成本.除非其他人对这些结果有可行的解释(或者愿意检查程序集),否则我认为可以合理地断定多次容量检查有明显的成本.

Answer 1

1. std::transform 是使用 STL 的最佳方法吗？

我不能这么说。如果您保留空间，则差异应该是短暂的，因为编译器或 CPU 可能会优化检查。找出答案的唯一方法是测量您的真实代码。
如果你没有特殊需要，你应该去std::transform。

2. 如果是这样，我们能做得更好吗？

你想拥有什么：

• 减少长度检查
• push当'n_时利用移动语义back

如果需要，您可能还想创建一个二元函数。

template <typename InputIt, typename OutputIt, typename UnaryCallable>
void move_append(InputIt first, InputIt last, OutputIt firstOut, OutputIt lastOut, UnaryCallable fn)
{
       if (std::distance(first, last) < std::distance(firstOut, lastOut)
           return;

       while (first != last && firstOut != lastOut) {
              *firstOut++ = std::move( fn(*first++) );

       }
 }

一个电话可能是：

std::vector<T1> vec1 {/* filled with T1's */};
std::vector<T2> vec2 {/* filled with T2's */};
// ...
vec1.resize( vec1.size() + vec2.size() );
move_append( vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), f );

我不确定你可以用 plain 来做到这一点，algorithm因为back_inserter会调用Container::push_back它在任何情况下都会检查重新分配。此外，该元素将无法从移动语义中受益。

注意：安全检查取决于您的使用情况，以及您如何传递要附加的元素。它还应该返回一个bool.

这里有一些测量值。我无法解释这么大的差异。