c++ - std::list 是否有等效于 vector::reserve() 的方法？

Question

我有一个如下所示的类(class):

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() 的每个后续调用中使用。

那么问题出在哪里？一切正常，除了分析显示由于从 DoStuff() 调用的 list::push_back() 调用了过多的操作符 new。

为了提高性能，我想在 Foo 的初始化中为 m_list 预分配内存，就像 std::vector 一样>。问题是这会引入新的问题，例如:

1. insert 和 erase 元素的效率较低。
一旦 vector 从对 DoStuff() 的一次调用更改为下一次调用，
2. m_it 就会变得无效。 编辑: Alan Stokes 建议使用索引而不是迭代器来解决这个问题。

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

是我遗漏了什么还是它真的是最简单的解决方案？我宁愿不“重新发明轮子”，而是使用标准解决方案(如果存在)。

任何想法、解决方法或有启发性的评论都将不胜感激!

Answer 1

我认为你使用了错误的容器。

如果你想快速推回那么不要自动假设你需要链表，链表是一个慢容器，它基本上适合重新排序。

更好的容器是 std::deque。双端队列基本上是一个数组数组。它分配一 block 内存并在您推回时占用它，当它用完时它将分配另一个 block 。这意味着它只会非常不频繁地分配，并且您不必像 std::vector 和 reserver 那样提前知道容器的大小以提高效率。