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是雙向開(kāi)口容器漫试，它模擬了一個(gè)連續(xù)的存儲(chǔ)空間(實(shí)質(zhì)為連續(xù)分段的容器)医清，其中buffer和元素結(jié)點(diǎn)設(shè)計(jì)如下圖所示：
stl3_1.png
其中buffer為deque的緩沖區(qū), 每個(gè)buffer可以存放多個(gè)元素結(jié)點(diǎn), 而每個(gè)buffer指針存放在vector容器中.
-
G2.9版的deque:
stl3_02.png -
deque的iterator (deque如何模擬連續(xù)空間, 全都是deque iterator的功勞):
stl3-03.png
每個(gè)iterator有四個(gè)指針: cur(當(dāng)前數(shù)據(jù)結(jié)點(diǎn)的指針)喊儡、first(buffer首指針)、last(buffer的尾指針)甩卓、node(node表示這個(gè)iterator在vector中的指針地址).
G2.9版queue:
G2.9版stack:
容器rb_tree
Red-Black tree (紅黑樹(shù)) 是平衡二元搜尋樹(shù) (balanced binary search tree) 中常被使用的一種. 平衡二元搜尋樹(shù)的特征: 排列規(guī)則有利于search 和 insert, 并保持適度平衡----無(wú)任何節(jié)點(diǎn)過(guò)深.
rb_tree提供"遍歷"操作及iterators. 按正常規(guī)則(++ite)遍歷, 便能獲得排序狀態(tài).
我們不應(yīng)使用rb_tree的iteraotr改變?cè)刂?因?yàn)樵赜衅鋰?yán)謹(jǐn)?shù)呐帕幸?guī)則). 編程層面(programming level)并未阻絕此事. 如此設(shè)計(jì)是正確的, 因?yàn)閞b_tree即將為set 和 map 服務(wù)(做為其底部支持), 而map允許元素的data 被改變, 只有元素的key才是不可被改變的.
rb_tree 提供兩種insertion操作: insert_unique() 和 insert_equal(). 前者表示節(jié)點(diǎn)的key一定在整個(gè)tree中獨(dú)一無(wú)二, 否則安插失敗弦聂；后者表示節(jié)點(diǎn)的key可重復(fù).
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 只有三筆資料表現(xiàn)自己
size_type node_count; // rb_tree的大小(節(jié)點(diǎn)數(shù)量)
link_type header;
Compare key_compare; // Key的大小比較準(zhǔn)則: 應(yīng)會(huì)是個(gè)function object
};
- 定義一個(gè)簡(jiǎn)單rb_tree class的對(duì)象:
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); // 不會(huì)有用, 因?yàn)檫@里是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
紅黑樹(shù)的特性 (摘自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為底層結(jié)構(gòu), 因此有"元素自動(dòng)排序"特性. 排序的依據(jù)是key, 而set/multiset元素的value和key合一: value就是key.
set/multiset提供"遍歷"操作及iterators. 按正常規(guī)則(++ite)遍歷, 便能獲得排序狀態(tài)(sorted).
我們無(wú)法使用set/multiset的iterator改變?cè)刂?因?yàn)閗ey有其嚴(yán)謹(jǐn)排列規(guī)則). set/multiset的iterator是其地步的RB tree的const iterator, 就是為了禁止user對(duì)元素賦值.
set元素的key必須獨(dú)一無(wú)二, 因此其insert()用的是rb_tree的insert_unique(). multiset元素的key可以重復(fù), 因此其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為底層結(jié)構(gòu)柳击， 因此有“元素自動(dòng)排序”特性。 排序的依據(jù)是key片习。
map/multimap提供"遍歷"操作及iterators捌肴。按正常規(guī)則（++ite）遍歷蹬叭， 便能獲得排序狀態(tài)（sorted）。
我們無(wú)法使用map/multimap的iterators改變?cè)氐膋ey（因?yàn)閗ey有其嚴(yán)謹(jǐn)排序規(guī)則）状知， 但可以用它來(lái)改變?cè)氐膁ata秽五。 因此map/multimap內(nèi)部自動(dòng)將user制定的key type設(shè)為const， 如此便能禁止user對(duì)元素的key賦值饥悴。
map元素的key必須獨(dú)一無(wú)二坦喘， 因此其insert（）用的是rb_tree的insert_unique(). multimap元素的key可以重復(fù)， 因此其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; }
};
