一,、STL中六大組件：

1）容器（Container）,，是一種數(shù)據(jù)結構，如list,，vector,，和deques ，以模板類的方法提供,。為了訪問容器中的數(shù)據(jù),，可以使用由容器類輸出的迭代器；

2）迭代器（Iterator）,，提供了訪問容器中對象的方法,。例如，可以使用一對迭代器指定list或vector中的一定范圍的對象,。迭代器就如同一個指針。事實上,，C++的指針也是一種迭代器,。但是，迭代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對象,。迭代器實際上也是一種將operator*,、operator->、operator++,、operator--等指針相關操作予以重載的class template

3）算法（Algorithm）,，是用來操作容器中的數(shù)據(jù)的模板函數(shù)。例如，STL用sort()來對一個vector中的數(shù)據(jù)進行排序,，用find()來搜索一個list中的對象,，函數(shù)本身與他們操作的數(shù)據(jù)的結構和類型無關，因此他們可以在從簡單數(shù)組到高度復雜容器的任何數(shù)據(jù)結構上使用,；

4）仿函數(shù)（Function object） ,，行為類似函數(shù)，可作為算法的某種策略,。從實現(xiàn)角度看,，仿函數(shù)是一種重載了operator（）的class或class template。一般函數(shù)指針可視為狹義的仿函數(shù),。

5）迭代適配器（Adaptor）,，一種用來修飾容器、仿函數(shù),、迭代器接口的東西,。STL提供的的queue和stack，雖然看似容器,，其實只能算是一種容器配接器,，因為他們的弟弟不完全借助deque，所有操作都由底層deque提供,。

6）配置器（allocator）,，負責空間配置與管理。實現(xiàn)了動態(tài)空間配置,，空間管理,，空間釋放的class template。

7）六大組件的交互關系：容器通過空間配置器取得數(shù)據(jù)存儲空間,，算法通過迭代器取得容器的內(nèi)容,，仿函數(shù)可以協(xié)助空間配置器完成不同的策略變化，適配器可以修飾或套接仿函數(shù),。

二,、底層數(shù)據(jù)結構的實現(xiàn)

1.vector       底層數(shù)據(jù)結構為數(shù)組 ，支持快速隨機訪問,。

2.list            底層數(shù)據(jù)結構為雙向鏈表,，支持快速增刪。

3.deque       底層數(shù)據(jù)結構為一個中央控制器和多個緩沖區(qū),，支持首尾（中間不能）快速增刪,，也支持隨機訪問，看起來像是list和vector的結合品,。

4.stack        底層一般用list或deque實現(xiàn),，封閉頭部即可,，不用vector的原因應該是容量大小有限制，擴容耗時,。

5.queue     底層一般用list或deque實現(xiàn),，封閉頭部即可，不用vector的原因應該是容量大小有限制,，擴容耗時,。

（stack和queue其實是適配器,而不叫容器，因為是對容器的再封裝）

6.priority_queue     底層數(shù)據(jù)結構一般為vector為底層容器,，堆heap為處理規(guī)則來管理底層容器實現(xiàn),。

7.set                   底層數(shù)據(jù)結構為紅黑樹，有序,，不重復

8.multiset            底層數(shù)據(jù)結構為紅黑樹,，有序，可重復 

9.map                 底層數(shù)據(jù)結構為紅黑樹,，有序,，不重復

10.multimap      底層數(shù)據(jù)結構為紅黑樹，有序,，可重復

11.hash_set         底層數(shù)據(jù)結構為hash表,，無序，不重復

12.hash_multiset   底層數(shù)據(jù)結構為hash表,，無序,，可重復

13.hash_map       底層數(shù)據(jù)結構為hash表，無序,，不重復

14.hash_multimap  底層數(shù)據(jù)結構為hash表,，無序，可重復 

三,、容器（Container）

1,、STL的容器種類

（1）序列式容器(Sequence container)， 這是- .種有序(ordered) 集合,，其內(nèi)每個元素均有確鑿的位置一-取決 于插人時機和地點,，與元素值無關。如果你以追加方式對一.個集合置人6個元素,，它們的排列次序將和置人次序- -致,。STL 提供了5個定義好的序列式容器: array. vector、 deque,、 list 和forward_ list。

（2）關聯(lián)式容器(Associative container),，這是-種已排序(sorted) 集合,，元素位置取決于其value (或key---如 果元素是個key/value pair)和給定的某個排序準則,。如果將6個元素置入這樣的集合中，它們的值將決定它們的次序,，和插入次序無關,。STL 提供了4個關聯(lián)式容器: set、 multiset,、 map和multimap,。

（3）無序容器(Unordered (associative) container)， 這是一 種無序集合(unordered collec-tion),其內(nèi)每個元素的位置無關緊要,，唯一重要的是某特定元素是否位于此集合內(nèi),。元素值或其安插順序，都不影響,。

2,、容器類的共通操作

c1 = move(c2) //賦值，c2賦給c1

元素訪問：

a,、簡單訪問

for(auto& elem : coll){
cout<<elem;
}

b,、指定位置操作的訪問

for(auto pos=coll.begin(); pos!=coll.end; ++pos){
*pos = ...;
}

c、使用迭代器訪問

for(iterator pos=coll.begin(); pos!=coll.end(); ++pos){
cout<<*pos;
}

3,、容器提供的類型

4,、序列式容器

（1）Array（其class名為array）

a、類似數(shù)組,，固定大小,，隨機訪問。

例：

array<string,5>  coll = {“hello”, “world”}; //初始化

for(int i = 0; i<coll.size(); i++){

cout<<coll[i]<,endl;

}

b,、Class array<>的構造函數(shù)

c,、Class array<>的賦值操作

d、Class array<>元素直接訪問

注：只有at（）執(zhí)行范圍檢查

e,、Class array<>迭代器的相關操作

f,、把array當成C-Style Array

array<char 10>  a;
strcpy(&a[0], “hello”);
printf(“%s\n”, &a[0]);
//可使用data訪問array的元素
strcpy(a.data(), “hello”);
printf(“%s\n”, a.data());

（2）Vector

a、類似尾部可伸縮的組數(shù),，隨機訪問,，尾部增刪方便，其他地方增刪較為耗時

例：

vector<int>  coll;
for(int i = 1; i<=5; i++){
coll.push_back(i);
}
for(int i=0; i<coll.size(); i++){
cout<<coll[i]<<endl;
}

注：可使用c.data()訪問vector中的元素

b,、容量

操作大小除了size(),、empty()、max_size()外還有容量capacity(),。

• 一旦內(nèi)存重新分配,，vector元素相關的所有reference、pointer,、iterator都會失效
• 內(nèi)存重新分配很耗時

法一：使用reserve()保留適當容量,，避免重新分配內(nèi)存,。不能縮減vector的長度。

vector<int> v;

v.reserve(80);

另：shrink_to_fit可縮減容量以符合當前元素個數(shù),，但會使得reference,、pointer、iterator失效

v.shrink_to_fit();

法二：初始化期間向構造函數(shù)傳遞額外實參,，構建足夠空間

vector<T> v(5);

c,、構造和析構函數(shù)

d、操作

e,、賦值

f,、元素訪問

g、迭代器

h,、vector的安插和移除

i,、vecto<bool>的特殊操作

例：移除與某值相等的第一個元素

vector<Elem>  col;
...
vector<Elem>::iterator pos;
pos = find(coll.begin(), coll.end(), val);
if(pos != coll.end()){
coll.erase(pos);
}

例：vector的應用

#include<iostream>
#include<vector>
#include<iterator>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	vector<string> sentence;
	sentence.reserve(5);		//5個元素
	sentence.push_back("Hello,");
	sentence.insert(sentence.end(), { " how", " are", " you", " ?" });
	//輸出元素和空格
	copy(sentence.cbegin(), sentence.cend(), ostream_iterator<string>(cout, " "));
	cout << endl;
	cout << "max_size: " << sentence.max_size() << endl;
	cout << "size: " << sentence.size() << endl;
	cout << "capaticy: " << sentence.capacity() << endl;
	swap(sentence[1], sentence[3]);
	//找到“ ?”插入“  always”
	sentence.insert( find(sentence.begin(), sentence.end(), " ?"), " always");
	sentence.back() = "!";
	copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
	cout << endl;
	//刪除后兩個元素
	sentence.pop_back();
	sentence.pop_back();
	sentence.shrink_to_fit();
	cout << "size: " << sentence.size() << endl;
	cout << "capaticy: " << sentence.capacity() << endl;
	system("pause");
	return 0;
}

輸出：

（3）Deque

a、類似首尾均可安插元素的數(shù)組,，在首尾安插元素方便,，中間安插元素則比較費時

例：

deque<float> coll;
for(int i =1; i <= 6; ++i){
coll.push_front(i*1.1);		//每個元素都安插在上一個元素的前面
}
for(int i = 0 ;i < coll.size(); ++i){
cout<<coll[i]<<endl;
}

b、deque的內(nèi)部結構

c,、deque構造函數(shù)和析構函數(shù)

d,、deque的操作函數(shù)

注： Deque的各項操作只有以下兩點和vector不同:

• Deque 不提供容量操作(capacity() 和reserve())。
• Deque 直接提供函數(shù)完成頭部元素的安插和刪除(push_ front ()和pop_ front()),。其他操作都相同,，所以這里不重復。

    請注意,，C++11添 加了shrink. .to. fit(),，那是個不具強制力(nonbinding) 的函數(shù)，負責縮小內(nèi)部內(nèi)存以匹配元素個數(shù),。你可能會認為shrink to_ fit()對deque沒意義,，因為deque本就會釋放不再用到的區(qū)塊內(nèi)存。然而,，deque 內(nèi)部用來存放“指向獨立區(qū)塊”的所有pointer的空間,，通常不會被縮小，如果用了這個函數(shù)就有可能真的被縮小,。

deque的非易型操作

deque的更易型操作

e,、deque和vector的區(qū)別

1）Deque與vector相比，功能上的差異如下:

●兩端都能快速安插元素和移除元素(vector 只在尾端逞威風),。這些操作可以在攤提的常量時間(amortized constant time)內(nèi)完成,。

●訪問元素時deque內(nèi)部結構會多一個間接過程，所以元素的訪問和迭代器的動作會稍稍 慢一些,。

●迭代器 需要在不同區(qū)塊間跳轉,，所以必須是個smart pointer,不能是尋常pointer,。

●在內(nèi)存區(qū)塊大小有限制的系統(tǒng)中(例如PC系統(tǒng))， deque可以內(nèi)含更多元素,，因為它使用不止一塊內(nèi)存。因此deque的max_ size()可能更大,。

●Deque不支持對容量和內(nèi)存重新分配時機的控制,。特別要注意的是，除了頭尾兩端,，在任何地點安插或刪除元素都將導致指向deque元素的任何pointer, reference 和iterator失效,。不過，deque 的內(nèi)存重分配優(yōu)于vector,因為其內(nèi)部結構顯示,，deque 不必在內(nèi)存重新分配時復制所有元素,。

●Deque會釋放不再使用的內(nèi)存區(qū)塊。Deque 的內(nèi)存大小是可縮減的,，但要不要這么做,，

以及如何做，由實現(xiàn)決定,。

2）Deque的以下特性跟Vector差不多:

●在中段安插,、移除元素的速度相對較慢，因為所有元素都需移動以騰出或填補空間,。

●迭代器屬于random-access iterator (隨機訪向迭代器),。

3）總之，以下情形最好采用deque:

●你需要在兩端安插和移除元素(這是deque的拿手好戲),。

●無須指向(referto) 容器內(nèi)的元素,。

●要求“不再使用的元素必須釋放”(不過C++ standard 對此無任何保證)。

Vector 和deque的接口兒乎一樣,，所以如果你不需要什么特殊性質,，兩者都可試試。

（4）List

a,、類似雙向鏈表,，非隨機訪問，插入和刪除迅速,。

b,、list的構造函數(shù)和析構函數(shù)

c、list的操作

list的非易型操作

list的賦值操作

d,、list的訪問

除front()和back()能直接訪問,，還可以使用range-based-for循環(huán)來訪問元素。

注：range-based-for循環(huán)（C++11）

list<char> coll;
for (char c = 'a'; c <= 'z'; ++c) {
	coll.push_back(c);
}
for (auto elem : coll) {			//auto為自動匹配類型
		cout << elem << ' ';
}

e,、迭代器的相關函數(shù)

f,、list的安插,、移除、操作函數(shù)

g,、list的特殊更易型操作

h,、list異常發(fā)發(fā)生時提供的特殊保證

例：

#include<iostream>
#include<list>
#include<iterator>
#include<algorithm>
using namespace std;
void printList(const list<int> l1, const list<int> l2)
{
	cout << "list1: ";
	copy(l1.cbegin(), l1.cend(), ostream_iterator<int>(cout, " "));
	cout << endl << "list2: ";
	copy(l2.cbegin(), l2.cend(), ostream_iterator<int>(cout, " "));
	cout << endl <<endl;
}
int main()
{
	list<int> list1,list2;
	for (int i = 0; i < 6; i++) {
		list1.push_back(i);
		list2.push_front(i);
	}
	printList(list1, list2);
	//在list2中第一次找到3，再把list1轉移到第一次找到的3之前
	list2.splice(find(list2.begin(), list2.end(), 3), list1);
	printList(list1, list2);
	//將list2中的第一個元素轉移到最后
	list2.splice(list2.end(), list2, list2.begin());
	printList(list1, list2);
	list2.sort();				//排序
	list1 = list2;				
	list2.unique();				//去相鄰重復
	printList(list1, list2);
	//在list和list2有序的情況下,，把list2轉移到list1,，并保證轉移后還是有序
	list1.merge(list2);
	printList(list1, list2);
	system("pause");
	return 0;
}

輸出：

（5）Fordward-List（C++11）

a、類似單向鏈表,，相對list的優(yōu)點是內(nèi)存用來少,，行動也略快。非隨機訪問

例：

forward_list<int> coll = { 2, 5, 6, 8, 5, 9, 4 };

coll.resize(9); //9個元素,，不夠補0

coll.resize(11, 99); //11個元素,，（第9個后開始）不夠補99

b、forward_list的約束

• 只有前向迭代器
• 不提供成員函數(shù)size()
• 沒有指向最末元素的錨點,，沒有push_back(),、pop_back()
• 增加和刪除元素必須傳遞前一元素的位置，例如用insert_after代替insert

c,、forward_list的構造函數(shù)和析構函數(shù)

d,、forward_list的操作

forward_list的非更易型操作

e、forward_list賦值

f,、forward_list元素訪問

使用range-based for循環(huán)訪問各個元素,，或者使用迭代器訪問

g、迭代器的相關函數(shù)

注：before_begin()和cbefore_begin()并不代表forward_list的一個合法位置,，除賦值和賦值動作,，對before_begin()返回值的合法操作只有++、==和!=

h,、元素的安插和移除

注：如果要找出某元素并替換該元素則需要找到該元素的前一個位置,，再用insert_after()插入?；蛘呤褂胣ext()函數(shù),。

i、forward_list提供的特殊更易型操作

5,、關聯(lián)式容器

關聯(lián)式容器由二叉樹實現(xiàn),，在二叉樹中，每個元素都有一個父節(jié)點和兩個子節(jié)點,，左子樹的所有元素都比自己小,，右子樹的所有元素都比自己大。

（1）set和multiset

set：依據(jù)value自動排列，每個元素只能出現(xiàn)一次,，不允許重復,。

multiset：與set的區(qū)別：元素可以重復。

a,、排序準則

• 1.必須是非對稱的(antisymmetric),。

對operator <而言，如果x < y為true, 則y < x為false.

對判斷式(predicate) op()而言,， 如果op(x,y) 為true,則op(y ,x)為false,。

• 2.必須是可傳遞的(transitive),。

對operator <而言,，如果x < y為truey< z為true, 則x < z為true,。

對判斷式op()而言,，如果op(x ,y)為true H.op(y ,z)為true,則op(x,z) 為true,。

• 3.必須是非自反的(ireflexive),。

對operator <而言,，x < x永遠為false,。

對判斷式op()而言,，op(x,x) 永遠為false。

• 4.必須有等效傳遞性(transitivity of equivalence),。

大體意義是:如果a等Fb且_b等于c,那么a必然等于c,。

    這意味著對于操作符<，若!(a<b) && ! (b<a)為truel!(b<c) & !(c<b) 為true,那么!(a<c) && !(c<a) 亦為true,。

    這也意味著對于判斷式op(),若op(a,b). op(b,a),、 op(b,c) 和op(c ,b)都為false,那么op(a,c)和op(c,a)為false。

    注意,，這意味著你必須區(qū)分less 和equal,一個像operator <=這樣的準則并不滿足這個條件,。

    根據(jù)這些性質，排序準則也被用來檢查等效性(equivalence),。 也就是說,， 兩個元素如果沒有任何一個小于另一個(或如果op(x,y)和op(y,x)都取得false)，則它們被視為重復,。

Multiset的等效元素的次序是隨機但穩(wěn)定的(random but stable),。因此C++11保證安插和抹除(erasure) 動作都會保存等效元素的相對次序。

注：排序準則也被用來檢驗元素相等性:

if(! (elem1<elem2 || elem2<elem1))

b,、set和multiset的構造函數(shù)和析構函數(shù)

其中的set可為下列形式

c,、set和multiset的非更易型操作

d、set和multiset的查找操作函數(shù)

e,、賦值

f,、set和multiset的迭代器相關操作

g、set和multiset的安插和移除

注：inset()和emplace()的返回值不同；

set：

pair<iterator,bool>  insert(const  value_type&  val);

iterator  insert (const_ iterator posHint, const value_ type& val) ;

template <typename... Args>  pair<iterator, bool> emplace (Args&&... args);

template <typename... Args>  iterator  emplace_ ,hint (const_ iterator posHint,

        Args&... args);

multiset:

 iterator  insert (const value_ type& val) ;

iterator  insert (const_ iterator posHint, const value_ type& val) ;

template <typename... Args>  iterator  emplace (Args&... args);

template <typename... Args>  iterator  emplace_ hint (const_ iterator posHint,

         Args&... args);

（2）map和multimap

map：每個元素都是key/value pair（鍵值對）,，其中key是排序準則的基準,。每個key只能出現(xiàn)一次，不允許重復,。map可被視為一種關聯(lián)式數(shù)組,，即”索引可為任意類型”的數(shù)組。

multimap：與map的區(qū)別：元素可以重復,，即multimap允許有相同的key,。multimap可被當做字典使用。

注：可將set視為一種特殊的map：元素的value等同于key,。

a,、map和multimap構造函數(shù)和析構函數(shù)

注：其中map可為下列形式

b、map和 multimap的非更易型操作

c,、map和 multimap的特殊查找操作

d,、map和multimap的賦值

e、map和multimap的迭代器相關操作

f,、map和multimap的元素的安插和移除

h,、將value傳入map和multimap內(nèi)：

1）運用value_type。

value_type是容器本身提供的類型定義

std::map<std:: string ,  float>  coll;

...

coll.insert(std::map<std::string, float>::value_type(“ott”, 66.2) );

或

coll.insert(decltype(coll)::value_type(“ott”, 66.2));

2）運用pair<>

std::map<std:: string ,  float>  coll;

coll.insert(std::pair<std::string, float> (“ddd”, 2225.5));

3）運用make_pair()

std::map<std:: string ,  float>  coll;

...

coll.insert(std::make_pair(“dd”, 22.2));

h,、map的直接元素訪問操作

6,、無序容器

無序容器常以hash table實現(xiàn)出來，內(nèi)部結構是一個有l(wèi)inked list組成的array,。通過某個hash函數(shù)的運算確定元素落于這個array的位置,，hash函數(shù)運算的目標是：讓每個元素的落點（位置）有助于用戶快速訪問。

（1）STL中無序容器

1）unordered set：無序元素的集合,，每個元素只允許出現(xiàn)一次,。

2）unordered multiset：與unordered set的區(qū)別就是允許元素重復。

3）unordered map：元素都是key/value pair,。每個key只可出現(xiàn)一次,，可作為關聯(lián)式數(shù)組。

注：關聯(lián)式數(shù)組：key/value pair中“索引并非整數(shù)”的array,。

4）unordered multimap：和unordered map的區(qū)別是允許key重復,。

（2）無序容器的構造函數(shù)和析構函數(shù)

（3）無序容器unord的所有可能類型

（4）布局操作

（5）無序容器的非更易型操作

（6）無序容器的特殊查找操作

（7）無序容器的賦值操作

（8）無序容器的迭代器操作

（9）無序容器的安插和移除操作

（10）bucket（桶）接口

（11）各容器的使用時機

●默認情況下應該使用vector, Vector的內(nèi)部結構最簡單，并允許隨機訪問,，所以數(shù)據(jù)的訪問十分方便靈話,，數(shù)據(jù)的處理也夠快。

●如果經(jīng)常要在序列頭部和尾部安插和移除元素,，應該采用deque,。 如果你希望元素被移 除時，容器能夠自動縮減內(nèi)部內(nèi)存用量，那么也該采用deque,。此外,，由于vector通常采用一個內(nèi)存區(qū)塊來存放元素，而deque采用多個區(qū)塊,，所以后者可內(nèi)含更多元素,。

●如果需要經(jīng)常 在容器中段執(zhí)行元素的安插、移除和移動,，可考慮使用list.,。List 提供特殊

的成員函數(shù)，可以在常量時間內(nèi)將元素從A容器轉移到B容器,。但由于list不支持隨機訪問,，所以如果只知道list的頭部卻要造訪list的中段元素，效能會大打折扣,。

        和所有“以節(jié)點為基礎”的容器相似,，只要元素仍是容器的一部分，list 就不會令指向那些元素的迭代器失效,。Vector 則不然，一旦超過其容量,，它的所有iterator,pointer和reference都會失效:執(zhí)行安插或移除動作時,，也會令一部分iterator. pointer和reference失效。至于deque,當它的大小改變,，所有iterator. pointer 和reference都會失效,。

●如果你要的容器對異常的處理使得“每次操作若不成功便無任何作用”，那么應該選用list (但是不調(diào)用其assignment操作符和sort(),而且如果元素比較過程中會拋出異常,，就不要調(diào)用merge(),、remove(). remove. .if() 和unique()，或選用associative/unordered容器(但是不調(diào)用多元素安插動作,，而iL如果比較準則(comparison criterion]的復制賦值動作可能拋出異常,，就不要調(diào)用swap()或erase())。

●如果你經(jīng)常需要根據(jù)某個準則查找元素,，應當使用“依據(jù)該準則進行hash”的unordered

set或muliset,然而,，hash 容器內(nèi)是無序的，所以如果你必項依賴元素的次序(order),，應該使用set或multiset,它們根據(jù)查找準則(search criterion)對元素排序,。

●如果想處理 key/value pair,請采用unordered (multimap)。如果元素次序很重要,，可采用

(multi)map,。

●如果需要關聯(lián)式數(shù)組(associaive array),應采用unordered map。如果元素次序很重要，

可采用map,。

●如果需要字典結構,，應采用unordered mulimap, 如果元素次序很重要，可采用mul-

Timap,。

（12）STL容器能力一覽表