2

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

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
};

v因此，对in graph的所有后继者的循环g将如下所示：

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

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

不幸的是，我的图可能有非常不同的实现，所以每个图可能有自己的succ_iterator接口实现。本质上，层次结构中的每个类在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的方法。recycle()由于代码库非常大，这需要更改接口，在我实施之前，我想听听其他设计理念或可能的改进。

编辑：我不使用线程。

4

1 回答 1

0

You could cache the succ_iterators per graph instance and lookup and reuse them when needed?

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

But I don't know if you have threadsafety issues.

于 2012-07-04T09:42:04.800 回答