连接两个std::vectors

Question

连接两个std::vectors

c++vectorstlconcatenationstdvector

988

我应该如何拼接两个std::vector？

- yigal

10

给出的答案实际上并没有连接。它们附加了一个副本。也许创建一个std::vector连接方法在效率方面有用，但这将需要对节点管理进行一些复杂的共享，这可能就是为什么它还没有被实现的原因。 - Douglas Daseeco

16

@FauChristian：从效率的角度来看，可能没有用处。向量内存必须是连续的，所以你建议的做法是不可能的。如果你希望进行“一些复杂的节点管理共享”，并且你要以这种方式更改向量类，那么你最终会得到一个deque。即使这样，按照建议的方式重用内存也非常困难，尽管这样开始变得更加可行。我认为它目前还没有被实现。主要问题是，在这种节点管理共享（deque）中，末尾节点可能部分为空。 - Cookie

17

我是唯一一个想知道为什么标准库中没有将这个实现为 a + b 或 a.concat(b) 的人吗？也许默认实现会不够优化，但并不需要对每个数组连接都进行微观优化。 - oseiskar

54

多年的演化，成为任何主流语言中最先进的运算符重载系统，采用一种模板系统来增加语言的复杂性，然而答案并不是简单的 v = v1 + v2; - Spike0xff

7

我的猜测是，STL不想在语言方面过于具体，以防您希望将运算符用于其他操作，比如在物理模型中添加力向量。在这种情况下，您可能希望重载 forceVector1 + forceVector2，以便在清晰简明的代码中进行逐项加法。 - Jonathan Lidbeck

显示剩余2条评论

29个回答

304

如果你正在使用C++11，并且希望移动元素而不仅仅是复制它们，你可以使用std::move_iterator与insert（或copy）一起使用：

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<int> dest{1,2,3,4,5};
  std::vector<int> src{6,7,8,9,10};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  // Print out concatenated vector.
  std::copy(
      dest.begin(),
      dest.end(),
      std::ostream_iterator<int>(std::cout, "\n")
    );

  return 0;
}

对于整数示例而言，这样做并不会更加高效，因为移动它们的效率与复制它们相同，但是对于已优化移动的数据结构，它可以避免复制不必要的状态：

#include <vector>
#include <iostream>
#include <iterator>

int main(int argc, char** argv) {
  std::vector<std::vector<int>> dest{{1,2,3,4,5}, {3,4}};
  std::vector<std::vector<int>> src{{6,7,8,9,10}};

  // Move elements from src to dest.
  // src is left in undefined but safe-to-destruct state.
  dest.insert(
      dest.end(),
      std::make_move_iterator(src.begin()),
      std::make_move_iterator(src.end())
    );

  return 0;
}

在移动完成后，src元素处于未定义但安全销毁状态，其以前的元素直接转移到dest的新元素末尾。

- Alex

14

std::make_move_iterator()方法帮助我在尝试连接std::unique_ptr的std::vectors时使用。 - Knitschi

4

这种方法和std::move(src.begin(), src.end(), back_inserter(dest))有什么不同？ - kshenoy

4

@kshenoy，insert 可能一次性分配所需的内存。而 back_inserter 则可能导致多次重新分配。 - yrHeTateJlb

1

这和没有使用 std::make_move_iterator() 有什么区别？ - road_to_quantdom

3

这将使用移动构造函数将src中的元素移动到dest。如果没有使用std::make_move_iterator，它将使用拷贝构造函数。 - Carlo Wood

189

我会使用insert函数，类似这样：

vector<int> a, b;
//fill with data
b.insert(b.end(), a.begin(), a.end());

- AviewAnew

92

或者您可以使用：

std::copy(source.begin(), source.end(), std::back_inserter(destination));

如果两个向量包含的内容不完全相同，那么这种模式是有用的，因为您可以使用某些东西代替 std::back_inserter 将一种类型转换为另一种类型。

- Roger Lipscombe

16

复制方法并不是一个好的方式。它会多次调用push_back，这意味着如果需要插入很多元素，这可能会导致多次重新分配内存。更好的方法是使用insert函数，因为vector的实现可以进行一些优化以避免重新分配内存。在开始复制之前，它可以预留内存。 - Yogesh Arora

11

可以，但你可以先调用 reserve 方法。使用 std::copy 的原因在于如果你想使用除了 back_inserter 以外的其他方式时，它就会变得很有用。 - Roger Lipscombe

当你说“多次分配”时，这是正确的 - 但最坏情况下分配的次数是log（添加的条目数） - 这意味着添加一个条目的成本与添加的条目数量无关。（基本上，除非分析表明需要保留，否则不必担心它）。 - Martin Bonner supports Monica

2

复制很糟糕，即使使用保留。vector::insert将避免所有检查： http://quick-bench.com/bLJO4OfkAzMcWia7Pa80ynwmAIA - Denis Yaroshevskiy

2

@SamuelLi - 在 push_back 中，if > capacity_ 大多是一个问题。这个问题足够严重，以至于 resize 中的 memset 并不重要。 - Denis Yaroshevskiy

显示剩余2条评论

85

使用C++11，我更喜欢将向量b附加到向量a的以下方式：

std::move(b.begin(), b.end(), std::back_inserter(a));

当a和b没有重叠，并且b不再需要使用时。

这是来自<algorithm>的std::move，而不是来自<utility>的通常的std::move。

- Deqing

17

如果a实际上等于b，将会出现未定义行为（如果你知道这种情况永远不会发生，那么可以接受，但在编写通用代码时应该意识到这一点）。 - Martin Bonner supports Monica

1

@MartinBonner 谢谢您提到这个。也许我应该回到旧的“插入”方式，这样更安全。 - Deqing

29

啊，另一个std::move。第一次看到它时相当令人困惑。 - xaxxon

4

这与使用move_iterator的insert()有何不同？如果有，具体是什么？ - GPhilo

2

我已经添加了一条关于我们正在讨论的std::move的注释，因为大多数人不知道这个重载。希望这是一个改进。 - YSC

显示剩余3条评论

45

std::vector<int> first;
std::vector<int> second;

first.insert(first.end(), second.begin(), second.end());

- James Curran

37

我更喜欢已经提到的那一个：

a.insert(a.end(), b.begin(), b.end());

但如果您使用C++11，还有一种更通用的方法：

a.insert(std::end(a), std::begin(b), std::end(b));

此外，虽然不是问题的一部分，但建议在追加之前使用reserve以获得更好的性能。如果您将向量与自身连接而没有保留空间，则操作将失败，因此您应始终reserve。

所以基本上你需要：

template <typename T>
void Append(std::vector<T>& a, const std::vector<T>& b)
{
    a.reserve(a.size() + b.size());
    a.insert(a.end(), b.begin(), b.end());
}

- ST3

2

std::是通过参数相关查找推导出来的。end(a)就足够了。 - asu

5

如果a的类型来自于std，那么ADL只会添加std::，这将破坏泛型的特性。 - Potatoswatter

好的观点。在这种情况下它是一个向量，所以它仍然可以工作，但是是的，那是更好的解决方案。 - asu

std::begin()/end()是为那些没有成员函数的集合（如数组）添加的。但是数组也没有一个insert()成员函数，这引出了一个问题：“是否有一种集合具有insert()但没有begin()（可以使用std::begin()）？” - James Curran

2

您应尽量避免使用reserve函数，因为它可能会带来巨大的开销。请参考此链接：https://dev59.com/InVC5IYBdhLWcg3wYQAp#64102335 - Ido Kessler

请注意，使用insert将向量连接到自身是超出insert规范的（未定义行为）。提前调用reserve也无法改变这一点。 - j6t

32

使用range v3，你可以实现一个惰性（lazy）的连接：

ranges::view::concat(v1, v2)

演示。

- Jarod42

12

我预测这将是2023年左右的恰当答案。 - wcochran

@wcochran 现在是2023年。当前的C++23草案（N4928）尚未包含concat，但它已经在计划中，最终将被添加到某个C++标准中。 - ReinstateMonica3167040

4

@ReinstateMonica3167040 真遗憾——我也在等待飞行汽车。或许要等到2024年了。 - wcochran

22

提高concatenate的性能的一般方法是检查向量的大小，并将较小的向量与较大的向量合并/插入。

//vector<int> v1,v2;
if(v1.size()>v2.size()) {
    v1.insert(v1.end(),v2.begin(),v2.end());
} else {
    v2.insert(v2.end(),v1.begin(),v1.end());
}

- Vikramjit Roy

如此简单，但我从未想过这种方式！ - Zimano

2

示例代码不正确。v1.insert(v2.end()...)使用了一个指向v2的迭代器来指定在v1中的位置。 - David Stone

1

你也可以使用快速交换。@DavidStone 我编辑了一下，这样连接顺序就可以改变了。能否在向量的开头添加内容？ - qwr

1

你可以插入到开头，但这样会更慢。然而，为了真正“连接”，通常顺序确实很重要，所以这就是你需要做的事情。 - David Stone

2

我不喜欢这个答案，因为你并没有在所有情况下（没有注明）在v1之后插入v2。否则，如果你添加一个将连接保存在另一个向量中而不是修改它们之一的解决方案，那么你的答案可能更完整。 - user6547518

15

在C++17中，有一个算法std::merge，当输入向量已排序时非常易于使用。

以下是示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    //DATA
    std::vector<int> v1{2,4,6,8};
    std::vector<int> v2{12,14,16,18};

    //MERGE
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));

    //PRINT
    for(auto item:dst)
        std::cout<<item<<" ";

    return 0;
}

- Pavan Chandaka

14

我不认为它比std::vector::insert更容易使用，但它确实做了一些不同的事情：将两个范围合并成一个新范围，而不是将一个向量插入到另一个末尾。这值得在答案中提到吗？ - j b

好的，我明白需要回答什么。我会添加。 - Pavan Chandaka

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

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

- Robert Gamble · Accepted Answer

1025

vector1.insert( vector1.end(), vector2.begin(), vector2.end() );

- Robert Gamble

63

我只需要添加代码来获取每个向量所包含的元素数量，并将 vector1 设置为包含最多元素的向量。如果你不这样做，就会进行很多不必要的复制。 - Joe Pineda

45

我有一个问题。如果vector1和vector2是相同的向量，这个方法还有效吗？ - Alexander Rafferty

41

只有当 vector1.capacity() >= 2 * vector1.size() 时才能这样做。这种情况并不常见，除非你已经调用了 std::vector::reserve()。否则，向量将进行重新分配，从而使参数2和3所传递的迭代器无效。 - Drew Dormann

56

很遗憾标准库中没有更简洁的表达方式。.concat或+=或其他什么东西。 - nmr

15

在C++中，这非常简洁。 - YSC

显示剩余5条评论