将向量的向量合并成一个单一的向量

Question

我有一个T类型的向量向量：

std::vector<std::vector<T>> vector_of_vectors_of_T;

我想把它们合并成一个T类型的向量：

std::vector<T> vector_of_T;

我目前正在使用这种方法：

size_t total_size{ 0 };
for (auto const& items: vector_of_vectors_of_T){
    total_size += items.size();
}
vector_of_T.reserve(total_size);
for (auto const& items: vector_of_vectors_of_T){
    vector_of_T.insert(end(vector_of_T), begin(items), end(items));
}

有更简单的方法吗？例如准备好的标准函数？如果没有，手动操作是否有更有效率的方式？

- Humam Helfawi

---

我认为将这个问题发布至http://codereview.stackexchange.com/会更合适。 - default

@Luca Pizzamiglio 感谢您的纠正。 - Humam Helfawi

抱歉，这是错误的语言。请提供英文文本以进行翻译。 - CompuChip

如果你想使用太多STL，可以将此代码用于“reserve”部分：vector_of_T.reserve(std::accumulate(std::begin(vector_of_vectors_of_T), std::end(vector_of_vectors_of_T), 0, [](size_t size, std::vector<T> const& vec) { return size + vec.size(); }));。 - LogicStuff

除了使用移动迭代器（如果您不再需要原始数据），这里没有太多改进的空间。这是range-v3中的“action::join”，也许有一天您会在标准中看到它。 - T.C.

Answer 1

这是一个很好的练习，尝试编写通用的“join”代码。下面的代码接受一个嵌套容器“R1 < R2 < T >”，并返回一个已连接的容器“R1 < T >”。请注意，由于标准库中的分配器参数，这有点麻烦。没有尝试检查分配器的兼容性等问题。

幸运的是，在即将发布的Eric Niebler的range-v3库中有一个名为“action :: join”的函数，它已经非常健壮，并且在Clang上可以使用。

#include <range/v3/all.hpp>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

// quick prototype
template<template<class, class...> class R1, template<class, class...> class R2, class T, class... A1, class... A2>
auto join(R1<R2<T, A2...>, A1...> const& outer)
{
    R1<T, A2...> joined;
    joined.reserve(std::accumulate(outer.begin(), outer.end(), std::size_t{}, [](auto size, auto const& inner) {
        return size + inner.size();
    }));
    for (auto const& inner : outer)
        joined.insert(joined.end(), inner.begin(), inner.end());
    return joined;
}

int main()
{
    std::vector<std::vector<int>> v = { { 1, 2 }, { 3, 4 } };

    // quick prototype
    std::vector<int> w = join(v);
    std::copy(w.begin(), w.end(), std::ostream_iterator<int>(std::cout, ",")); std::cout << "\n";

    // Eric Niebler's range-v3
    std::vector<int> u = ranges::action::join(v);
    std::copy(u.begin(), u.end(), std::ostream_iterator<int>(std::cout, ",")); std::cout << "\n";
}

实时示例

- TemplateRex

---

顺便提一下，这种"可连接容器"的数学术语是单子，（这个概念比你可以用迭代器写的任何东西要更加通用）。 - leftaroundabout

Answer 2

使用back_inserter和move；

size_t total_size{ 0 };
for (auto const& items: vector_of_vectors_of_T){
    total_size += items.size();
}

vector_of_T.reserve(total_size);
for (auto& items: vector_of_vectors_of_T){    
    std::move(items.begin(), items.end(), std::back_inserter(vector_of_T));
}

使用std::move而非简单的复制，可以稍微提高一下性能。

- Praveen

---

如果不进行基准测试，从抽象的角度来看，它应该比我的更快吗？它在使用前也需要预留吗？ - Humam Helfawi

这种方法可能比使用移动迭代器的范围插入版本效率低，特别是对于平凡可复制的元素类型（对于这些类型，范围插入很可能被大量优化）。 - T.C.

Answer 3

我想你可以尝试在循环中使用已经存在的std算法std::merge/std::move。不知道这样做是否更快。

- Piotr Smaroń