c++ - 基于抽象迭代器加速设计的想法

Question

在某些 C++ 项目中，我正在处理表示各种性质的图形的对象。它们都实现了一个通用的抽象接口(interface)，我将在这篇文章中将其简化为一个函数:

class graph {
public:
   ...
   // Create an iterator over the successors of v
   virtual succ_iterator* succ(const vertex* v) const = 0;
   ...
};

succ_iterator 类也是一个抽象类，可以迭代 v 的后继顶点:

class succ_iterator {
public:
   virtual void first() = 0;               // reset the iterator
   virtual void next() = 0;                // move to next successor
   virtual bool done() const = 0;          // no more successor left?
   virtual const vertex* dest() const = 0; // destination vertex
};

因此，在图 g 中遍历 v 的所有后继者的循环看起来像这样:

succ_iterator* i = g->succ(v);
for (i->first(); !i->done(); i->next()) {
   // use i->dest()
}
delete i;

我经常使用这样的循环来实现图形算法。 分析代码表明它花费了大量时间为这些微小的迭代器实例分配内存，所以我想听听改进它的想法。

不幸的是，我的图可能有非常不同的实现，因此每个图可能都有自己的 succ_iterator 接口(interface)实现。本质上，graph 层次结构中的每个类在 succ_iterator 层次结构中都有对应的类。例如，可以使用 std::vector 显式存储邻接列表来实现一个图(在这种情况下，succ_iterator 是 std::vector 之上的简单包装器: :const_iterator)，而另一个图可能是即时计算的(在这种情况下，它的 succ_iterator 实例实际上会计算后继者)。我不知道编译时图表的性质，所以这排除了基于 template 的实现 à la STL。

我考虑过让每个图处理一个 succ_iterator 池。这似乎需要一个额外的 graph::succ_release(succ_iterator*) 方法来将迭代器返回到池中而不是删除它。我见过的大多数池都是在内存级别完成的:即，当你释放一个对象时，它的析构函数被调用，但占用的内存被保留，以便下一个对象将在同一时间创建(使用就地构造函数)堵塞。这似乎仍然浪费时间，因为就地构造函数将不得不设置一个与前一个对象相同的虚拟表指针。我认为在这样的池中，我应该将 delete+new 替换为与构造函数具有相同原型(prototype)的 recycle() 方法。由于代码库非常大，并且这需要更改界面，因此在实现此代码之前，我想听听其他设计想法或可能的改进。

编辑:我不使用线程。

Answer 1

您可以缓存每个图形实例的 succ_iterators 并在需要时查找和重用它们吗？

//static or member:
std::map<graph*,succ_iterator*> graph_iterator_cache;

但我不知道你是否有线程安全问题。