C++ STL与泛型编程-第二篇 （Boolan）

本章内容：
1 OOP(面向对象编程) vs. GP(泛型编程)
2 模板(泛化，全特化，偏特化)
3 分配器
4 容器之间实现关系与分类
5 深度探索list
6 迭代器的设计原理和interator traits的作用与设计

1 OOP(面向对象编程) vs. GP(泛型编程)

• OOP企图将datas和methods关联在一起。
  list不能使用全局的::sort()进行排序，因为全局sort()中用到了RandomAccessIterator，而list没有该迭代器，只有当有RandomAccessIterator时才能进行全局的排序操作。

• GP却是将datas和methods分开来。
  Data Structures(Containers)
  template<class T, class Alloc=alloc>
  class vector{
  ……
  };
  template<class T, class Alloc=alloc, size_t BufSiz=0>
  class deque{
  ……
  };
  Alogrithms
  template<typename _RandomAccessIterator>
  inline void
  sort(_RandomAccessIterator __first,
  _RandomAccessIterator __last)
  {
  ……
  }

    template<typename _RandomAccessIterator,
                    typename _Compare>
    inline void
    sort(_RandomAccessIterator __first,
          _RandomAccessIterator __last,
          _Compare __comp)
    {
      ……
    }
  

• 采用GP：
  (1). Containers和Algorithms团队可各自闭门造车，其间以iterator贯通即可。
  (2). Algorithms和Iterators确定操作范围，并通过Iterators取用Container元素。

• 结构说明图如下所示：

  
  
  GP采用结构

• 代码示例如下所示：

  
  
  GP示例程序

2 模板(泛化，全特化，偏特化)

• Class Templates类模板：
  template<typename T>
  class complex
  {
  public:
  Complex(T r = 0, T i = 0):re(r), im(i) { }
  T real() const { return re; }
  T imag() const { return im; }
  private:
  T re, im;
  friend Complex& __doapl(complex*, const complex&);
  };

• 模板类使用

    {
            complex<double> c1(2.5, 1.5);
            complex<int> c2(2, 6);
    }
  

• Function Templates函数模板

    stone r1(2, 3), r2(3, 3), r3;
    r3 = min(r1, r2);
  

• 编译器对function template进行实参推导(argument deduction)

    template<class T>
    inline const T& min(const T& a, const T& b)
    {
            return b < a ? b : a;
    }
  

• 实参推导的结果，T为stone，于是调用stone::operator<()

    class stone
    {
    public:
            stone(int w, int h, int we):_w(w), _h(h), _weight(we) { }
            bool operator<(const stone& rhs) const
            {
                    return _weight < ths._weight;
            }
    private:
          int _w, _h, _weight;
    };
  

• Member Templates，成员模板

    template<class T1, class T2>
    struct pair
    {
            typedef T1 first_type;
            typedef T2 second_type;
            T1 first;
            T1 second;
            pair() : first(T1()), second(T2()) { }
            pair(const T1& a, const T2& b) : first(a), second(b) { }
      #ifdef __STL_MEMBER_TEMPLATES
            template<class U1, class U2>
            pair(const pair<U1, U2>& p) : first(p.first), second(p.second) { }
      #endif
    };
  

• generalization，泛化

    struct __true_type { };
    struct __false_type { };
  
    template<class type>
    struct __type_trait
    {
            typedef __true_type this_dummy_number_must_be_first;
            typedef __false_type has_trivial_default_constructor;
            typedef __false_type has_trivial_copy_constructor;
            typedef __false_type has_trivial_assignment_operator;
            typedef __false_type has_trivial_destructor;
            typedef __false_type is_POD_type;
    };
  

• Specialization，特化

    template<>
    struct __type_trait<int>
    {
            typedef __false_type has_trivial_default_constructor;
            typedef __false_type has_trivial_copy_constructor;
            typedef __false_type has_trivial_assignment_operator;
            typedef __false_type has_trivial_destructor;
            typedef __false_type is_POD_type;
    };
  
    template<>
    struct __type_trait<double>
    {
            typedef __false_type has_trivial_default_constructor;
            typedef __false_type has_trivial_copy_constructor;
            typedef __false_type has_trivial_assignment_operator;
            typedef __false_type has_trivial_destructor;
            typedef __false_type is_POD_type;
    };
  

• Partial Specialization，偏特化
  

  偏特化代码示例

3 分配器

• 1. 分配器allocator在vc6.0下的实现如下所示：
     
     allocator实现

• VC6.0的allocator只是以::operator new和::operator delete完成allocate()和deallocate，没有任何特殊的设计。

• 其中int *p = allocator<int>().allocate(512, (int*)0); allocator<int>().deallocate(p, 512);表示利用allocate分配得到了一个指针p存放了512个int，利用deallocate归返了指针p。allocator<int>()表示产生了一个临时对象。

• 2. 分配器allocator在Borland C++下的实现如下所示：
     
     allocator实现

• Borland C++的allocator只是以::operator new和::operator delete完成allocate()和deallocate，没有任何特殊的设计。

• 3. 分配器allocator在G2.9下的实现如下所示：
     
     allocator实现
     
     注意：右边的注解说明G2.9中没有使用该分配器，而是使用了SGI的STL分配器。

• G2.9 STL对 allocator的使用如下图所示：
  

  allocator使用

• 其中使用的分配器名字为alloc，而不是像其他库中使用了allocator。

• G2.9的alloc实现如下：
  

  alloc实现

4 容器之间实现关系与分类

• 本图以缩排形式表达“基层与衍生层”的关系。这里的衍生层并非继承(inheritance)而是复合(composition)。

  
  
  容器结构分类图

• 容器及其迭代器的sizeof()大小

  
  
  容器和迭代器大小

5 深度探索list

• 容器list的结构和实现如下图所示：
  
  结构和实现代码
• list的迭代器interator实现如下：
  
  iterator实现
• iterator++和++iterator的实现说明：
  
  iterator++和++iterator

6 迭代器的设计原则和interator traits的作用与设计

• iterator需要遵循的原则
  
  iterator原则
• 其中traits需要的五个accociated types，如下所示：
  
  associate types
• iterator Traits用以分离class iterators和non-class iterators
  
  Iterator Traits

不同iterator的iterator traits

• 完整的iterator_traits
  
  iterator_traits