【STL和泛型編程】3. set、map分析（及typename起源）
前置知識(shí)：紅黑樹原理 【數(shù)據(jù)結(jié)構(gòu)】7.平衡搜索樹（AVL樹和紅黑樹），紅黑樹的平衡性有利于 search 和 insert
- 紅黑樹的迭代器
- begin() 左側(cè)
- end() 右側(cè)
- 迭代順序 5 6 7 8 10 11 12 13 15
- 不能使用迭代器修改 Key 的值，例如將 6 改成 50 會(huì)破壞紅黑樹的性質(zhì)
1. RB-tree
在g++編譯器中（4.9），rbtree在 <bits/stl_tree.h> 中定義
// Key: key; Value: Key+Data; KeyOfValue: 從Value中取出Key 注意這里的Value是Key和Data結(jié)合起來傳入的類 // Compare: 比較Key大小的函數(shù) template <class Key, class Value, class KeyOfValue, class Compare, class Allocated = alloc> class _Rb_tree { protected: typedef __rb_tree_node<Value> rb_tree_node; public: typedef rb_tree_node* link_type; protected: size_type node_count; // 節(jié)點(diǎn)元素個(gè)數(shù) link_type header; // 頭節(jié)點(diǎn)指針，包括了Value, left, right, parent Compare key_compare; // key的大小比較函數(shù) };
- 使用案例，該rbtree的key就是value，獲取key的方式就是直接返回該元素
- rbtree._M_insert_unique(5); 插入元素（無重復(fù)）
- rbtree._M_insert_equal(5); 插入元素（可以重復(fù)），可以使用 .count(5) 計(jì)算數(shù)量
_Rb_tree<int, int, identity<int>, less<int>, alloc> rbtree; // identity 類重載了括號(hào)，直接返回該元素本身 template <class T> struct identity : public unary_function<T, T> { const T& operator()(const T& x) const { return x; } }; // less 重載了括號(hào)，比較大小后返回元素 template <class T> struct less : public binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x<y; } };
2. set / multiset
- set 提供遍歷操作以及迭代器 iterator，可以使用 ++ite 進(jìn)行遍歷，并且得到排序后的數(shù)據(jù)
- 無法使用迭代器修改元素值，修改值會(huì)導(dǎo)致破壞排序
- set insert 調(diào)用無重復(fù)插入方法，multiset insert 調(diào)用可重復(fù)插入的方法
template <class Key, class Compare = less<Key>, class Alloc = alloc> class set { public: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; prevate: typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t; // 實(shí)際存儲(chǔ)內(nèi)容的紅黑樹 public: typedef typename rep_type::const_iterator iterator; // 從set拿迭代器拿到的是 const_iterator，避免使用者使用迭代器修改元素 // ... };
2.1 typename
typedef typename rep_type::const_iterator iterator; // STL源碼的寫法 typedef rep_type::const_iterator iterator; // 這樣存在什么問題？
首先看類作用域下操作符 MyClass::name 調(diào)用實(shí)際上有 3 種可能：以MyClass為例子來說，MyClass::A靜態(tài)數(shù)據(jù)成員，MyClass::B靜態(tài)成員函數(shù)，MyClass::C嵌套類型。由于MyClass是一個(gè)完整的定義，所以編譯器完全可以推斷出任意一個(gè)變量究竟是什么類型的。但還有一種可能，如果是T::name呢？
class MyClass{ static int A; // 靜態(tài)變量A static int B(); // 靜態(tài)成員函數(shù)B typedef int C; // 嵌套類型C }
以foo函數(shù)為例子，一眼看下去它的含義是定義了T類中iterator的指針并起名為iter；如果傳入的是ContainsAType則完全沒有問題。但如果傳入的是ContainsAnotherType則會(huì)出現(xiàn)問題，因?yàn)樵谠擃愔卸x了靜態(tài)整形變量，如果有一個(gè)全局整形變量iter，則翻譯后這里就會(huì)變成一個(gè)乘法表達(dá)式，二義性是不能被允許的，所以委員會(huì)引入了typename關(guān)鍵字
模板類型實(shí)例化前，并不知道它具體是哪個(gè)類型，而使用typename 可以直接告訴編譯器這是一個(gè)類型，而非成員對(duì)象。
struct ContainsAType { struct iterator { /* ... */ } }; struct ContainsAnotherType { static int iterator; }; template <class T> void foo() { T::iterator * iter; // ... }
3. map / multimap
- map 提供遍歷操作以及迭代器 iterator，可以使用 ++ite 遍歷排序后的數(shù)據(jù)
- 無法使用迭代器修改 key，但允許修改 data（源碼實(shí)現(xiàn)很巧妙，借用 pair<const Key, T> 實(shí)現(xiàn)）
- map insert 調(diào)用無重復(fù)插入方法，multimap insert 調(diào)用可重復(fù)插入方法
- insert(pair<long, string>(1, "HelloWorld"); 插入時(shí)應(yīng)該插入一個(gè)pair
- map[5] = "Hi Five"; // 插入 (5, "Hi Five")
- map[5]; // 這個(gè)比較有趣，標(biāo)準(zhǔn)規(guī)定，如果沒有 Key 5, 則創(chuàng)建 Key 5 和 string 的默認(rèn)值
- 在multimap 不可以使用 multimap[]進(jìn)行插入
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; // value 是 const Key 和 Data 的結(jié)合 typedef Compare key_compare; prevate: typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; // 實(shí)際存儲(chǔ)內(nèi)容的紅黑樹 public: typedef typename rep_type::iterator iterator; // 因?yàn)閜air中是const key, 從而實(shí)現(xiàn)只能修改value不能修改key // ... };
浙公網(wǎng)安備 33010602011771號(hào)