20

我有一个看起来像这样的类：

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()。

所以有什么问题？ 一切正常，除了分析显示由于调用 from导致操作员new被调用过多。list::push_back()DoStuff()

为了提高性能，我想m_list在初始化时预分配内存，Foo如果它是std::vector. 问题是这会引入新的问题，例如：

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

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

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

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

4

5 回答 5

9

我认为您使用错误的容器。

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

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

于 2012-05-20T14:57:33.510 回答
4

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

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

于 2012-05-21T18:52:40.607 回答
3

我的建议与 's 相同，请在编写任何重要代码之前111111尝试切换到。deque

但是，要直接回答您的问题：您可以使用std::list自定义分配器。这有点繁琐，我不会在这里详细介绍所有细节，但要点是您编写一个表示列表节点的内存分配策略的类。分配的节点list将是一个小的实现定义的数量，大于char*，但它们都将具有相同的大小，这意味着您可以仅针对该大小编写优化的分配器（内存块池而不是对象池），并且您可以向它添加功能，让您在需要的时候在分配器中保留您想要的任何空间。然后列表可以快速分配/释放。这使您无需重新实现任何实际list功能。

如果您（出于某种原因）要实现一个具有列表功能的对象池，那么您可以从boost::intrusive. 这在编写您自己的分配器时也可能很有用，用于跟踪您的空闲块列表。

于 2012-05-20T16:21:54.110 回答
3

列表和向量在管理对象的方式上完全不同。

Vector 将元素构建到给定容量的已分配缓冲区中。当容量耗尽时会发生新的分配。列表一个一个地分配元素，每个元素到一个单独分配的空间中。

当插入/删除某些东西时，向量元素会发生变化，因此，向量索引和元素地址是不稳定的。当插入/删除某些内容时，列表元素会重新链接，因此，列表迭代器和元素地址是稳定的。

使列表的行为类似于向量的一种方法是将默认分配器（每次调用时从系统分配）替换为另一个分配器，在更大的块中分配对象，在调用时将子块分配给列表它。这不是标准库默认提供的。

于 2012-05-20T15:09:04.083 回答
1

可能会使用list::get_allocator().allocate(). Afaik，由于 s 的非连续性质，默认行为是在何时获取内存list- 因此缺乏reserve()- 但使用该allocator方法并没有立即发生在我身上的主要缺点。如果您的程序中有一个非关键部分，在开始时或其他任何情况下，您至少可以选择在那个时候承受损害。

于 2012-05-20T14:42:22.543 回答