6

我正在使用向量来管理我的大型结构数据。但是突然，当我发现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::operator []and vector::push_back()，尤其是pushing back占用了我大部分的程序时间（这很耗时）。就我而言，有没有更好的容器可以比std::vector, 而我尝试 google 但没有运气？

4

6 回答 6

6

每次向量超过其当前容量时，分配复制删除（或 C++11 中的分配移动删除）仅发生一次。每次这样的重新分配，容量都会翻倍。这会随着时间的推移而平均化，因此 的摊销复杂度是push_back()恒定的。

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

于 2013-02-21T14:14:13.537 回答
2

在添加元素之前保留您需要的所有空间会解决您的问题吗？

于 2013-02-21T14:11:06.467 回答
0

仅当您的向量大小超过其容量时才会发生重新分配。如果您提前（甚至粗略地）知道您的向量将包含多少项目，您可以使用它的保留成员来预先分配足够的容量。即使在填充向量时，您也可以自己以受控方式触发重新分配，以减少调用的次数，从而获得更好的性能。

现在，如果您想要保证恒定时间插入，则可以使用一些容器，但需要权衡取舍（例如，std::list将分配许多小内存块，这些内存块最终可能不会比您当前的向量使用更快，new因为慢，而且内存使用也会更重要，并且您会丢失随机访问，但请确保每次插入所花费的时间与其他插入大致相同）。

于 2013-02-21T14:11:19.387 回答
0

如果您知道最终数据大小，则可以使用它reserve来预分配向量所需的内存。这将删除所有重新分配和复制。

如果您不知道确切的大小，请根据您对传入数据的了解进行有根据的猜测。

于 2013-02-21T14:11:29.480 回答
0

向量是一个动态扩展的容器，但它的内容需要在一个连续的内存块中（我记得，这在 C++11 之前没有指定，但每个人都这样做了）。所以如果你的vector已经有8个元素，而vector当前的容量是8个元素，那么当你push_back第9个元素时，容器必须为更大的容量分配新的空间，复制容器中已经存在的8个元素，将第 9 个元素复制到新空间，然后销毁旧空间。如果您使用的是 C++11，并且您的元素支持移动构造，那么 8 个副本可以变成 8 个移动。或者，如果您想产生管理指针的开销，您可以存储指向元素的指针而不是元素（复制指针很便宜，但现在您需要处理寿命问题）。

至于哪个容器比向量快，这是一个很大的开放式问题。它取决于各种访问/操作模式。std::list 被提及为候选人。O(1) 添加到列表的末尾，但可能比向量使用的摊销 O(1) 更大。您失去了对容器的随机访问权。

于 2013-02-21T16:05:05.267 回答
-1

众所周知，大部分时间是push_back()恒定的，但是当size()到达capacity().

如果您想要恒定时间插入，您必须尝试 astd::list或 a std::deque。特别是 astd::deque在靠近其接口中的向量的同时，为在容器末尾的插入提供了正确的性能。

从cpp 参考中提取：

因此，它们提供了与向量相似的功能，但在序列的开头也可以有效地插入和删除元素，而不仅仅是在序列的结尾。但是，与向量不同，双端队列不能保证将其所有元素存储在连续的存储位置，因此不允许通过偏移指向元素的指针进行直接访问。

于 2013-02-21T14:09:53.713 回答