继承列表

• 下载源代码 - 1.6 KB

引言

本文讨论了一对多关系常见实现所带来的算法复杂度。作者提出了一种在 C++ 中简单高效的替代方案。

背景

对象之间的关系是面向对象编程中开发人员需要处理的主要主题之一。这些关系根据其基数进行分类：一对一、一对多、多对多，

对于一对多关系，根据我的经验，开发人员可用的各种资源（书籍、教程、论坛）提供的实现从算法复杂度的角度来看都非常低效。

这些实现主要使用聚合数组或列表，有些使用集合。这个示例代码应用于主题-观察者模式，说明了我的观点。

class Observer
{
   Subject* _subject;

public:
   Observer() : _subject(nullptr) { }
   ~Observer() { detach(); }

   void attach(Subject* s)
   {
      detach();
      if(_subject = s)
         _subjet->attach(this);
   }
   void detach()
   {
      if(_subject)
         _subject->detach(this);
      _subject = nullptr;
   }
};

class Subject
{
   friend class Observer;

  // Obviously, only one of these containers should be used at a time
  array<Observer*> _observers;
  list<Observer*> _observers;
  set<Observer*> _observers;

  void _notify() { ... }
  void _attach(Observer* o)
  {
      // this is pseudo-code
      // the proper method should be called according to the container specification
     _observers.insert(o);
  }
  void _detach(Observer* o)
  {
     // this is pseudo-code
     // the proper method should be called according to the container specification
     _observers.remove(o);
  }
  ~Subject()
  {
     // this is pseudo-code
     while(_observers.size())
        _observers[0]->detach();
  }
};

在数组容器上，删除操作的复杂度为 O(n)。首先，必须找到观察者的位置，然后必须移动表中后续的元素来填补观察者删除后留下的空缺。

在列表容器上，复杂度是相同的，问题类似。在删除观察者之前，必须先找到它的位置。查找元素导致 O(n) 的复杂度，而不是删除操作本身。

在集合容器上，复杂度取决于集合的实现。在二叉树（如 std::set）中，插入和删除操作的复杂度都为 O(log2(n))。

总而言之，所有复杂度都来自于 **需要找到指向它的容器中观察者的位置**。

简单但高效的替代方案

可以通过在 Observer 类中直接使用双向链表实现来非常简单地解决查找复杂度问题。

class Observer
{
   friend class Subject;

   Subject*  _subject;
   Observer* _prev;
   Observer* _next;

public:
   Observer() : _subject(nullptr) , _prev(nullptr) , _next(nullptr) { }
   ~Observer();           // same implementation
   void attach(Subject*); // same implementation
   void detach();         // same implementation
};

class Subject
{
   friend class Observer;

   Observer* _first;

   void attach(Observer* o)
   {
      o->_next = _first;
      if(_first)
         _first->_prev = o;
      _first = o;
   }
   void detach(Observer* o)
   {
      if(_first == o)
         _first = o->_next;
      if(o->_prev)
         o->_prev->_next = o->_next;
      if(o->_next)
         o->_next->_prev = o->_prev;
      o->_prev = o->_next = nullptr;
   }
};

因为 **观察者知道它在列表中的位置**（_prev 和 _next 成员），所以无需查找。**复杂度为 O(1)**。

附加（attach）或分离（detach）的实现很简单，

它占用的内存空间与列表或集合相似，是数组的两倍。

它唯一的缺点是存在裸指针（如今已不流行），并且需要为每种新关系重写相同的几行代码。

使用继承解决最后的缺点

相关类的成员和 attach/detach 方法可以移到一个模板类对：inList 和 inCell。“in”前缀表示继承。

template <typename LIST, typename CELL>
class inCell
{
 public: 
   inList<LIST,CELL>* _list;
   inCell<LIST,CELL>* _prev;
   inCell<LIST,CELL>* _next;
 
   inCell() : _list(nullptr) , _prev(nullptr) , _next(nullptr) { }
   ~inCell();                       // same implementation
   void attach(inList<LIST,CELL>*); // same implementation
   void detach();                   // same implementation
};

template <typename LIST, typename CELL>
class inList
{
public:
   inCell<LIST,CELL>* _first;

   void attach(inCell<LIST,CELL>*); // same implementation
   void detach(inCell<LIST,CELL>*); // same implementation
};

然后，一对多关系的每种实现都通过继承来保证。对于设计问题，将优先使用私有继承，并编写外观方法。

class Observer : private inCell<Subject,Observer>
{
public:
   void attach(Subject* s) { InCell<Subject,Observer>::attach(s); }
   void detach()           { InCell<Subject,Observer>::detach(); } 
};

class Subject : private inList<Subject,Observer>
{
   friend class Observer;
};

对于主题-观察者模式，**一对多关系得到了保证**，永远“密封”在 inList-inCell 实现中。这与“通用”实现不同，后者需要为每种新关系编写少量代码。

因为 C++ 允许 **多重继承**，所以所有需要的类之间的多对多关系都可以通过这种方式轻松实现。下面是一个包含 3 个相关类的示例。

class Record : private inCell<Artist,Record>
{
};

class Label : private inList<Label,Artist>
{
   friend class Artist;
};

class Artist : private inList<Artist,Record>,
               private inCell<Label,Artist>
{
   friend class Record;

   void sign(Label* l) { inCell<Label,Artist>::attach(l); }
   ...
}; 

此外，这种做法非常直观。**一对多关系非常清晰可见**，集中在一个地方。

基准测试

测试中，vector、list 和 set 来自标准库。

测试包括将 N 个观察者附加到主题，然后将它们分离。分离的顺序对于衡量算法复杂度很重要。为了模拟真实用例，将分离位于容器中间的观察者，以避免偏向第一个或最后一个位置。在列表容器的特殊情况下，如果移除的观察者总是在第一个位置，则执行时间将为 O(1)（此测试中不可见）。

继承列表（inList）的执行是线性的。执行时间以 inList 的执行时间为基准进行归一化。

Attach

所有容器类型的执行速度都比 inList 慢。

除了 std::set 的 O(log2(n)) 外，所有容器的执行时间都是线性的。

随着容器大小的增长，vector 的相对速度会变快。这是因为 vector 的重分配策略。

list 需要为其中包含的每个单元分配/释放内存，这非常耗时。inCell 则不然，因为 **观察者本身就是单元**。

	附加
	向量	列表	set	inList
10	20	16	23	1
100	11	36	61	1
1000	7	40	86	1
10000	7	42	101*	1

(*) 在普通的笔记本电脑上，附加 10k 个元素的 set 操作耗时 0.0015 秒。

Detach

vector 和 list 的复杂度为 O(n)。如果 set 增长 10 倍，执行时间相对于 inList 会延长 10 倍。

set 的复杂度为 O(log2(n))。每当容器大小翻倍时，执行时间会慢一个级别。

	分离
	向量	列表	set	inList
10	5	15	29	1
100	42	71	80	1
1000	575	703	187	1
10000	5135	8681*	233	1

(*) 在普通的笔记本电脑上，分离列表中的 10k 个元素耗时 0.05 秒。

讨论

一种常见的实现（即使用聚合的 vector/list/set）可能足以满足某些需求；容器可能很小，附加/分离操作不常发生，计算机足够快等等。

然而，继承列表在运行时始终是最佳选择，远远领先于其他方法，无论集合大小如何。它易于实现和理解，设计稳健，呈现清晰，并且具有 O(1) 的复杂度。总之，它值得被所有人了解。

我想向我的导师 Michel Ziackovic 致敬（法语中“Rendre à César ce qui est à César”）。他 25 年前就教会了我这种做事方式。他是复杂的 CAD 软件的架构师，其中成千上万的一对多关系，涉及数百个类，至今仍以这种方式实现。

历史

• 2020年1月23日：初版