STL与泛型编程 week 3 (Boolan)

deque&queue和stack深度探索

deque的定义(C++ Primer):

Sequential container. Elements in a deque can be accessed by their positional index. Supports fast random access to elements. Like a vector in all respects except that it supports fast insertion and deletion at the front of the container as well as at the back and does not relocate elements as a result of insertions or deletions at either end.

• deque是双向开口容器，它模拟了一个连续的存储空间(实质为连续分段的容器)，其中buffer和元素结点设计如下图所示：

  
  stl3_1.png
  

  其中buffer为deque的缓冲区, 每个buffer可以存放多个元素结点, 而每个buffer指针存放在vector容器中.

• G2.9版的deque:

  
  stl3_02.png

• deque的iterator (deque如何模拟连续空间, 全都是deque iterator的功劳):

  
  stl3-03.png
  

  每个iterator有四个指针: cur(当前数据结点的指针)、first(buffer首指针)、last(buffer的尾指针)、node(node表示这个iterator在vector中的指针地址).

G2.9版queue:

stl3-04.png

G2.9版stack:

stl3-05.png

容器rb_tree

Red-Black tree (红黑树) 是平衡二元搜寻树 (balanced binary search tree) 中常被使用的一种. 平衡二元搜寻树的特征: 排列规则有利于search 和 insert, 并保持适度平衡----无任何节点过深.

rb_tree提供"遍历"操作及iterators. 按正常规则(++ite)遍历, 便能获得排序状态.

我们不应使用rb_tree的iteraotr改变元素值(因为元素有其严谨的排列规则). 编程层面(programming level)并未阻绝此事. 如此设计是正确的, 因为rb_tree即将为set 和 map 服务(做为其底部支持), 而map允许元素的data 被改变, 只有元素的key才是不可被改变的.

rb_tree 提供两种insertion操作: insert_unique() 和 insert_equal(). 前者表示节点的key一定在整个tree中独一无二, 否则安插失败；后者表示节点的key可重复.

G2.9版rb_tree:

template <class Key,
          class Value,
          class KeyOfValue,
          class Compare,
          class Alloc = alloc>
class rb_tree {
 protected:
  typedef  __rb_tree_node<Value> rb_tree_node;
  ...
 public:
  typedef rb_tree_node* link_type;
  ...
 protected:
  // RB-tree 只有三笔资料表现自己
  size_type node_count;  // rb_tree的大小(节点数量)
  link_type header;
  Compare key_compare;  // Key的大小比较准则: 应会是个function object
};

• 定义一个简单rb_tree class的对象:

template <class Arg, class Result>
struct unary_function {
  typedef Arg argument_type;
  typedef Result result_type;
};

template <class Arg1, class Arg2, class Result>
struct binary_function {
  typedef Arg1 first_argument_type;
  typedef Arg2 first_argument_type;
  typedef Result result_type;
};

template <class T>
struct identity : public unary_function<T, T> {
  const T& operator()(const T &x) const { return x; }
};

template <class T>
struct less : public binary_function <T, T, bool> {
  bool operator() (const T &x, const T &y) const 
  { return x < y; }
};

• 容器rb_tree的用例

rb_tree<int, int, identity<int>, less<int>> itree;
cout << itree.empty() << endl;  // 1
cout << itree.size() << endl;  // 0

itree.insert_unique(3);
itree.insert_unique(8);
itree.insert_unique(5);
itree.insert_unique(9);
itree.insert_unique(13);
itree.insert_unique(5);  // 不会有用, 因为这里是insert_unique()
cout << itree.empty() << endl;  // 0
cout << itree.size() << endl;  // 5
cout << itree.count(5) << endl;  // 1

itree.insert_equal(5);
itree.insert_equal(5);
cout << itree.size() << endl;  // 7, since using insert_equal().
cout << itree.count(5) << endl;  // 3

红黑树的特性 (摘自Introduction to algorithms)

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK . By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
Each node of the tree now contains the attributes color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL . We shall regard these NIL s as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.
A red-black tree is a binary tree that satisfies the following red-black properties:

• Every node is either red or black.
• The root is black.
• Every leaf ( NIL ) is black.
• If a node is red, then both its children are black.
• For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

容器set, multiset

set/multiset以rb_tree为底层结构, 因此有"元素自动排序"特性. 排序的依据是key, 而set/multiset元素的value和key合一: value就是key.

set/multiset提供"遍历"操作及iterators. 按正常规则(++ite)遍历, 便能获得排序状态(sorted).

我们无法使用set/multiset的iterator改变元素值(因为key有其严谨排列规则). set/multiset的iterator是其地步的RB tree的const iterator, 就是为了禁止user对元素赋值.

set元素的key必须独一无二, 因此其insert()用的是rb_tree的insert_unique(). multiset元素的key可以重复, 因此其insert()用的是rb_tree的insert_equal().

• G2.9版set:

template <class Key,
          class Compare = less<Key>,
          class Alloc = alloc>
class set {
 public:
  // typedefs:
  typedef Key key_type;
  typedef Key value_type;
  typedef Compare key_compare;
  typedef Compare value_compare;
 private:
  typedef rb_tree<key_type, value_type, 
                  identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t;
 public:
  typedef typename rep_type::const_iterator iterator;
...
};

容器map，multimap

map/multimap以rb_tree为底层结构， 因此有“元素自动排序”特性。 排序的依据是key。

map/multimap提供"遍历"操作及iterators。按正常规则（++ite）遍历， 便能获得排序状态（sorted）。

我们无法使用map/multimap的iterators改变元素的key（因为key有其严谨排序规则）， 但可以用它来改变元素的data。 因此map/multimap内部自动将user制定的key type设为const， 如此便能禁止user对元素的key赋值。

map元素的key必须独一无二， 因此其insert（）用的是rb_tree的insert_unique(). multimap元素的key可以重复， 因此其insert（）用的是rb_tree的insert_equal().

G2.9版map：

template <class Key,
          class T,
          class Compare = less<Key>,
          class Alloc = alloc>
class map {
 public:
  typedef Key key_type;
  typedef T data_type;
  typedef T mapped_type;
  typedef pair<const Key, T> value_type;
  typedef Compare key_compare;
 private:
  typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
  rep_type t;
 public:
  typedef typename rep_type::iterator iterator;
...
};

容器hashtable

• G2.9版hashtable:

template <class Value>
struct __hashtable_node {
  __hashtable_node *next;
  Value val;
};

template <class Value, class Key, class HashFun,
          class ExtractKey, class EqualKey
          class Alloc = alloc>
class hashtable {
 public:
  typedef HashFcn hasher;
  typedef EqualKey key_equal;
  typedef size_t size_type;

 private:
  hasher hash;
  key_equal equals;
  ExtractKey get_key;

  typedef __hashtable_node<Vlaue> node;

  vector<node*, Alloc> buckets;
  size_type num_elements;
 public:
  size_type bucket_count() const { return buckets.size(); }
};

template <class Value, class Key,
          class HashFcn, class ExtractKey,
          class EqualKey, class Alloc>
struct __hashtable_iterator {
...
  mode *cur;
  hashtable *ht;
};

• hashtable用例:

struct eqstr {
  bool operator()(const char *s1, const char *s2) const
  { return strcmp(s1, s2) == 0; }
};

hashtable <const char*,
           const char*,
           hash<const char*>,
           identity<const char*>,
           eqstr,
           alloc>
ht(50, hash<const char*>(), eqstr());

ht.insert_unique("kiwi");
ht.insert_unique("plum");
ht.insert_unique("apple");

hash-function, hash-code

// 泛化
template <class Key> struct hash { };

// 特化
template <> struct hash <char> {
  size_t operator() (char x) const { return x; }
};

template <> struct hash <short> {
  size_t operator() (short x) const { return x; }
};

template <> struct hash <unsigned short> {
  size_t operator() (unsigned short x) const { return x; }
};

template <> struct hash <int> {
  size_t operator() (int x) const { return x; }
};

template <> struct hash <unsigned int> {
  size_t operator() (unsigned int x) const { return x; }
};

template <> struct hash <long> {
  size_t operator() (long x) const { return x; }
};

template <> struct hash <unsigned long> {
  size_t operator() (unsigned long x) const { return x; }
};