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>()表示产生了一个临时对象。
1. 分配器allocator在Borland C++下的实现如下所示：
  allocator实现
Borland C++的allocator只是以::operator new和::operator delete完成allocate()和deallocate，没有任何特殊的设计。
1. 分配器allocator在G2.9下的实现如下所示：
  allocator实现
  注意：右边的注解说明G2.9中没有使用该分配器，而是使用了SGI的STL分配器。
G2.9 STL对 allocator的使用如下图所示：

allocator使用
其中使用的分配器名字为alloc，而不是像其他库中使用了allocator。
G2.9的alloc实现如下：

alloc实现