std :: list是否有一个等效的vector :: reserve()？

Question

我有一个看起来像这样的课程:

typedef std::list<char*> PtrList;
class Foo
{
public:
   void DoStuff();
private:
   PtrList m_list;
   PtrList::iterator m_it;
};

该函数DoStuff()基本上将元素添加到其中m_list或从中删除元素,找到其中某些特殊元素的迭代器并将其存储在其中m_it.值得注意的是m_it,每个后续调用都使用了每个值DoStuff().

所以有什么问题？ 一切正常,除了分析显示new由于list::push_back()调用from 而调用运算符太多DoStuff().

为了提高性能,我想m_list在初始化时预先分配内存,Foo就像我做的那样std::vector.问题是这会引入新的问题,例如:

1. 效率insert和erase元素效率低下.
2. m_it一旦矢量从一个呼叫改变到下一个呼叫,它就变为无效DoStuff().编辑:艾伦斯托克斯建议使用索引而不是迭代器,解决这个问题.

我的解决方案:我能想到的最简单的解决方案是实现一个也具有链表功能的对象池.这样我就可以得到一个链表,并可以为它预先分配内存.

我错过了什么或者它是否真的是最简单的解决方案？我宁愿不"重新发明轮子",而是使用标准解决方案,如果存在的话.

任何想法,变通方法或启发性评论将不胜感激!

Answer 1

我认为你错了容器.

如果你想快速推回然后不自动假设你需要一个链表,一个链表是一个缓慢的容器,它基本上适合重新排序.

一个更好的容器是std :: deque.deque基本上是一个数组数组.它会分配一块内存并在你向后推时占用它,当它用完时会分配另一个块.这意味着它只是很少分配,你不必提前知道容器的大小,如std :: vector和reserver.

Answer 2

您可以使用splice中的函数std::list来实现池。添加一个新的成员变量PtrList m_Pool。当要添加新对象且池不为空时，将值赋给池中的第一个元素，然后将其拼接到列表中。要删除一个元素，请将其从列表拼接到池中。

但如果你不关心元素的顺序，那么 adeque会快得多。如果要删除中间的元素，请将最后一个元素复制到要删除的元素上，然后删除最后一个元素。