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成本

回答

相关问题