「剪切並粘貼」std :: vector的最後k個元素嗎？

Question

是否有可能在C++ 11中將std :: vector A的最後k個元素「剪切並粘貼」到一個新的std :::向量B中？

一種方法是使用B.insert(A.end() - k, A.end())然後在A上使用擦除，但這些都是O（k）時間操作。

毛

Answer 1

不，向量擁有自己的記憶。

此操作稱爲拼接。否則forward_list是可笑的，但它確實有O（1）拼接。

通常，決定要移動哪些元素的過程已經是O（n），因此讓拼接本身花費O（n）時間不是問題。矢量上的其他操作更快，而不是彌補它。

Answer 2

這通常是不可能的，因爲（至少在C++ 03版本中 - 它是23.2.4/1）C++標準保證vector<T>使用的內存是一個連續的塊。因此，在O（1）時間內「傳輸」超過固定數量的元素的唯一方法是，如果接收向量爲空，並且您已安排將其分配的內存塊開始於內部的第一個向量 - 在這種情況下，「轉移」可能會被認爲完全沒有時間。 （以這種方式故意重疊對象幾乎肯定會構成理論上的未定義行爲 - 實際上它也非常脆弱，因爲任何使迭代器無效到vector<T>的操作也可以重新分配內存，從而破壞事情。）

如果您準備犧牲一大堆可移植性，我聽說可以通過虛擬內存映射來玩OS級別（或硬件級別）技巧，以實現諸如無開銷環形緩衝區之類的技巧。也許這些技巧也可以在這裏應用 - 但要記住，單一過程中虛擬物理內存映射是一對一的假設是非常根深蒂固的，所以您可能會遇到一些驚喜。