STL向量與反向和彈出/ push_back成本

我不是很好想出算法成本，所以我在這裏問。STL向量與反向和彈出/ push_back成本

這裏是最初與1000個元素初始化的向量：

vector<unsigned int> mFreeIndexes(1000);

我將不斷pop_back /的push_back元素到矢量，但從來沒有的push_back超過1000（所以從來力矢量來重新分配）。

在這種情況下，pop_back/push_back操作是O（1）還是O（n）？

來源

2017-09-12 Avithohol

只要沒有重新分配，它應該是O（1）。 –

當你'push_back'你*添加*元素的向量。在上述定義之後，如果你做了'mFreeIndexes.push_back（1）;'那麼矢量將有1001個元素。也許你想要['reserve']（http://en.cppreference.com/w/cpp/container/vector/reserve）函數？ –

此問題已在[documentation]（http://en.cppreference.com/w/cpp/container/vector/pop_back）中得到解答。 – nwp

從C++標準23.3.7.5：

空隙的push_back（常量Ť& X）;

void push_back（T & & x）;

備註：導致重新分配，如果新的大小比原來容量（...）

注意，它不說，它不能在其他情況下重新分配更高，但是這將是該標準非常不尋常的實現。我認爲你可以放心地認爲push_back在有容量時不會重新分配。

pop_back的東西有點複雜。該標準沒有在pop_back上下文中說明重新分配的任何內容。但它似乎是一個常見的實現（不知道例外），pop_back不會重新分配。還有一些擔保雖然看到：

Can pop_back() ever reduce the capacity of a vector? (C++)

反正只要你不走了預定義的大小你是安全的假設，沒有發生重新分配和複雜性確實是O（1）。

來源

2017-09-12 15:12:06 freakish

我只是想補充一點，帶有'push_back（）'和'pop_back（）'用法的'vector <>'是你可以得到的最快的堆棧：你的內部循環中不會有任何內存分配，它提供了良好的緩存局部性。 – cmaster

如果容量不變，（迭代器和引用）失效保證可以防止它重新分配。 – Caleth

@Caleth我無法在標準中找到這些保證。不適合流行。僅用於擦除。流行音樂可能從功能上來源於擦除，但我也無法找到。 – freakish

STL向量與反向和彈出/ push_back成本

回答

相關問題