c++ - std::vector 推速？

Question

我正在使用 vector 来管理我的大型结构数据。但是突然间，当发现 vector 源代码时，我很惊讶地看到下面的一些代码:

inline void push_back(const _Ty& _X)
    {insert(end(), _X); }
//...

void insert(iterator _P, size_type _M, const _Ty& _X)
    {
//////////////////////////////////////////////////////////////
        iterator _S = allocator.allocate(_N, (void *)0);
        iterator _Q = _Ucopy(_First, _P, _S);
        _Ufill(_Q, _M, _X);
        _Ucopy(_P, _Last, _Q + _M);
        _Destroy(_First, _Last);
        allocator.deallocate(_First, _End - _First);
//////////////////////////////////////////////////////////////
    }

这是“销毁”然后重新分配其整个 vector 数据的片段代码。这太烦人了，因为我的结构很大，一个 vector 必须管理​​数百个元素，而我只使用 vector::operator [] 和 vector::push_back()，尤其是 pushing back 占用了我大部分的程序时间(很耗时)。就我而言，有没有更好的容器可以比 std::vector 执行得更快，而我尝试用谷歌搜索但没有成功？

Answer 1

分配-复制-删除(或 C++11 中的分配-移动-删除)只会在每次 vector 超过其当前容量时发生一次。每次重新分配时，容量都会加倍。这会随着时间的推移平均化，所以 push_back() 的摊销复杂度是常数。

您可以使用其 reserve() 预先分配 vector 的容量成员函数。