在 c++中如何高效的将一个 vector 连接到另外一个 vector 上后面？

[v2byy]

我的理解是需要做一次拷贝。因为 vector 在内部是用数组实现的，其地址是保证是连续的，无法使用移动语义，将一个 vector 移动到另外的一个 vector 上。

还有一个问题，地址连续是说虚拟内存地址是连续，还是说物理内存地址也是连续？

stackoverflow 上类似问题:

concatenating-two-stdvectors

上面说道使用：std::make_move_iterator。令我难以理解的是：为了实现 vector 内部地址的连续，我觉得必须重新将一个 vector 的数据拷贝过来，这里的“移动”是怎么移动的呢？

我理解的“移动”是直接通过指针接管过来。但是如果已经定义了两个 vector，相当于已经申请了两块不连续的内存空间，这个时候如何通过“移动”来不拷贝的直接将 vector 连接起来呢？

[v2byy]

还有一个问题：在 visual studio 中，通过 memory 窗口查看的数据，这个地址应该是进程的虚拟地址空间吧？不是 physical memory 吧？

[lixiang1993]

是虚拟地址连续啊 不然你只有 2G 内存 但是 32 位系统还是 4G 虚拟内存的。就是整块拷贝吧 其实看 vector 底层实现有一个目前这块的最大长度 如果两个长度加一起超过了最大长度，就会新申请一段新空间 2(1.5?)倍扩展。stl 源码底层 cp 调用的可能是 memcpy ？这块记不清了。

[exch4nge]

地址连续指的是虚拟内存地址连续。
一般应用层程序能看到的只能是虚拟内存地址，不过物理内存与虚拟内存一般是按页映射的，所以很大可能上物理地址也是连续的。

在 visual studio 中，通过 memory 窗口查看的数据，这个地址是进程的虚拟地址空间。

你的主问题，个人觉得无法满足吧，用了 make_move_iterator 也只是把元素当成右值，后来应该会用移动构造（？）方式构造一个新对象放到 vector 后面，具体发生不发生拷贝得看类 T 的移动构造（？）怎么写的；（这点可能说的不对，看楼下的）

[neoblackcap]

@lixiang1993 是 2，最好的应该是 phi （约为 1.6，即黄金比率）

[Akiyu]

移动语义不是你想的那样, 人家说了

This will not be more efficient for the example with ints, since moving them is no more efficient than copying them, but for a data structure with optimized moves, it can avoid copying unnecessary state:
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;
}

在这里, 使用了 move 后, 对 src 的访问都会失效, 因为 src 被 "move" 了
move 和具体的类有关, 它支持移动语义, 那么 move 就是有效的

[dosmlp]

因为 vector 内部就是数组啊，要拼起来当然要重新申请内存把两个都拷贝过来（前提 vector 预留内存不够）
虚拟地址连续一般物理地址也连续

[GeruzoniAnsasu]

c++中提到“移动”，绝大多数情况都是在说移动语义，实际上就是去调用移动构造函数在新的内存空间上构造新对象。而又由于，通常对于可移动可复制的对象来说，复制构造需要进行 deep copy 而移动构造只需要修改指针，因此使用移动构造以及移动语义能高效得多。

假设 vector 中的对象是容器类型，如 string，那么在使用赋值语义或复制语义时，每个容纳的 string 都会进行 deep copy，以保证新旧 vector 里都还有同样内容的，不同的 string 实例；而“移动”过去的话，则不需要存在两倍的 string 实例，被 move 走的 vector 里的 string 对象会变成一个不指向内容的空壳，但新旧 vector 里的 string 仍然是不同实例。

[wevsty]

地址连续是说虚拟内存地址是连续的，对应的物理内存地址一般来说是连续的，但是也有可能不连续。

std::make_move_iterator 的作用是把迭代器转换为引用右值的迭代器。右值进行移动的时候就会使用移动构造函数，对于普通的复制将会使用复制构造函数。
vector 上如果存的是基本数据类型，移动和复制没有什么区别，区别在于遇到类类型的时候，这时候调用移动构造函数就不一定会复制类种所有的值。

[GeruzoniAnsasu]

至于连接两个 vector，仅假设 capacity 不够大的情况。

首先肯定要重新申请连续的空间这是毋庸置疑的，大小至少能容纳连接后的总长。如果事先 reserve 过足够大的空间，这个重分配只会发生一次，如果不 reserve 直接迭代插入末尾，每当空间不够大时都会重新分配两倍大小的空间，并使用前面说的移动语义在新空间上构造原先存在的对象。

make_move_iterator 的作用是产生指向右值引用的迭代器，迭代器解引用后是个右值引用，用右值引用构造新对象时调用的是移动构造，之后发生的事跟上面说的移动语义发生的事一样

[stephen9357]

当然是指虚拟地址连续，对于应用层以及绝大部分内核开发来说，都不会直接面对物理地址。
单论正规操作的话，我认为最高效的连接方式应该是获取两个 vector 的 size 之和，将第一个 vector resize 到足够的大小，然后将第二个 vector move 到第一个 vector 后面。
先 resize，避免可能的多次空间分配，再 move，避免深拷贝的开销。

[koebehshian]

效率的事件是类库框架考虑的问题,程序员只要会调用就行了,如果没有一个满意的,那就自己造一个,如果对编译器不满意,就直接用汇编写,如果对机器指令不满意,就自己画电路.

[exonuclease]

看你 vector 持有的是引用还是值了 vector 里面存的东西复制一次是避免不了的

[lixiang1993]

@neoblackcap 记得看了一篇文章 标准是 2 有的也采用了 1.5 https://www.zhihu.com/question/36538542 并没有见过 1.6 的，如果哪个版本 stl 是用 1.6 实现的，请给出链接，只是单纯的想了解更多，并没有别的意思。

[lixiang1993]

@neoblackcap 看到你在那个答案下的回复了 黄金分割最佳没问题

[neoblackcap]

@lixiang1993 这个只是理论上限的值，实际生产用 1.5 就可以了。要不然完全用 phi，你永远也不可能重用之前的内存的。