C++ STL與泛型編程-第二篇（Boolan）

本章內(nèi)容：
1 OOP(面向?qū)ο缶幊? vs. GP(泛型編程)
2 模板(泛化，全特化，偏特化)
3 分配器
4 容器之間實(shí)現(xiàn)關(guān)系與分類
5 深度探索list
6 迭代器的設(shè)計(jì)原理和interator traits的作用與設(shè)計(jì)

1 OOP(面向?qū)ο缶幊? vs. GP(泛型編程)

OOP企圖將datas和methods關(guān)聯(lián)在一起。
list不能使用全局的::sort()進(jìn)行排序，因?yàn)槿?code>sort()中用到了RandomAccessIterator，而list沒(méi)有該迭代器，只有當(dāng)有RandomAccessIterator時(shí)才能進(jìn)行全局的排序操作。
GP卻是將datas和methods分開(kāi)來(lái)。
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團(tuán)隊(duì)可各自閉門造車，其間以iterator貫通即可。
(2). Algorithms和Iterators確定操作范圍，并通過(guò)Iterators取用Container元素。
結(jié)構(gòu)說(shuō)明圖如下所示：

GP采用結(jié)構(gòu)
代碼示例如下所示：

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函數(shù)模板

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

編譯器對(duì)function template進(jìn)行實(shí)參推導(dǎo)(argument deduction)

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

實(shí)參推導(dǎo)的結(jié)果，T為stone，于是調(diào)用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下的實(shí)現(xiàn)如下所示：
  
  allocator實(shí)現(xiàn)
VC6.0的allocator只是以::operator new和::operator delete完成allocate()和deallocate，沒(méi)有任何特殊的設(shè)計(jì)。
其中int *p = allocator<int>().allocate(512, (int*)0); allocator<int>().deallocate(p, 512);表示利用allocate分配得到了一個(gè)指針p存放了512個(gè)int，利用deallocate歸返了指針p。allocator<int>()表示產(chǎn)生了一個(gè)臨時(shí)對(duì)象。
1. 分配器allocator在Borland C++下的實(shí)現(xiàn)如下所示：
  
  allocator實(shí)現(xiàn)
Borland C++的allocator只是以::operator new和::operator delete完成allocate()和deallocate，沒(méi)有任何特殊的設(shè)計(jì)。
1. 分配器allocator在G2.9下的實(shí)現(xiàn)如下所示：
  
  allocator實(shí)現(xiàn)
  
  注意：右邊的注解說(shuō)明G2.9中沒(méi)有使用該分配器，而是使用了SGI的STL分配器。
G2.9 STL對(duì) allocator的使用如下圖所示：

allocator使用
其中使用的分配器名字為alloc，而不是像其他庫(kù)中使用了allocator。
G2.9的alloc實(shí)現(xiàn)如下：

alloc實(shí)現(xiàn)