Repeat contents of a std::vector

user_9988487 0
Viewed 164

Suppose I have a vector (potentially large) of trivial types, e.g.

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

What is the best way to repeat it n times?

E.g. 3 times would give the result {1,2,3,1,2,3,1,2,3}

Surely, this is a problem that arises often (numeric libraries usually have such a function build in). My naive solution:

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;
}

Surely this can be made faster? Maybe with std::copy? In that case, however, I'm not sure how to tell the vector its new size while avoiding zero-initialization. Apparently it cannot be done easily (see, e.g., 1). I tried to do it with iterators as well, but it didn't seem to be faster.

stdvector c++ performance
3 Answers

I would just immediately size the vector to avoid any intermediate re-allocations. Then you can use std::copy with some arithmetic to copy the input vector into result using specific offsets into that pre-allocated vector.

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;
}
user_22964580

With range-v3 you could write:

#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>>;
}

Here's a demo.

I suspect this will have sufficiently good performance for your needs.

user_83728530

This was originally an edit to the question. The user cigien suggested to post it as an answer. This contains some incomplete (i.e., not yet exploring all possibilities to implement the solution) profiling results.

I made some profiling code (I'm by no means an expert on profiling) comparing my version and the one in the answer by Cory Kramer. The code in the answer appears to be 4.5 times faster than mine (tested at quick-bench.com with GCCv10.1, C++17, O3 optimization). The suggestion by Remy Lebeau to save a temporary of the iterator does not appear to make any difference.

There were duplicate questions of this that I missed before asking myself: 1 and 2. Some of the answers in these suggest even more slightly different solutions which I haven't profiled yet.

The range-v3 library (answer by cigien), while it looks very convenient, is not an option for me to use and I also didn't profile it.

Profiling code:

// 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);
user_99884870
Related