修剪連續STD容器

Question

假設我有一個容器一樣如下：

std::vector<int> numbers{1,2,3,4,5,6,7,8}; 

什麼是「修剪」，它最有效的方法是什麼？如在中，從其中刪除元素，但僅從開始或結束。

可以說我想將'數字'轉換爲容器{3,4,5,6,7}。一種方法我能想到的刪除「8」非常有效地爲：

numbers.resize(numbers.size()-2); 

這似乎保證無重新分配和去除不適合新尺寸所有尾隨元素（在這種情況下，只有最後一個元素，8）。

有沒有類似的方式來做到這一點與容器的開始？而且，只要我傳遞給resize的參數小於或等於容器的原始大小，該操作是否保證爲O（1）？

Answer 1

一種方法我能想到的刪除「8」非常有效地爲：

numbers.resize(numbers.size()-2); 

假設這應該是-1，不，這不是你想要做什麼。您應該始終選擇用於該作業的工具。在這種情況下，如果你想只刪除最後一個元素，那就是：

numbers.pop_back(); 

如果你想刪除最後n元素（假設n <= numbers.size()全境），這就是：

numbers.erase(numbers.end() - n, numbers.end()); 

這保證了沒有重新分配或額外移動 - 它只會調用適當的析構函數，然後移動結束指針。如果這種類型可以被破壞，那麼即使是這個類型的第一部分也是不可操作的。

如果你想刪除第一n元素，這就是對稱：

numbers.erase(numbers.begin(), numbers.begin() + n); 

然而，這涉及整體平移以後的元素來填補這個洞 - 所以它有多少元素的功能在那邊。 vector從後面抹去很便宜，但從前面擦除很昂貴（這本身就是具有pop_back()但不是pop_front()的動機）。正因爲如此，如果你想trim()，從右邊擦掉。

如果你從前面進行大量擦除，你應該考慮使用一個容易修剪兩端的容器 - 如std::deque。好的是 - 代碼看起來都一樣。您仍然希望使用雙迭代器erase()進行修剪。

你絕對不想要做的是（儘管多麼誘人它可能會出現）：

numbers.assign(numbers.begin() + 2, numbers.end() - 1); 

也就是不確定的行爲。

Answer 2

std::vector不支持從有效地將前除去的元素，但boost::circular_buffer確實：http://www.boost.org/doc/libs/release/doc/html/circular_buffer.html

在一定程度上，std::deque支持此過，但它有一些問題，如常見的實現僅在分配少量這意味着它可能比circular_buffer分配更多的內存。並且從std::deque中刪除很多元素的速度並不快，因爲它必須釋放許多塊（而circular_buffer只是遞增整數值）。