多态 STL 容器和迭代器

引言

STL标准容器存储固定类型对象的实例，该类型在其模板参数中指定。因此，它们在设计上不支持多态性：您无法轻松地存储类层次结构中的对象。

第一个，也是最直接的想法是定义一个容器来存储指向基类的指针

typedef std::list<T*> polyTlist;

但这会带来两个主要问题

1. 当容器被使用时，指针会被复制，但被指向的对象（被指向者）不会。这将导致内存泄漏和多重引用问题，例如

   polyTList a;
   a.push_back(new T(1));
   polyTList b=a; // the pointer to T(1) is copied in b list
   *b.front()=T(2); // but *a.front() is also re-assigned!

2. 标准算法将操作指针，而不是被指向的对象。除非您想按内存地址对对象进行排序，否则这没什么用……

智能指针再次出击！

在容器中存储智能指针可以部分解决第一个问题。理想情况下，我们需要使用“深拷贝”或“写时拷贝（cow）”所有权策略的智能指针，如[1]中所述，以模仿标准容器的行为。然而，这需要基类实现某种类型的克隆方法，这可能会对性能产生一定影响。

我们更倾向于使用引用计数指针，例如[2]，它们主要为标准指针行为增加了自动释放功能。这确保了算法中的最佳性能，并且我们将通过另一种机制防止多重引用的事故，该机制实现在迭代器中，如下所述。

typedef std::list<boost::shared_ptr<T> > polyTlist;
polyTList a;
a.push_back(new T(1));
polyTList b=a; // the pointer to T(1) is copied in b list
*b.front()=T(2); // should not compile
b.front()=new T(2); // correct way to re-assign

多态迭代器

对存储在容器中的数据的访问是通过迭代器对象完成的。通过定义我们自己的迭代器来透明地支持多态性，标准算法可以在不修改的情况下应用于多态容器。

我们首先实现const_iterator，它提供对数据的只读访问。第一次尝试可能是

template<class C, typename T>
class const_poly_iterator:public C::const_iterator
{
    typedef C::const_iterator _Parent;
    typedef const_poly_iterator<C,T> _Self;
public:
    _Self() {};
    _Self(const _Parent& p):_Parent(p) {};

    const T& operator*() const {return *_Parent::operator*();}
    const T* operator->() const {return &operator*();}
};

这基本上重写了给定容器C的标准const_iterator的解引用运算符*和->，以执行双重解引用，从而访问存储的数据。

然而，某些STL实现存在一个问题，它们使用实际指针作为迭代器，特别是对于std::vector：C++不允许从内置类型派生类，因此上述模板定义可能会失败。我们必须这样实现const_iterator

template<class C, typename T>
class const_poly_iterator
#if _MSC_VER>=1300 // VC7
  :public std::iterator_traits<typename C::const_iterator>
  // needed by VC7 (VS.NET / 2003) 
#endif
{
  typedef const_poly_iterator<C,T> _Self;
  //! mimic inheritage from the regular const_iterator
  //! because we cannot simply derive from it since
  //            some iterators are regular pointers
protected:
  typedef typename C::const_iterator I;
  //!< regular iterator of the underlying container
  I i; 
public:
  operator I&() {return i;}
  //!<needed to use poly_iterator in algorithms transparently
public:
  _Self() {};
  _Self(const I& p):i(p) {}

  const T& operator*() const {return **i;}
  T* const operator->() const {return &**i;}

public: // compatibility with I iterator
  _Self& operator++() {++i; return *this;}
  _Self& operator--() {--i; return *this;}
  bool operator==(const I& other) const {return i==other;}
  bool operator!=(const I& other) const {return i!=other;}
  bool operator==(const _Self& other) const {return i==other.i;}
  bool operator!=(const _Self& other) const {return i!=other.i;}
};

隐式转换运算符“operator _Parent&()”模仿了C::const_iterator的实际继承。

const_iterator满足了我们关于多重引用的安全要求，因为它提供了对const数据的访问。理想情况下，如果我们不为多态容器提供非const迭代器，我们就会是安全的。然而，许多算法需要为任何容器提供迭代器。我们的解决方案是定义具有与const_iterator完全相同的接口的迭代器。

template<class C, typename T>
  class poly_iterator:public const_poly_iterator<C,T>
#if _MSC_VER>=1300 // VC7 iterators must derive from iterator_traits
  ,public std::iterator_traits<typename C::iterator>
#endif
{
  typedef poly_iterator<C,T> _Self;
  typedef const_poly_iterator<C,T> _Parent;
  typedef typename C::iterator I;
  //!< regular iterator of the underlying container
 
  //! mimic inheritage from the regular iterator
  //! because we cannot simply derive from it since
  //            some iterators are regular pointers
public:
  operator I&() {return (I&)i;}
  //!<needed to use poly_iterator in algorithms transparently
public:
  _Self() {};
  _Self(const I& p):_Parent(p) {};
  _Self(const _Parent& p):_Parent(p) {};
  //!< construction form const_poly_iterator
public: // compatibility with I iterator
  _Self& operator++() {++i; return *this;}
  _Self& operator--() {--i; return *this;}
};

在这里，所需的隐式转换运算符对数据安全构成微小威胁，因为它允许访问底层的智能指针，该指针可能在解引用+赋值中使用。然而，只要多态容器和迭代器可以安全地透明地使用（即，与标准容器相同的方式），我们就认为允许那些“知道自己在做什么”的用户访问底层数据结构是可以的。

引入工厂

要将多态对象插入我们的结构中，我们需要一种克隆它们的方法，即一种在保留其类型的同时复制它们的方法。由于每个类层次结构可能需要不同的克隆方式，我们实现了一个通用类，它包装了一个类工厂，该工厂将默认用于多态容器，但可以根据需要轻松覆盖。

template<typename T, typename R=boost::shared_ptr<T> >

struct poly_factory
{
    inline static R factory(const T& p) {return R(T::Factory(p));}
};

默认情况下，工厂会调用类层次结构中名为“Factory”的方法，该方法返回一个指向对象新副本的智能指针，该对象作为参数传递。

现在，容器(们)

当然，我们可以实现polymorphic_list、polymorphic_vector、polymorphic_queue等等，但是懒惰是泛型程序员的优点，所以我们定义了一个单一的、基于模板的polymorphic_container，它可以派生自（几乎）任何标准容器。

template<class C, typename T, typename F=poly_factory<T,C::value_type> >
class poly_container : public C
{
  typedef C _Parent;
  typedef poly_container<C,T,F> _Self;
  typedef typename C::value_type value_type; // (smart) pointer to T  
protected:
  typedef T& reference;
  typedef const T& const_reference;
public:
  typedef typename _Parent::size_type size_type;
  typedef poly_iterator<C,T> iterator;
  typedef const_poly_iterator<C,T> const_iterator;

  _Self() {}; // default constructor
  _Self(const _Parent& p):_Parent(p) {}; // copy constructor

  const_iterator begin() const {return _Parent::begin();}
  const_iterator end() const {return _Parent::end();}
  iterator begin() {return _Parent::begin();}
  iterator end() {return _Parent::end();}
  iterator insert(iterator i, const value_type& f) 
                   {return _Parent::insert(i, f);}
 
  void push_front(const value_type& f) {insert(begin(), f);}
  void push_back(const value_type& f) {insert(end(), f);}
  const_reference front() const {return *_Parent::front();}
  const_reference back() const {return *_Parent::back();}

  void push_front(const_iterator& f) 
    {copy(begin(), *_Parent::const_iterator(f));}
  void push_back(const_iterator& f) 
    {insert(end(), *_Parent::const_iterator(f));}

  iterator insert(iterator i, const T& f) 
    {return _Parent::insert(i, F::factory(f));}
  void push_front(const T& f) {insert(begin(), F::factory(f));}
  void push_back(const T& f) {insert(end(), F::factory(f));}
};

我们添加了一些方法来插入、在末尾添加和在开头添加已存在于其他多态容器中的元素，以避免需要深拷贝机制，以及通过使用工厂直接插入对象的方法。

然后，我们可以这样定义我们的示例多态列表：

typedef poly_container<std::list<boost::shared_ptr<T>,T> polyTlist;

源代码

该代码是“DYL”库的一部分，可在SourceForge上找到。

未来工作

我们的方法可以轻松应用于关联容器，如std::map，我们尚未这样做，仅仅是因为我们的应用程序中不需要它（再次是懒惰）。

参考文献

1. Andrei Alexandrescu "Modern C++ Design, Generic Programming and Design Pattern Applied", 2001, Addison-Wesley In-Depth Series, ISBN 0-201-70431-5。
2. Boost库中的智能指针。
3. STL多态容器简介.
4. 尝试实现对多态敏感的算法.