OOP (Object-Oriented programming)

课件解析

template <class T, class Alloc = alloc>
class list {
...
void sort();
};

评论: OOP企图将datas和methods关联在一起, 例如std::list这个template class在其内部定义了sort这个member function来进行排序操作.

我们都知道标准库的algorithm头文件中提供了sort()这个generic algorithm, 为什么list不能使用::sort()排序呢?

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, 
                 RandomAccessIterator last) {
  if (first != last) {
    __introsort_loop(first, last, value_type(first),
                     __lg(last - first) * 2);
    __final_insertion_sort(first, last);
  }
}

template <class RandomAccessIterator, 
          class T, class Size>
void __introsort_loop(RandomAccessIterator first,
                      RandomAccessIterator last, 
                      T*, Size depth_limit) {
...
  RandomAccessIterator cut = 
    __unguarded_partition(first, last,
      T(__median(*first, *(first+(last-first)/2), *(last-1))));
...
}

评论: std::list由于其独特的迭代器设计，所以不能使用std::sort()，而自己设计了一个成员函数sort(). 具体的原因是std::sort默认传入的是RandomAccessIterator, 并在其内部函数中用到了*(first+(last-first)/2), 而std::list的Iterator是不能这么使用的(其空间非连续).

GP (Generic Programming)

课件解析
Data Structures (Containers):

template <class T, 
          class Alloc = alloc>
class vector {
...
};

template <class T, 
          class Alloc = alloc,
          size_t BufSiz = 0>
class deque {
...
};

Algorithms:

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将datas和methods分离开来, 这里不同的数据结构vector和deque都可以调用两种sort模板函数.

采用GP:

• Container和Algorithms团队可各自闭门造车, 其间以Iterator沟通即可;
• Algorithms通过Iterators确定操作范围, 并通过Iterator取用Container元素.

阅读C++标准库源码 必要基础 之 操作符重载

template <class T, class Ref, class Ptr>
struct __list_iterator {
  typename __list_iterator<T, Ref, Ptr> self;
  typename bidirectional_iterator_tag iterator_category;  // (1)
  typename T value_type;                                  // (2)
  typename Ptr pointer;                                   // (3)
  typename Ref reference;                                 // (4)
  typename __list_node<T>* link_type;
  typename ptrdiff_t difference_type;                     // (5)
};

• 关于operator overloading (操作符重载) (摘自C++ Primer):

Overloaded operators are functions with special names: the keyword operator followed by the symbol for the operator being defined. Like any other function, an overloaded operator has a return type, a parameter list, and a body.
An overloaded operator function has the same number of parameters as the operator has operands. A unary operator has one parameter; a binary operator has two. In a binary operator, the left-hand operand is passed to the first parameter and the right-hand operand to the second. Except for the overloaded function-call operator, operator(), an overloaded operator may not have default arguments.
If an operator function is a member function, the first (left-hand) operand is bound to the implicit this pointer. Because the first operand is implicitly bound to this, a member operator function has one less (explicit) parameter than the operator has operands.

阅读C++标准库源码 必要基础 之 模板

Class Templates, 类模板

template <typename T>
class complex {
 public:
  complex(T r = 0, T i = 0)
    : re(r), im(i)
  { }
  complex& operator += (const complex&);
  T real() const { return re; }
  T imag() const { return im; }
 private:
  T re, im;
  friend complex& __doapl(complex*, const complex&);
};

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

Function Template, 函数模板

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

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;
};

stone r1(2, 3), r2(3, 3), r3;
// 编译器对function template进行实参推到(argument deduction)
// 实参推导的结果, T为stone, 于是调用stone::operator<()
r3 = min(r1, r2);

Member Template, 成员模板

template<class T1, class T2>
struct pair
{
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;
  T2 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
};

Specialization，特化

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;  // Plain Old Data
};

// 特化1
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;
};

// 特化2
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;
};

关于模板特化(摘自C++ Primer):

Redefinition of a class template, a member of a class template, or a function template, in which some (or all) of the template parameters are specified. A template specialization may not appear until after the base template that it specializes has been declared. A template specialization must appear before any use of the template with the specialized arguments. Each template parameter in a function template must be completely specialized.

Partial Specialization, 偏特化

• 个数的偏:

template <class T, class Alloc = alloc>
class vector {
...
};

template <class Alloc = alloc>
class vector<bool, Alloc> {
...
};

• 范围的偏:

template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
};

// partial specialization for regular pointers
template <class T>
struct iterator_traits<T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T value_type;
  typedef ptrdiff difference_type;
  typedef T* pointer;
  typedef T& reference;
};

// partial specialization for regular const pointers
template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T value_type;
  typedef ptrdiff difference_type;
  typedef T* pointer;
  typedef T& reference;
};

关于模板偏特化(摘自C++ Primer):

Differently from function templates, a class template specialization does not have to supply an argument for every template parameter. We can specify some, but not all, of the template parameters or some, but not all, aspects of the parameters. A class template partial specialization is itself a template. Users must supply arguments for those template parameters that are not fixed by the specialization.

std::list

• 容器list的结构和实现如下图所示：

  
  
  list.png

• list的迭代器interator实现如下:

  
  
  list2.png

迭代器Iterator

• iterator需要遵循的原则

  
  
  iter1.png

• traits需要的五个accociated types，如下所示:

  
  
  iter2.png

• iterator Traits用以分离class iterators和non-class iterators

  
  
  iter3.png

• iterator Traits用以分离class iterators和non-class iterators

  
  
  iter4.png

• 完整的iteraotr_traits

  
  
  iter5.png

关于Iterator Traits (摘自The C++ Programming Language)

In <iterator> , the standard library provides a set of type functions that allow us to write code specialized for specific properties of an iterator: