重复 std::vector 的内容

Question

假设我有一个普通类型的向量（可能很大），例如

std::vector<int> v{1,2,3};

重复n次最好的方法是什么？

例如3 次会给出结果 {1,2,3,1,2,3,1,2,3}

当然，这是一个经常出现的问题（数值库通常内置这样的函数）。我天真的解决方案：

template<typename T>
std::vector<T> repeat(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result;
    auto input_size = input.size();
    result.reserve(input_size * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        for (std::size_t i = 0; i < input_size; ++i) {
            result.push_back(input[i % input_size]);
        }
    }
    return result;
}

当然可以让它更快吗？也许 std::copy？然而，在那种情况下，我不确定如何在避免零初始化的同时告诉向量它的新大小。显然这不容易完成（参见，例如，1）。我也尝试用迭代器来做，但它似乎并没有更快。

Answer 1

我会立即调整向量的大小以避免任何中间重新分配。然后，您可以使用 std::copy 和一些算法将 input 向量复制到 result 中，使用特定的偏移量到该预分配向量中。

template<typename T>
std::vector<T> repeat(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        std::copy(input.begin(), input.end(), std::next(result.begin(), rep * input.size()));
    }
    return result;
}

Answer 2

使用 range-v3 你可以这样写：

#include <range/v3/all.hpp>
namespace rv = ranges::views;

template<typename T>
auto repeat(const std::vector<T> &input, unsigned int times) 
{
    return rv::repeat_n(input, times) 
           | rv::join 
           | ranges::to<std::vector<T>>;
}

这里是 demo。

我怀疑这将有足够好的性能满足您的需求。

Answer 3

这最初是对问题的编辑。用户 cigien 建议 post 它作为答案。这包含一些不完整的（即，尚未探索实施解决方案的所有可能性）分析结果。

我做了一些分析代码（我绝不是分析专家）比较我的版本和 Cory Kramer 的答案中的版本。答案中的代码似乎比我的代码快 4.5 倍（在 quick-bench.com 使用 GCCv10.1、C++17、O3 优化进行测试）。 Remy Lebeau 关于保存迭代器临时值的建议似乎没有任何区别。

在问自己之前我错过了重复的问题： and 2。这些中的一些答案提出了更多我尚未介绍的略有不同的解决方案。

range-v3 库（由 cigien 回答）虽然看起来很方便，但不是我可以使用的选项，我也没有对它进行概要分析。

分析代码：

// This code is intended to be used at quick-bench.com.
// Needs profiling library AND ADDITIONAL INCLUDES to compile, 
// see https://github.com/google/benchmark
    
#include<vector>
    
template<typename T>
std::vector<T> repeat_1(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result;
    auto input_size = input.size();
    result.reserve(input_size * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        for (std::size_t i = 0; i < input_size; ++i) {
            result.push_back(input[i % input_size]);
        }
    }
    return result;
}
    
template<typename T>
std::vector<T> repeat_2(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    for (std::size_t rep = 0; rep < times; ++rep) {
        std::copy(input.begin(), input.end(),
                  std::next(result.begin(), rep * input.size()));
    }
    return result;
}
    
template<typename T>
std::vector<T> repeat_3(const std::vector<T> &input, unsigned int times) {
    std::vector<T> result(input.size() * times);
    auto iter = result.begin();
    for (std::size_t rep = 0; rep < times; ++rep, iter += input.size()) {
        std::copy(input.begin(), input.end(), iter);
    }
    return result;
}


static void version_1(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_1(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_1);
    
static void version_2(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_2(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_2);
    
static void version_3(benchmark::State &state) {
    std::vector<int> vec = {12, 4, 4, 5, 16, 6, 6, 17, 77, 8, 54};
    for (int i = 0; i < 100'000; ++i) {
        vec.push_back(i % 10'000);
    }

    for (auto _ : state) {
        auto repeated = repeat_3(vec, 1000);
        // Make sure the variable is not optimized away by compiler
        benchmark::DoNotOptimize(repeated);
    }
}
BENCHMARK(version_3);

重复 std::vector 的内容

Repeat contents of a std::vector

c++

performance

stdvector