连接两个向量的最佳方法是什么？

Question

我正在使用多线程并想要合并结果.例如:

std::vector<int> A;
std::vector<int> B;
std::vector<int> AB;

我希望AB按顺序拥有A的内容和B的内容.做这样的事情最有效的方法是什么？

Answer 1

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );

Answer 2

这正是成员函数std::vector::insert的用途

std::vector<int> AB = A;
AB.insert(AB.end(), B.begin(), B.end());

Answer 3

取决于您是否真的需要物理连接两个向量,或者您希望给出迭代的连接外观.boost :: join函数

http://www.boost.org/doc/libs/1_43_0/libs/range/doc/html/range/reference/utilities/join.html

会给你这个.

std::vector<int> v0;
v0.push_back(1);
v0.push_back(2);
v0.push_back(3);

std::vector<int> v1;
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
...

BOOST_FOREACH(const int & i, boost::join(v0, v1)){
    cout << i << endl;
}

应该给你

1
2
3
4
5
6

注意boost :: join不会将两个向量复制到一个新容器中,而是生成一对覆盖两个容器跨度的迭代器(范围).将会有一些性能开销,但可能会少于将所有数据首先复制到新容器.

Answer 4

在 Bradgonesurfing 的回答的方向上，很多时候人们并不真的需要连接两个向量 (O(n))，而只是像连接它们一样处理它们 (O(1))。如果这是你的情况，它可以在不需要 Boost 库的情况下完成。

诀窍是创建一个向量代理：一个包装类，它操作对两个向量的引用，外部视为一个连续的向量。

用法

std::vector<int> A{ 1, 2, 3, 4, 5};
std::vector<int> B{ 10, 20, 30 };

VecProxy<int> AB(A, B);  // ----> O(1). No copies performed.

for (size_t i = 0; i < AB.size(); ++i)
    std::cout << AB[i] << " ";  // 1 2 3 4 5 10 20 30

执行

template <class T>
class VecProxy {
private:
    std::vector<T>& v1, v2;
public:
    VecProxy(std::vector<T>& ref1, std::vector<T>& ref2) : v1(ref1), v2(ref2) {}
    const T& operator[](const size_t& i) const;
    const size_t size() const;
};

template <class T>
const T& VecProxy<T>::operator[](const size_t& i) const{
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};

template <class T>
const size_t VecProxy<T>::size() const { return v1.size() + v2.size(); };

主要优势

创建它是 O(1)（恒定时间），并且需要最少的额外内存分配。

一些需要考虑的事情

• 只有当你真正知道处理引用时你在做什么时，你才应该去做。此解决方案旨在针对所提出问题的特定目的，对此效果很好。如果您不确定引用的工作方式，在任何其他上下文中使用它可能会导致意外行为。
• 在这个例子中，AB并没有提供一种非const访问运算符（[]）。随意包含它，但请记住：由于 AB 包含引用，因此为其分配值也会影响 A 和/或 B 中的原始元素。这是否是一个理想的功能，这是一个特定于应用程序的问题，应该仔细考虑。
• 直接对 A 或 B 进行的任何更改（如赋值、排序等）也将“修改”AB。这不一定是坏事（实际上，它可能非常方便：AB 永远不需要显式更新以保持自身与 A 和 B 同步），但它肯定是一种必须注意的行为。重要的例外：将 A 和/或 B 调整为更大可能会导致它们在内存中重新分配（为了需要连续空间），这反过来会使 AB 无效。
• 因为每次访问一个元素之前都要进行一次测试（即“i < v1.size()”），VecProxy 访问时间虽然恒定，但也比向量慢一点。
• 这种方法可以推广到 n 个向量。我没试过，但应该没什么大不了的。

Answer 5

根据Kiril V. Lyadvinsky的回答,我做了一个新版本.此代码段使用模板和重载.有了它,你可以写vector3 = vector1 + vector2和vector4 += vector3.希望它可以提供帮助.

template <typename T>
std::vector<T> operator+(const std::vector<T> &A, const std::vector<T> &B)
{
    std::vector<T> AB;
    AB.reserve( A.size() + B.size() );                // preallocate memory
    AB.insert( AB.end(), A.begin(), A.end() );        // add A;
    AB.insert( AB.end(), B.begin(), B.end() );        // add B;
    return AB;
}

template <typename T>
std::vector<T> &operator+=(std::vector<T> &A, const std::vector<T> &B)
{
    A.reserve( A.size() + B.size() );                // preallocate memory without erase original data
    A.insert( A.end(), B.begin(), B.end() );         // add B;
    return A;                                        // here A could be named AB
}