C++ 标準模闆庫元件介紹

原文位址：http://my.oschina.net/myspaceNUAA/blog/78557

在前幾天的阿裡面試過程中，問到了我标準模闆庫的繼承體系。平時開發對vector,list, map,set ,stack等容器用的比較多，但是沒有深入研究過。經曆過面試，發現了很多需要完善和提高的地方。

但是有個問題哦，标準模闆庫中得幾大元件沒有啥繼承關系，隻是說有某些容器之間有适配關系。

Container(容器):

所謂容器，就是存放資料的倉庫，定義了資料在記憶體中的組織方式，

主要：有序列式容器（線性資料結構）、關聯連式容器（非線性資料結構：樹結構）

序列容器，典型的容器vector，相對于C++内嵌的數組，vector的優點是支援資料的動态擴充。

而空間的動态擴充，有空間配置器配置。它會為容器提供空間配置設定的政策，比如空間不夠時增長的幅度。

關聯式容器：關聯式容器的思想類似于關系資料庫，由key-value組成。 主要分為map和set，hash及其相關衍生.

Iteraotrs(疊代器)：

疊代器統一了容器的通路操作，很好的東西。想到了疊代器模式 view source print ?

1	Container<Type> cons;

2	for (Container<Type>::iterator iter = cons.begin();

3	iter != cons.end(); iter++)

4

{

5	visit(iter);

6

}

看看《STL源碼分析》中關于vector的定義

view source print ?

1	template < class T, class Alloc = alloc>

2	class vector

3

{

4	typedef T value_type;

5	typedef value_type* pointer;

6	typedef value_type* iterator;

7

......

8

}

這裡很明顯的是通過typedef定義将指針定義為vector的疊代器，提供統一通路，但是本質上還是指針哈。

VC的vector的疊代器定義：是一個類哈，有許多資料組成了疊代器的定義，其中有指針，有引用。

view source print ?

01	template < class _Myvec>

02	class _Vector_iterator

03	: public _Vector_const_iterator<_Myvec>

04	{   // iterator for mutable vector

05

public :

06	typedef _Vector_iterator<_Myvec> _Myiter;

07	typedef _Vector_const_iterator<_Myvec> _Mybase;

08	typedef random_access_iterator_tag iterator_category;

09

10	typedef typename _Myvec::value_type value_type;

11	typedef typename _Myvec::difference_type difference_type;

12	typedef typename _Myvec::pointer pointer;

13	typedef typename _Myvec::reference reference;

14

......

15

}

pointer定義，就是某個資料類型的指針

view source print ?

1	typedef value_type _FARQ *pointer;

再看下hashtable中的疊代器的定義：

view source print ?

1

......

2	struct _hashtable_iterator

3

{

4

......

5	node* cur;

6	hashtable* ht;

7

.....

8

}

在hashtable疊代器中，有兩個指針，一是目前節點的指針，二是buckets vector的指針。

綜上所述，所謂疊代器，就是對指針以及其他輔助資訊的一個封裝。對資料的通路一定是通過位址通路，位址是必須的，是以位址是疊代器中不可缺少的資訊。

在疊代器的使用中，常常遇到的一個問題就是，在進行資料的插入删除時的失效問題！其實就是指針的問題哈

Allocator(空間配置器)：

空間配置器用于屏蔽容器關于記憶體管理的細節。比如容器記憶體的申請釋放，當記憶體不夠時采用怎樣的一種政策。在我們平常的使用中，

view source print ?

1	vector<strudent> stus;

并沒有制定容器的空間配置方案，于是采用預設的配置方案，其實我們是可以自己編寫空間配置方案，并将該方案實施于某個容器。(CustomAlloc是自定義的命名空間，并實作了空間配置方案allocator)

view source print ?

1	vector< int , CustomAlloc::allocator< int >> datas;

可以在自定義的方案中進行記憶體管理。

Algorithms(算法)：

提供了大量常用、通過的算法，比如比較、查詢、資料移動、複制、交換等等。

基礎算法：min, max, swap

排序：sort

替換：replace

查找：find

此處不一一列舉

Function Objects（函數對象）：

函數對象，簡單的了解就是将一個函數封裝為對象，但是它的作用是為容器的操作提供依據。我進行比較大小，根據什麼比，函數對象提供，查詢，比對的規則是什麼，函數對象提供。 

例如：

1. 對vector容器進行排序，排序的标準是？

2. 對容器中得資料進行查詢，查詢的标準是？

通過函數對象，可以靈活的編寫操作依據，并注入到操作函數中。

為sort函數編寫Compare()

為find_if編寫Query()

此處寫了個執行個體，說明一下用法：

業務對象定義：

view source print ?

01	class student

02

{

03

public :

04	string name;

05

int age;

06

07	student(string name, int age)

08

{

09	this ->name = name;

10	this ->age = age;

11

}

12

13	student( const student &stu)

14

{

15	* this = stu;

16

}

17

18	student& operator=( const student &stu)

19

{

20	this ->name = stu.name;

21	this ->age = stu.age;

22	return * this ;

23

}

24

};

函數對象定義，說明對象之間比較的依據，此處依據是年齡

view source print ?

01	struct Compare : public std::binary_function<student, student, bool >

02

{

03	bool operator()( const student stu1, const student stu2) const

04

{

05	if (stu1.age < stu2.age)

06	return true ;

07

else

08	return false ;

09

}

10

};

測試程式：

view source print ?

01	int _tmain( int argc, _TCHAR* argv[])

02

{

03	vector<student> stus;

04	srand ((unsigned int ) time (NULL));

05	string strName = "student" ;

06	for ( int i = 0; i < 10; i++)

07

{

08	int val = rand ()/10;

09	char dataBuf[20];

10	memset (dataBuf, 0, 20);

11	itoa(val, dataBuf, 10);

12	student stu(dataBuf, val);

13	stus.push_back(stu);

14

}

15

16	for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++)

17	cout<<iter->name<< "--" << iter->age<<endl;

18	cout<< "-----------------------------" <<endl;

19	sort(stus.begin(), stus.end(),  Compare());

20	for (vector<student>::iterator iter = stus.begin(); iter != stus.end(); iter++)

21	cout<<iter->name<< "--" << iter->age<<endl;

22

23	getchar ();

24

return 0;

25

}

測試結果：将原本随機插入的資料根據年齡進行了排序

注：此處是對幾個元件的簡要說明，并未詳細深入