在 O(1) 时间内将右值向量附加到向量

Question

我想知道如何将恒定时间 (O(1)) 中的右值向量附加到另一个向量。我知道使用std::insertand 的方法std::move，但是有没有任何方法std::vector<T>&&可以std::vector<T>&在 O(1) 时间内将 a 添加到。

Answer 1

为什么右值对这个很重要？Big-O 表示法计算进程中完成的操作数。无论这些操作是复制还是移动，如果执行的操作数与源列表中的项目数成正比，那么它是一个 O(n) 过程。

如果您要将一个连续的元素序列复制/移动到另一个连续的元素序列中，结果是连续的，则该过程必须是 O(n)（至少），其中 n 是元素的数量源序列。即使它做了一个memcpy源元素，smemcpy的某个序列在序列中的Ts 数量上也是 O(n) T。