C++ 遍历大小为 N 的子向量

Question

我有一个可以是任意大小的输入向量。我想要的是将这个向量分成每个大小为 64 的向量并做一些事情。输入向量的大小不一定是 64 的倍数。

假设我有一个大小为 200 的向量，那么我应该将它分成 3 个大小为 64 的向量和 1 个大小为 8 的向量。

目前我想到的是：

vector<double> inputVector;
vector<vector<double>> resultVector;

UInt16 length = inputVector.size();
int div = (length % 64) == 0 ? length / 64 : (length / 64) + 1;

for (int i = 0, j = 0; i < div; i++) {
    vector<double> current
    for (int k = 0; k < 64; k++) {
        current.push_back(inputVector[j]);
       if (j++ >= length) break;
    }
    resultVector.push_back(current);
    if (j >= length) break;
}

我相信会有更好的方法，但我找不到任何示例

Answer 1

您可以使用迭代器创建子向量：

vector<double> inputVector;
vector<vector<double>> resultVector;

for (auto it = inputVector.cbegin(), e = inputVector.cend(); it != inputVector.cend(); it = e) {
    e = it + std::min<std::size_t>(inputVector.cend() - it, 64);
    resultVector.emplace_back(it, e);
}

Answer 2

最简单的就是将每个元素 push_back 放到某个向量中，跟踪它们，如果达到块大小，则将它们“刷新”到输出向量：

template<typename T>
std::vector<std::vector<T>> devide(const std::vector<T>& v, size_t chunk) {
    // iterative algorithm
    std::vector<T> tmp;
    std::vector<std::vector<T>> ret;
    size_t cnt = 0;
    for (auto&& i : v) {
        tmp.push_back(i);
        ++cnt;
        if (cnt == chunk) {
             cnt = 0;
             ret.push_back(tmp);
             tmp.clear();
        }
    }
    if (cnt != 0) {
        ret.push_back(tmp);
    }
    return ret;
}

但是这种迭代方法并不是最优的——我们可以复制内存块。因此遍历 vector 并在每个循环中复制最多元素的块数 - 并在最后一个循环中复制更少。

template<typename T>
std::vector<std::vector<T>> devide2(const std::vector<T>& v, size_t chunk) {
    // chunk algorithm
    std::vector<std::vector<T>> ret;
    const auto max = v.size();
    for (size_t i = 0; i < max; ) {
        const size_t chunkend = std::min(i + chunk, max);
        ret.emplace_back(v.begin() + i, v.begin() + chunkend);
        i = chunkend;
    }
    return ret;
}

Tested on godbolt.

Answer 3

更多STL风格：

void even_slice(In b, In e, size_t n, F f)
{
    while(std::distance(b, e) >= n) {
        f(b, b + n);
        b = b + n;
    }
    if (b != e) {
        f(b, e);
    }
}

template<typename In, typename Out>
Out even_slice_to_vetors(In b, In e, size_t n, Out out)
{
    using ValueType = typename std::iterator_traits<In>::value_type;
    using ItemResult = std::vector<ValueType>;
    even_slice(b, e, n, [&out](auto x, auto y) { *out++ = ItemResult{x, y}; });
    return out;
}

https://godbolt.org/z/zn9Ex1

Answer 4

请注意，您确切知道有多少子向量具有所需的最大大小：

template<typename It>
auto subdivide_in_chunks(It first, It last, size_t chunk_size) {
    using value_type = typename std::iterator_traits<It>::value_type;
    size_t size{ std::distance(first, last) / chunk_size };
    std::vector<std::vector<value_type>> ret;
    ret.reserve(size);
    auto last_chunk = std::next(first, size * chunk_size);
    while ( first != last_chunk ) {
        auto next = std::next(first, chunk_size);    
        ret.emplace_back(first, next);
        first = next;
    }
    ret.emplace_back(first, last);  // This is the last, shorter one. 
    return ret;
}

Answer 5

使用 range-v3，你可以简单地写：

namespace rs = ranges;
namespace rv = ranges::views;

auto resultVector = inputVector 
                  | rv::chunk(64) 
                  | rs::to<std::vector<std::vector<double>>>;

这是一个demo。

C++ 遍历大小为 N 的子向量

C++ iterate over subvectors of size N

c++

stdvector