C++ 標準模板庫組件介紹
在前幾天的阿里面試過程中，問到了我標準模板庫的繼承體系。平時開發對vector,list, map,set ,stack等容器用的比較多，但是沒有深入研究過。經歷過面試，發現了很多需要完善和提高的地方。
但是有個問題哦，標準模板庫中得幾大組件沒有啥繼承關系，只是說有某些容器之間有適配關系。
Container(容器):
所謂容器，就是存放數據的倉庫，定義了數據在內存中的組織方式，主要：有序列式容器（線性數據結構）、關聯連式容器（非線性數據結構：樹結構）
序列容器，典型的容器vector，相對于C++內嵌的數組，vector的優點是支持數據的動態擴展。
而空間的動態擴展，有空間配置器配置。它會為容器提供空間分配的策略，比如空間不夠時增長的幅度。
關聯式容器：關聯式容器的思想類似于關系數據庫，由key-value組成。 主要分為map和set，hash及其相關衍生.
Iteraotrs(迭代器)：
迭代器統一了容器的訪問操作，很好的東西。想到了迭代器模式 Container<Type> cons;
for (Container<Type>::iterator iter = cons.begin();
iter != cons.end(); iter++)
{
visit(iter);
} 看看《STL源碼分析》中關于vector的定義
template<class T, class Alloc = alloc>
class vector
{
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
......
}
這里很明顯的是通過宏定義將指針定義為vector的迭代器，提供統一訪問，但是本質上還是指針哈。
VC的vector的迭代器定義：是一個類哈，有許多數據組成了迭代器的定義，其中有指針，有引用。
template<class _Myvec>
class _Vector_iterator
: public _Vector_const_iterator<_Myvec>
{ // iterator for mutable vector
public:
typedef _Vector_iterator<_Myvec> _Myiter;
typedef _Vector_const_iterator<_Myvec> _Mybase;
typedef random_access_iterator_tag iterator_category;
typedef typename _Myvec::value_type value_type;
typedef typename _Myvec::difference_type difference_type;
typedef typename _Myvec::pointer pointer;
typedef typename _Myvec::reference reference;
......
}</pre>
pointer定義，就是某個數據類型的指針
typedef value_type _FARQ *pointer;
再看下hashtable中的迭代器的定義：
......
struct _hashtable_iterator
{
......
node* cur;
hashtable* ht;
.....
}
在hashtable迭代器中，有兩個指針，一是當前節點的指針，二是buckets vector的指針。
綜上所述，所謂迭代器，就是對指針以及其他輔助信息的一個封裝。對數據的訪問一定是通過地址訪問，地址是必須的，所以地址是迭代器中不可缺少的信息。
在迭代器的使用中，常常遇到的一個問題就是，在進行數據的插入刪除時的失效問題！其實就是指針的問題哈
Allocator(空間配置器)：
空間配置器用于屏蔽容器關于內存管理的細節。比如容器內存的申請釋放，當內存不夠時采用怎樣的一種策略。在我們平常的使用中，
vector<strudent> stus;
并沒有制定容器的空間配置方案，于是采用默認的配置方案，其實我們是可以自己編寫空間配置方案，并將該方案實施于某個容器。(CustomAlloc是自定義的命名空間，并實現了空間配置方案allocator)
vector<int, CustomAlloc::allocator<int>> datas;
可以在自定義的方案中進行內存管理。
Algorithms(算法)：
提供了大量常用、通過的算法，比如比較、查詢、數據移動、復制、交換等等。
基礎算法：min, max, swap
排序：sort
替換：replace
查找：find
此處不一一列舉
Function Objects（函數對象）：
函數對象，簡單的理解就是將一個函數封裝為對象，但是它的作用是為容器的操作提供依據。我進行比較大小，根據什么比，函數對象提供，查詢，匹配的規則是什么，函數對象提供。
例如：
- 對vector容器進行排序，排序的標準是？
對容器中得數據進行查詢，查詢的標準是？
通過函數對象，可以靈活的編寫操作依據，并注入到操作函數中。
為sort函數編寫Compare()
為find_if編寫Query()
此處寫了個實例，說明一下用法：
業務對象定義：
class student
{
public:
string name;
int age;
student(string name, int age)
{
this->name = name;
this->age = age;
}
student(const student &stu)
{
*this = stu;
}
student& operator=(const student &stu)
{
this->name = stu.name;
this->age = stu.age;
return *this;
}
};
函數對象定義，說明對象之間比較的依據，此處依據是年齡
struct Compare : public std::binary_function<student, student, bool>
{
bool operator()(const student stu1, const student stu2) const
{
if (stu1.age < stu2.age)
return true;
else
return false;
}
};
測試程序：
int _tmain(int argc, _TCHAR* argv[])
{
vector<student> stus;
srand((unsigned int)time(NULL));
string strName = "student";
for (int i = 0; i < 10; i++)
{
int val = rand()/10;
char dataBuf[20];
memset(dataBuf, 0, 20);
itoa(val, dataBuf, 10);
student stu(dataBuf, val);
stus.push_back(stu);
}
for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++)
cout<<iter->name<<"--"<< iter->age<<endl;
cout<<"-----------------------------"<<endl;
sort(stus.begin(), stus.end(), Compare());
for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++)
cout<<iter->name<<"--"<< iter->age<<endl;
getchar();
return 0;
}
測試結果：將原本隨機插入的數據根據年齡進行了排序
注：此處是對幾個組件的簡要說明，并未詳細深入
轉自：http://my.oschina.net/myspaceNUAA/blog/78557
jopen 
document_w 
zoopnin 
dewen2006