STL是C++重要的組件之一，大學時看過《STL源碼剖析》這本書，這幾天復習了一下，總結出以下LZ認為比較重要的知識點，內容有點略多 :)
STL提供六大組件，彼此可以組合套用：
STL六大組件的交互關系
一些可能令人困惑的C++語法糖：
STL的中心思想是：將數據容器和算法分隔開，彼此獨立設計，最後再用黏合劑將它們撮合在一起。容器和算法的泛型化，可以用C++的class template和function template來實現，而二者的黏合劑就是迭代器了。
與其說迭代器是一種指針，不如說迭代器是一種智能指針，它將指針進行了一層封裝，既包含了原生指針的靈活和強大，也加上很多重要的特性，使其能發揮更大的作用以及能更好的使用。迭代器對指針的一些基本操作如*、->、++、==、!=、=進行了重載，使其具有了遍歷復雜數據結構的能力，其遍歷機制取決於所遍歷的數據結構。下面上一段代碼，了解一下迭代器的“智能”：
template<typename T>
class Iterator
{
public:
Iterator& operator++();
//...
private:
T *m_ptr;
};
對於不同的數據容器，以上Iterator類中的成員函數operator++的實現會各不相同，例如，對於數組的可能實現如下：
//對於數組的實現
template<typename T>
Iterator& operator++()
{
++m_ptr;
retrun *this;
}
對於鏈表，它會有一個類似於next的成員函數用於獲取下一個結點，其可能實現如下：
//對於鏈表的實現
template<typename T>
Iterator& operator++()
{
m_ptr = m_ptr->next();//next()用於獲取鏈表的下一個節點
return *this;
}
iterator首先要對iterator指向對象的實現細節有非常豐富的了解，所以iterator為了不暴露所指向對象的信息，干脆就將iterator的實現由各個容器的設計者來實現好了。STL將迭代器的實現交給了容器，每種容器都會以嵌套的方式在內部定義專屬的迭代器。各種迭代器的接口相同，內部實現卻不相同，這也直接體現了泛型編程的概念。
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main(int argc, const char *argv[])
{
int arr[5] = { 1, 2, 3, 4, 5 };
vector<int> iVec(arr, arr + 5);//定義容器vector
list <int> iList(arr, arr + 5);//定義容器list
//在容器iVec的頭部和尾部之間尋找整形數3
vector<int>::iterator iter1 = find(iVec.begin(), iVec.end(), 3);
if (iter1 == iVec.end())
cout << "3 not found" << endl;
else
cout << "3 found" << endl;
//在容器iList的頭部和尾部之間尋找整形數4
list<int>::iterator iter2 = find(iList.begin(), iList.end(), 4);
if (iter2 == iList.end())
cout << "4 not found" << endl;
else
cout << "4 found" << endl;
system("pause");
return 0;
}
從上面迭代器的使用中可以看到，迭代器依附於具體的容器，即不同的容器有不同的迭代器實現，同時，我們也看到，對於算法find來說，只要給它傳入不同的迭代器，即可對不同的容器進行查找操作。通過迭代器的穿針引線，有效地實現了算法對不同容器的訪問，這也是迭代器的設計目的。
所謂序列式容器，其中的元素都可序，但未必有序，C++本身內建了一個序列式容器array，STL另外提供了vector、list、deque、stack、queue、priority-queue等序列式容器。其中stack和queue由於只是deque改頭換面而來，技術上被歸為一種配接器 (adapter)。
vector采用的數據結構非常簡單：線性連續空間。它以兩個迭代器start和finish分別指向配置得來的連續空間中目前已被使用的范圍，並以迭代器end_of_storage指向整塊連續空間(含備用空間)的尾端。
template <class T, class Alloc = alloc>
class vector {
...
protected:
iterator start; //表示
iterator finish;
iterator end_of_storage;
...
};
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> a(5, 0); //16
cout << sizeof(a) << endl;
cout << (int)(void *)&a << endl;
cout << (int)(void *)&a[0] << endl;
cout << (int)(void *)&a[a.size() - 1] << endl;
cout << endl;
cout << *((int *)&a) << endl;
cout << *(((int *)&a) + 1) << endl;
cout << *(((int *)&a) + 2) << endl;
cout << *(((int *)&a) + 3) << endl;
cout << endl;
cout << a.size() << endl;
cout << a.capacity() << endl;
system("pause");
return 0;
}
測試結果顯示此時vector的大小為16字節，分別包括start、finish、end_of_storage成員，剩下的4個字節暫時不知道代表什麼意思… :(
測試環境：Ubuntu12.04 codeblocks10.05
測試代碼：
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> a(5, 0); //12
cout << sizeof(a) << endl;
cout << (int)(void *)&a << endl;
cout << (int)(void *)&a[0] << endl;
cout << (int)(void *)&a[a.size() - 1] << endl;
cout << endl;
cout << *((int *)&a) << endl;
cout << *(((int *)&a) + 1) << endl;
cout << *(((int *)&a) + 2) << endl;
cout << *(((int *)&a) + 3) << endl;
cout << endl;
cout << a.size() << endl;
cout << a.capacity() << endl;
return 0;
}
測試結果顯示此時vector的大小為12字節，包括start、finish、end_of_storage成員
小結
win和Ubuntu所用的STL的版本是不一樣的，不同的STL所使用的vector類也不同，有著不同的容器管理方式。
相對於vector的連續線性空間，list就顯得復雜許多，它的好處就是插入或刪除一個元素，就配置或刪除一個元素空間。對於任何位置的元素的插入或刪除，list永遠是常數時間。
list本身和節點是不同的結構，需要分開設計。以下是STL list的節點node結構：
template <class T>
class __list_node {
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
這是一個雙向鏈表
list數據結構
SGI list不僅是一個雙向鏈表，而且是一個環狀雙向鏈表。只需一個指針就可遍歷整個鏈表。
deque和vector的最大差異，一在於deque允許常數時間內對起頭端進行插入或移除操作，二在於deque沒有所謂容量(capacity)概念，因為它是以分段連續空間組合而成，隨時可以增加一段新的空間連接起來。
deque由一段一段連續空間組成，一旦有必要在deque的前端或尾端增加新空間，便配置一段連續空間，串接在整個deque的前端或尾端。deque的最大任務，便是在這些分段的連續空間上，維護其整體連續的假象，並提供隨機存取的接口，避開了“重新配置、復制、釋放”的輪回，代價是復雜的迭代器結構。
迭代器首先必須指出分段連續空間在哪裡，其次它必須能夠判斷自己是否已經處在緩沖區的邊緣，如果是，一旦前進或後退就必須跳躍下一個緩沖區，為了能夠正常跳躍，deque必須隨時掌握管控中心。
迭代器結構：
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator { // 未繼承 std::iterator
// 保持迭代器的連接
T* cur; // 此迭代器所指之緩沖區的現行（ current）元素
T* first; // 此迭代器所指之緩沖區的的頭
T* last; // 此迭代器所指之緩沖區的的尾（含備用空間）
map_pointer node; // 指向管控中心
...
};
假如deque中已經包含了20個元素了，緩沖區大小為8，則內存布局如下：
注意：deque最初狀態(無任何元素)保有一個緩沖區，因此，clear()完成之後回到初始狀態，也一樣會保留一個緩沖區。
tack是一種先進後出(First In Last Out，FILO)的數據結構，它只有一個出口。stack允許增加元素、移除元素、取得最頂端元素。但除了最頂端外，沒有任何其他方法可以存取，stack的其他元素，換言之，stack不允許有遍歷行為。stack默認以deque為底層容器。
queue是一種先進先出(First In First Out，FIFO)的數據結構，它有兩個出口，允許增加元素、移除元素、從最底端加入元素、取得最頂端元素。但除了最底端可以加入、最頂端可以取出外，沒有任何其他方法可以存取queue的其他元素，換言之，queue不允許有遍歷行為。queue默認以deque為底層容器。
heap並不歸屬於STL容器組件，它是個幕後英雄，扮演prority queue的助手。priority queue允許用戶以任何次序將任何元素推入容器內，但取出時一定是按照優先級最高的元素開始取。binary max heap正好具有這樣的特性，適合作為priority queue的底層機制。heap默認建立的是大堆。
heap測試用例：
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
template <class T>
struct display
{
void operator()(const T &x)
{
cout << x << " ";
}
};
/// heap默認為大堆，以下設置為建立小堆
template <typename T>
struct greator
{
bool operator()(const T &x, const T &y)
{
return x > y;
}
};
int main(void)
{
int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
vector<int> ivec(ia, ia + 9);
make_heap(ivec.begin(), ivec.end(), greator<int>()); //注意：此函數調用時，新元素應已止於底部容器的尾端
for_each(ivec.begin(), ivec.end(), display<int>());
cout << endl;
ivec.push_back(7);
push_heap(ivec.begin(), ivec.end(), greator<int>());
for_each(ivec.begin(), ivec.end(), display<int>());
cout << endl;
pop_heap(ivec.begin(), ivec.end(), greator<int>());
cout << ivec.back() << endl;
ivec.pop_back();
for_each(ivec.begin(), ivec.end(), display<int>());
cout << endl;
sort_heap(ivec.begin(), ivec.end(), greator<int>());
for_each(ivec.begin(), ivec.end(), display<int>());
cout << endl;
system("pause");
return 0;
}
priority_queue是一個擁有權值的queue，它允許加入新元素、移除舊元素、審視元素值等功能。由於是一個queue，所以只允許在底端加入元素，從頂端取出元素，除此之外別無其他存取元素方法。priority_queue內的元素並非按照被推入的順序排列，而是自動按照元素的權值排列。權值最高者排在前面。
默認情況下priority_queue利用max-heap按成，後者是一個以vector為底層容器的complate binary tree。
priority_queue測試用例：
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(void)
{
int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
vector<int> ivec(ia, ia + 9);
priority_queue<int> ipq(ivec.begin(), ivec.end());
ipq.push(7);
ipq.push(23);
while (!ipq.empty())
{
cout << ipq.top() << " ";
ipq.pop();
}
cout << endl;
system("pause");
return 0;
}
set和map底層數據結構都是紅黑樹，紅黑樹的data域段為pair<key, value>類型。關於紅黑樹更多知識請點擊：深入理解紅黑樹。
set的所有元素都會根據元素的鍵值自動排序。set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，set不允許有兩個相同的元素。Set元素不能改變，在set源碼中，set<T>::iterator被定義為底層TB-tree的const_iterator，杜絕寫入操作，也就是說，set iterator是一種constant iterators(相對於mutable iterators)
測試用例(讓set從大到小存放元素)：
#include <iostream>
#include <set>
#include <functional>
using namespace std;
/// set默認是從小到大排列，以下是讓set從大到小排列
template <typename T>
struct greator
{
bool operator()(const T &x, const T &y)
{
return x > y;
}
};
int main(void)
{
set<int, greator<int>> iset;
iset.insert(12);
iset.insert(1);
iset.insert(24);
for (set<int>::const_iterator iter = iset.begin(); iter != iset.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
system("pause");
return 0;
}
map的所有元素都會根據元素的鍵值自動排序。map的所有元素都是pair，同時擁有實值(value)和鍵值(key)。pair的第一元素為鍵值，第二元素為實值。map不允許有兩個相同的鍵值。
如果通過map的迭代器改變元素的鍵值，這樣是不行的，因為map元素的鍵值關系到map元素的排列規則。任意改變map元素鍵值都會破壞map組織。如果修改元素的實值，這是可以的，因為map元素的實值不影響map元素的排列規則。因此，map iterator既不是一種constant iterators，也不是一種mutable iterators。
測試用例(map從大到小存放元素)：
#include <iostream>
#include <string>
#include <map>
#include <functional>
using namespace std;
/// map默認是從小到大排列，以下是讓map從大到小排列
template <typename T>
struct greator
{
bool operator()(const T x, const T y)
{
return x > y;
}
};
int main(void)
{
map<int, string, greator<int>> imap;
imap[3] = "333";
imap[1] = "333";
imap[2] = "333";
for (map<int, string>::const_iterator iter = imap.begin(); iter != imap.end(); iter++)
{
cout << iter->first << ": " << iter->second << endl;
}
system("pause");
return 0;
}
multiset的特性以及用法和set完全相同，唯一的差別在於它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique()。
multimap的特性以及用法和map完全相同，唯一的差別在於它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique()。
二叉搜索樹具有對數平均時間表現，但這樣的表現構造在一個假設上：輸入數據有足夠的隨機性。hashtable這種結構在插入、刪除、查找具有“常數平均時間”，而且這種表現是以統計為基礎，不需依賴元素的隨機性。
hashtable底層數據結構為分離連接法的hash表，如下所示：
hashtable中的buckets使用的是vector數據結構，當插入一個元素時，找到該插入哪個buckets的插槽，然後遍歷該插槽指向的鏈表，如果有相同的元素，就返回；否則的話就將該元素插入到該鏈表的頭部。(當然，如果是multi版本的話，是可以插入重復元素的，此時插入過程為：當插入一個元素時，找到該插入哪個buckets的插槽，然後遍歷該插槽指向的鏈表，如果有相同的元素，就將新節點插入到該相同元素的後面；如果沒有相同的元素，產生新節點，插入到鏈表頭部)
當調用成員函數clear()後，buckets vector並未釋放空間，仍保留原來大小，只是刪除了buckets所連接的鏈表。
hash_multimap插入式的圖示說明
運用set，為的是快速搜尋元素。這一點，不論其底層是RB-tree或是hashtable，都可以完成任務，但是，RB-tree有自動排序功能而hashtable沒有，即set的元素有自動排序功能而hash_set沒有。
測試代碼：
hash_map以hashtable為底層結構，由於hash_map所提供的操作接口，hashtable都提供了，所以幾乎所有的hash_map操作行為都是轉調用hashtable的操作行為結果。RB-tree有自動排序功能而hashtable沒有，反映出來的結果就是，map的元素有自動排序功能而hash_map沒有。
測試代碼：
hash_multiset的特性與multiset完全相同，唯一的差別在於它的底層機制是hashtable，因此，hash_multiset的元素是不會自動排序的。
hash_multimap的特性與multimap完全相同，唯一的差別在於它的底層機制是hashtable，因此，hash_multimap的元素是不會自動排序的。
hash_multimap測試用例：
#include <iostream>
#include <hash_map>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
template <typename T>
struct print
{
void operator()(const T &x)
{
cout << x.first << ": " << x.second << endl;
}
};
int main(void)
{
hash_multimap<int, string> hmap;
hmap.insert(pair<int, string>(2, "32"));
hmap.insert(pair<int, string>(2, "22"));
hmap.insert(pair<int, string>(2, "12"));
hmap.insert(pair<int, string>(2, "2"));
for_each(hmap.begin(), hmap.end(), print<pair<int, string>>());
return 0;
}
在vs2013(windows 7 64位)下運行結果為：
在Kali2.0中運行(程序需添加using namespace __gun_cxx)結果為：
由運行結果可知，不同的系統所用的STL是有差別的，不同的STL的hash_table沖突解決方法不一樣。
參考：
1、《STL源碼剖析》
2、http://blog.csdn.net/shudou/article/details/11099931
3、http://www.cplusplus.com/search.do?q=slist
