How can I fill vector with values in the most efficient way in cpp?-CodePudding

Hi I have a function that assigns values from 0 to the size of ELEMENT_COUNT How can I improve the performance of this function?

constexpr size_t ELEMENT_COUNT = 1000 * 10000;

std::vector<uint64_t> fill_vector(size_t elementCount) {
    std::vector<uint64_t> vec(elementCount);
    for (size_t i = 0; i < elementCount; i  ) {
        vec.push_back(i);
    }
    return vec;
}

I thought about using basic assigment instead of using push_back(i):

std::vector<uint64_t> fill_vector(size_t elementCount) {

    std::vector<uint64_t> vec(elementCount);
    for (size_t i = 0; i < elementCount; i  ) {
        vec[i] = i;
    }
    return vec;
}

but does anyone have an idea for a better improvement?

CodePudding user response：

What you're currently doing can be done in a simpler way and it is usually fast enough:

#include <cstdint>
#include <numeric>
#include <vector>

auto fill_vector(std::uint64_t elementCount) {
    std::vector<std::uint64_t> vec(elementCount);

    std::iota(vec.begin(), vec.end(), std::uint64_t{});
    return vec;
}

Here's another solution, not sure if it is faster, but worth trying out. It should avoid the zero-initialization and the bounds-checks:

#include <cstddef>
#include <cstdint>
#include <vector>

template <class T = int>
struct IntIter {
    T i;
    const auto& operator*() const { return i; }
    auto operator==(IntIter rhs) const { return i == rhs.i; }
    auto operator!=(IntIter rhs) const { return !operator==(rhs); }
    auto& operator  () {
          i;
        return *this;
    }
    auto operator-(IntIter rhs) const {
        return static_cast<std::ptrdiff_t>(i - rhs.i);
    }
};

template <class T>
struct std::iterator_traits<IntIter<T>> {
    using iterator_category = std::random_access_iterator_tag;
    using value_type = const T;
    using reference = value_type&;
    using pointer = value_type*;
    using difference_type = std::ptrdiff_t;
    using size_type = std::size_t;
};

auto fill_vector(std::uint64_t elementCount) {
    return std::vector<std::uint64_t>(IntIter<std::uint64_t>{0},
                                      IntIter<std::uint64_t>{elementCount});
}

CodePudding user response：

First of all, your first example is incorrect. This version of vector constructor makes a vector, reserves a memory for elementCount elements and initializes them with default values, in this case with zeros. Then you are adding additional elementCount elements that are 0..elementCount.

In the second example you reserved a memeory, initizlized it with zeros and changed zeroes to values you need.

What you essentially want is to reserve a memory and fill elements without default initialization of them with push_back/emplace_back (with trivial types such as uint there wouldn't be difference)

So, the right and simple way to do this would be something like this:

std::vector<uint64_t> fill_vector(size_t elementCount) {

    std::vector<uint64_t> vec;
    vec.reserve(elementCount);
    for (size_t i = 0; i < elementCount; i  ) {
        vec.push_back(i);
    }
    return vec;
}