如何最佳地连接两个向量？

Question

如何最佳地连接两个向量？

253

我正在使用多线程并希望合并结果。例如：

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

我希望将A和B的内容按顺序合并到AB中，如何最有效地实现？

- jmasterx

1

如果你在处理大容量的容器时想要提高效率，使用链表可能更为高效。你可以通过多个指针操作将它们连接起来。但链表会带来空间开销（建议使用单向链表）。 - Kemin Zhou

1

这个回答解决了你的问题吗？连接两个std :: vectors - Henke

10个回答

94

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

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

- Shirik

5

@Nick：与什么相比较，它缓慢呢？ - GManNickG

2

也许它在每次插入元素时都会检查足够的空间？预先使用reserve将加速它。 - RvdK

13

@Nick：如果每个现代的stdlib实现都在随机访问迭代器上专门化insert并预留前置，我不会感到惊讶。 - GManNickG

1

@Gman：这是个不错的观点，因为我们知道源也是一个向量（其中迭代器“距离”具有O（1）复杂度）。但是，在你经常可以通过提前计划做得更好时，要注意insert的性能保证。 - Nick Bastin

2

@RvdK 检查空间只需要几个指令：加载容量，与大小比较，条件跳转；对于大多数情况来说，这些都是可以忽略的成本。由于 size < capacity 大部分时间都成立，分支预测很可能会导致非重新分配分支的指令在指令流水线中，最小化分支引起的延迟，除了低迭代计数。这假设有一个良好的向量实现，加上 CPU 指令流水线和[良好的]分支预测，但这些对于现代工具链和台式机来说是相当可靠的假设。不过我不知道智能手机怎么样。 - boycy

显示剩余3条评论

28

这取决于你是否真的需要物理连接这两个向量，或者你只是想为了迭代而给出连接的外观。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;
}

应该给你

注意，boost::join不会将这两个向量复制到新容器中，而是生成一对迭代器（范围），涵盖两个容器的跨度。可能会有一些性能开销，但也许比首先将所有数据复制到新容器中要少。

- bradgonesurfing

1

不错的想法。经过一段时间的思考，我意识到这个目标也可以在不使用boost库的情况下实现。我已经发布了一个解释如何做到这一点的答案。 - Ronald Souza

21

编辑： C++23为向量提供了append_range方法。

AB.append_range(A);
AB.append_range(B);

就是这样了！

时间复杂度为O（|A| + |B|）。对于那些只需要“看起来像连接”的情况，下面描述了一个O（1）（常数时间）的替代方法。

在Bradgonesurfing的回答方向上，很多时候我们并不真正需要将两个向量连接起来（O(n)），而是只需要像它们已经连接起来一样处理（O(1)）。如果你的情况是这样的，那么可以不使用Boost库来实现。

关键是创建一个向量代理：一个包装类，它通过引用操作两个向量，从外部看起来就像是一个连续的向量。

用法：

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

vproxy<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 vproxy {
private:
    std::vector<T>& v1, v2;
public:
    vproxy(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& vproxy<T>::operator[](const size_t& i) const{
    return (i < v1.size()) ? v1[i] : v2[i - v1.size()];
};

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

主要优势

创建它的时间复杂度是O(1)（常数时间），并且只需要最少的额外内存分配。

一些需要考虑的事项

如果你在处理引用时真的知道自己在做什么，那么你应该只是去做。这个解决方案是为了特定的问题而设计的，对于这个问题来说，它运行得相当不错。如果你不确定引用的工作原理，将它应用于其他任何上下文可能会导致意外行为。
在这个例子中，AB不提供非常量的访问操作符([ ])。你可以自由地添加它，但要记住：由于AB包含引用，为其赋值也会影响A和/或B中的原始元素。无论这是否是一个可取的特性，都是一个需要谨慎考虑的应用程序特定问题。
直接对A或B进行的任何更改（如赋值、排序等）也将“修改”AB。这并不一定是坏事（实际上，它非常方便：AB永远不需要显式更新以使其与A和B保持同步），但这确实是一个人必须注意的行为。 重要的例外：将A和/或B调整为更大可能会导致它们在内存中重新分配（为了连续空间的需求），这将使AB失效。
因为每次访问元素都要进行测试（即“i < v1.size()”），所以虚拟代理的访问时间虽然是恒定的，但也比向量稍微慢一些。
这种方法可以推广到n个向量。我没有尝试过，但应该不是一个大问题。

- Ronald Souza

1

正是我所需要的，非常感谢。 - thomas

18

基于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
}

- aloisdg

1

你的意思是将每个向量的元素相加吗？还是你的意思是追加？现在这很清楚，但未来5年呢？如果含义不明确，就不应该重载运算符。 - S.R

2

@S.R 我的意思是连接。我在三年前写下了这个答案，现在我仍然知道它的含义。没有问题。如果C++可以提供自己的重载，那就更好了。（是的，::已经被占用了;) - aloisdg

在向量中添加元素时（**operator+=**），最好不要在insert之前调用reserve。请参阅关于reserve的这些说明。但对于另一个运算符（operator+）来说，这是有意义的。 - user5534993

@aloisdgmovingtocodidact.com 乍一看，我会说hint表明insert()比reserve()更可取。因此，你应该不使用reserve()。然而，该注释将其与具有push_back()的特定示例进行了比较，而您没有使用它们。我的第一个想法是说可以省略reserve()。但是，我不会拿自己的生命去赌。值得提出一个单独的问题。 - user5534993

1

">>"是"追加"运算符的一个很好的选择，因为这就是Bash对文件所做的操作。 - Chris Reid

显示剩余5条评论

3

还有一种未被提到的简单变体：

copy(A.begin(),A.end(),std::back_inserter(AB));
copy(B.begin(),B.end(),std::back_inserter(AB));

使用合并算法：

```c++ #include #include #include #include #include #include template class Container, class T> std::string toString(const Container& v) { std::stringstream ss; std::copy(v.begin(), v.end(), std::ostream_iterator(ss, "")); return ss.str(); };

int main() { std::vector A(10); std::vector B(5); //零填充 std::vector AB(15);

std::for_each(A.begin(), A.end(), [](int& f)->void { f = rand() % 100; });

std::cout << "合并前: " << toString(A) << "\n"; std::cout << "合并前: " << toString(B) << "\n"; merge(B.begin(),B.end(), begin(A), end(A), AB.begin(), [](int&,int&)->bool {}); std::cout << "合并后: " << toString(AB) << "\n";

return 1; } ```

- D. Alex

0

对于这种情况，如果您事先知道每个线程产生的结果数量，则可以预先分配AB并将std::span传递给每个线程。这样就不需要进行连接操作。例如：

std::vector<int> AB(total_number_of_results, 0);
std::size_t chunk_length = …;
std::size_t chunk2_start = chunk_length;
std::size_t chunk3_start = 2 * chunk_length; // If needed
…
// Pass these to the worker threads.
std::span<int> A(AB.data(), chunk_length);
std::span<int> B(AB.data() + chunk2_start, chunk_length);
…

- tsnorri

0

我的答案基于Ronald Souza先生的原始解决方案。除了他的原始解决方案外，我还编写了一个支持迭代器的向量代理！

对于不了解原始解决方案背景的人，这里简要介绍一下：joined_vector模板类（即向量代理）将两个向量的引用作为构造函数参数，然后将它们视为一个连续的向量。我的实现还支持前向迭代器。

用法：

int main()
{
    std::vector<int> a1;
    std::vector<int> a2;

    joined_vector<std::vector<int>> jv(a1,a2);

    for (int i = 0; i < 5; i++)
        a1.push_back(i);
    for (int i = 5; i <=10; i++)
        a2.push_back(i);

    for (auto e : jv)
        std::cout << e<<"\n";
    for (int i = 0; i < jv.size(); i++)
        std::cout << jv[i] << "\n";
    return 0;
}

实现:

template<typename _vec>
class joined_vector
{
    _vec& m_vec1;
    _vec& m_vec2;

public:

    struct Iterator
    {
        typedef typename _vec::iterator::value_type type_value;
        typedef typename _vec::iterator::value_type* pointer;
        typedef typename _vec::iterator::value_type& reference;
        typedef std::forward_iterator_tag iterator_category;
        typedef std::ptrdiff_t difference_type;
        _vec* m_vec1;
        _vec* m_vec2;
        Iterator(pointer ptr) :m_ptr(ptr)
        {

        }
        Iterator operator++()
        {
            if (m_vec1->size() > 0 && m_ptr == &(*m_vec1)[m_vec1->size() - 1] && m_vec2->size() != 0)
                m_ptr = &(*m_vec2)[0];
            else
                ++m_ptr;
            return m_ptr;
        }
        Iterator operator++(int)
        {
            pointer curr = m_ptr;
            if (m_vec1->size() > 0 && m_ptr == &(*m_vec1)[m_vec1->size() - 1] && m_vec2->size() != 0)
                m_ptr = &(*m_vec2)[0];
            else
                ++m_ptr;
            return curr;
        }
        reference operator *()
        {
            return *m_ptr;
        }
        pointer operator ->()
        {
            return m_ptr;
        }

        friend bool operator == (Iterator& itr1, Iterator& itr2)
        {
            return itr1.m_ptr == itr2.m_ptr;
        }
        friend bool operator != (Iterator& itr1, Iterator& itr2)
        {
            return itr1.m_ptr != itr2.m_ptr;
        }
    private:
        pointer m_ptr;
    };

    joined_vector(_vec& vec1, _vec& vec2) :m_vec1(vec1), m_vec2(vec2)
    {

    }
    Iterator begin()
    {
        //checkes if m_vec1 is empty and gets the first elemet's address,
        //if it's empty then it get's the first address of the second vector m_vec2
        //if both of them are empty then nullptr is returned as the first pointer
        Iterator itr_beg((m_vec1.size() != 0) ? &m_vec1[0] : ((m_vec2.size() != 0) ? &m_vec2[0] : nullptr));
        itr_beg.m_vec1 = &m_vec1;
        itr_beg.m_vec2 = &m_vec2;
        return itr_beg;
    }
    Iterator end()
    {
        //check if m_vec2 is empty and get the last address of that vector
        //if the second vector is empty then the m_vec1's vector/the first vector's last element's address is taken
        //if both of them are empty then a null pointer is returned as the end pointer
        typename _vec::value_type* p = ((m_vec2.size() != 0) ? &m_vec2[m_vec2.size() - 1] : ((m_vec1.size()) != 0 ? &m_vec1[m_vec1.size() - 1] : nullptr));
        Iterator itr_beg(p != nullptr ? p + 1 : nullptr);
        itr_beg.m_vec1 = &m_vec1;
        itr_beg.m_vec2 = &m_vec2;
        return itr_beg;
    }
    typename _vec::value_type& operator [](int i)
    {
        if (i < m_vec1.size())
            return m_vec1[i];
        else
            return m_vec2[i - m_vec1.size()];
    }
    size_t size()
    {
        return m_vec1.size() + m_vec2.size();
    }

};

- Sudharsan

0

所有的解决方案都是正确的，但我发现编写一个函数来实现这个更容易。像这样：

template <class T1, class T2>
void ContainerInsert(T1 t1, T2 t2)
{
    t1->insert(t1->end(), t2->begin(), t2->end());
}

这样你就可以避免像这样的临时放置：

ContainerInsert(vec, GetSomeVector());

- user3360767

-1

如果你的向量已经排序好了，可以查看来自<algorithm>的set_union。

set_union(A.begin(), A.end(), B.begin(), B.end(), AB.begin());

在链接中有一个更全面的示例。

- Cogwheel

6

此外，它与直接追加不会执行相同的操作-输出范围内的元素是唯一的，这可能不是原帖作者想要的（它们甚至可能不可比较）。这肯定不是最有效的方法。 - Peter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kirill V. Lyadvinsky · Accepted Answer

403

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

- Kirill V. Lyadvinsky

8

谢谢！我没想到还有备用的选项。 - jmasterx

13

它应该复制每个元素，因此时间复杂度为O(n)。 - Kirill V. Lyadvinsky

2

不确定是否应该提出一个新问题，但是在考虑移动语义时，这个答案能否得到改进？我是否可以期望/指示编译器执行单个内存移动而不是循环遍历所有元素？ - Broes De Cat

2

@boycy 不是的。push_back一个元素的时间是摊销常数时间。push_back n个元素的时间是O(n)。 - Konrad Lindenbach

1

@Konrad 我并没有暗示其他，但感谢你的澄清。请注意，插入操作的复杂度从来没有以要插入的元素数量为基础 - 这将始终给出O(n) - 而是以容器中已有元素的数量为基础，因为这提供了其可扩展性的度量。 - boycy

显示剩余11条评论