1 什么是STL？

STL（Standard Template Library），即標準模板庫，是一個具有工業(yè)強度的，高效的C++程序庫。它被容納于C++標準程序庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個可擴展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。

STL的一個重要特點是數(shù)據(jù)結(jié)構(gòu)和算法的分離。盡管這是個簡單的概念，但這種分離確實使得STL變得非常通用。例如，由于STL的sort()函數(shù)是完全通用的，你可以用它來操作幾乎任何數(shù)據(jù)集合，包括鏈表，容器和數(shù)組；

STL另一個重要特性是它不是面向?qū)ο蟮?。為了具有足夠通用性，STL主要依賴于模板而不是封裝，繼承和虛函數(shù)（多態(tài)性）——OOP的三個要素。你在STL中找不到任何明顯的類繼承關(guān)系。這好像是一種倒退，但這正好是使得STL的組件具有廣泛通用性的底層特征。另外，由于STL是基于模板，內(nèi)聯(lián)函數(shù)的使用使得生成的代碼短小高效；

從邏輯層次來看，在STL中體現(xiàn)了泛型化程序設(shè)計的思想，引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；

從實現(xiàn)層次看，整個STL是以一種類型參數(shù)化的方式實現(xiàn)的，這種方式基于一個在早先C++標準中沒有出現(xiàn)的語言特性--模板（template）。

2 STL內(nèi)容介紹

STL中六大組件：

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

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

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

仿函數(shù)（Functor）

適配器（Adaptor）

分配器（allocator）

2.1 容器

STL中的容器有隊列容器和關(guān)聯(lián)容器，容器適配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。

（1）序列式容器（Sequence containers），每個元素都有固定位置－－取決于插入時機和地點，和元素值無關(guān)，vector、deque、list；

Vector：將元素置于一個動態(tài)數(shù)組中加以管理，可以隨機存取元素（用索引直接存?。瑪?shù)組尾部添加或移除元素非?？焖?。但是在中部或頭部安插元素比較費時；

Deque：是“double-ended queue”的縮寫，可以隨機存取元素（用索引直接存取），數(shù)組頭部和尾部添加或移除元素都非?？焖?。但是在中部或頭部安插元素比較費時；

List：雙向鏈表，不提供隨機存?。ò错樞蜃叩叫璐嫒〉脑兀琌(n)），在任何位置上執(zhí)行插入或刪除動作都非常迅速，內(nèi)部只需調(diào)整一下指針；

（2）關(guān)聯(lián)式容器（Associated containers），元素位置取決于特定的排序準則，和插入順序無關(guān)，set、multiset、map、multimap等。

Set/Multiset：內(nèi)部的元素依據(jù)其值自動排序，Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multisets內(nèi)可包含多個數(shù)值相同的元素，內(nèi)部由二叉樹實現(xiàn)，便于查找；

Map/Multimap：Map的元素是成對的鍵值/實值，內(nèi)部的元素依據(jù)其值自動排序，Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次，Multimaps內(nèi)可包含多個數(shù)值相同的元素，內(nèi)部由二叉樹實現(xiàn)，便于查找；

容器類自動申請和釋放內(nèi)存，無需new和delete操作。

2.2 STL迭代器

Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內(nèi)部表示?；蛘哌@樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內(nèi)部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。

迭代器的作用：能夠讓迭代器與算法不干擾的相互發(fā)展，最后又能無間隙的粘合起來，重載了*，＋＋，＝＝，?。?，＝運算符。用以操作復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，容器提供迭代器，算法使用迭代器；常見的一些迭代器類型：iterator、const_iterator、reverse_iterator和const_reverse_iterator.

2.3 算法

函數(shù)庫對數(shù)據(jù)類型的選擇對其可重用性起著至關(guān)重要的作用。舉例來說，一個求方根的函數(shù)，在使用浮點數(shù)作為其參數(shù)類型的情況下的可重用性肯定比使用整型作為它的參數(shù)類性要高。而C++通過模板的機制允許推遲對某些類型的選擇，直到真正想使用模板或者說對模板進行特化的時候，STL就利用了這一點提供了相當(dāng)多的有用算法。它是在一個有效的框架中完成這些算法的——你可以將所有的類型劃分為少數(shù)的幾類，然后就可以在模版的參數(shù)中使用一種類型替換掉同一種類中的其他類型。

STL提供了大約100個實現(xiàn)算法的模版函數(shù)，比如算法for_each將為指定序列中的每一個元素調(diào)用指定的函數(shù)，stable_sort以你所指定的規(guī)則對序列進行穩(wěn)定性排序等等。只要我們熟悉了STL之后，許多代碼可以被大大的化簡，只需要通過調(diào)用一兩個算法模板，就可以完成所需要的功能并大大地提升效率。

算法部分主要由頭文件，和組成。

是所有STL頭文件中最大的一個（盡管它很好理解），它是由一大堆模版函數(shù)組成的，可以認為每個函數(shù)在很大程度上都是獨立的，其中常用到的功能范圍涉及到比較、交換、查找、遍歷操作、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等等。

體積很小，只包括幾個在序列上面進行簡單數(shù)學(xué)運算的模板函數(shù)，包括加法和乘法在序列上的一些操作。

中則定義了一些模板類，用以聲明函數(shù)對象。

STL中算法大致分為四類：

非可變序列算法：指不直接修改其所操作的容器內(nèi)容的算法。
可變序列算法：指可以修改它們所操作的容器內(nèi)容的算法。
排序算法：對序列進行排序和合并的算法、搜索算法以及有序序列上的集合操作。
數(shù)值算法：對容器內(nèi)容進行數(shù)值計算。

以下對所有算法進行細致分類并標明功能：

<一>查找算法(13個)：判斷容器中是否包含某個值

adjacent_find: 在iterator對標識元素范圍內(nèi)，查找一對相鄰重復(fù)元素，找到則返回指向這對元素的第一個元素的 ForwardIterator。否則返回last。重載版本使用輸入的二元操作符代替相等的判斷。

binary_search: 在有序序列中查找value，找到返回true。重載的版本實用指定的比較函數(shù)對象或函數(shù)指針來判斷相等。

count: 利用等于操作符，把標志范圍內(nèi)的元素與輸入值比較，返回相等元素個數(shù)。

count_if: 利用輸入的操作符，對標志范圍內(nèi)的元素進行操作，返回結(jié)果為true的個數(shù)。

equal_range: 功能類似equal，返回一對iterator，第一個表示lower_bound，第二個表示upper_bound。

find: 利用底層元素的等于操作符，對指定范圍內(nèi)的元素與輸入值進行比較。當(dāng)匹配時，結(jié)束搜索，返回該元素的一個InputIterator。

find_end: 在指定范圍內(nèi)查找"由輸入的另外一對iterator標志的第二個序列"的最后一次出現(xiàn)。找到則返回最后一對的第一個ForwardIterator，否則返回輸入的"另外一對"的第一個ForwardIterator。重載版本使用用戶輸入的操作符代替等于操作。

find_first_of: 在指定范圍內(nèi)查找"由輸入的另外一對iterator標志的第二個序列"中任意一個元素的第一次出現(xiàn)。重載版本中使用了用戶自定義操作符。

find_if: 使用輸入的函數(shù)代替等于操作符執(zhí)行find。

lower_bound: 返回一個ForwardIterator，指向在有序序列范圍內(nèi)的可以插入指定值而不破壞容器順序的第一個位置。重載函數(shù)使用自定義比較操作。

upper_bound: 返回一個ForwardIterator，指向在有序序列范圍內(nèi)插入value而不破壞容器順序的最后一個位置，該位置標志一個大于value的值。重載函數(shù)使用自定義比較操作。

search: 給出兩個范圍，返回一個ForwardIterator，查找成功指向第一個范圍內(nèi)第一次出現(xiàn)子序列(第二個范圍)的位置，查找失敗指向last1。重載版本使用自定義的比較操作。

search_n: 在指定范圍內(nèi)查找val出現(xiàn)n次的子序列。重載版本使用自定義的比較操作。

<二>排序和通用算法(14個)：提供元素排序策略

inplace_merge: 合并兩個有序序列，結(jié)果序列覆蓋兩端范圍。重載版本使用輸入的操作進行排序。

merge: 合并兩個有序序列，存放到另一個序列。重載版本使用自定義的比較。

nth_element: 將范圍內(nèi)的序列重新排序，使所有小于第n個元素的元素都出現(xiàn)在它前面，而大于它的都出現(xiàn)在后面。重載版本使用自定義的比較操作。

partial_sort: 對序列做部分排序，被排序元素個數(shù)正好可以被放到范圍內(nèi)。重載版本使用自定義的比較操作。

partial_sort_copy: 與partial_sort類似，不過將經(jīng)過排序的序列復(fù)制到另一個容器。

partition: 對指定范圍內(nèi)元素重新排序，使用輸入的函數(shù)，把結(jié)果為true的元素放在結(jié)果為false的元素之前。

random_shuffle: 對指定范圍內(nèi)的元素隨機調(diào)整次序。重載版本輸入一個隨機數(shù)產(chǎn)生操作。

reverse: 將指定范圍內(nèi)元素重新反序排序。

reverse_copy: 與reverse類似，不過將結(jié)果寫入另一個容器。

rotate: 將指定范圍內(nèi)元素移到容器末尾，由middle指向的元素成為容器第一個元素。

rotate_copy: 與rotate類似，不過將結(jié)果寫入另一個容器。

sort: 以升序重新排列指定范圍內(nèi)的元素。重載版本使用自定義的比較操作。

stable_sort: 與sort類似，不過保留相等元素之間的順序關(guān)系。

stable_partition: 與partition類似，不過不保證保留容器中的相對順序。

<三>刪除和替換算法(15個)

copy: 復(fù)制序列

copy_backward: 與copy相同，不過元素是以相反順序被拷貝。

iter_swap: 交換兩個ForwardIterator的值。

remove: 刪除指定范圍內(nèi)所有等于指定元素的元素。注意，該函數(shù)不是真正刪除函數(shù)。內(nèi)置函數(shù)不適合使用remove和 remove_if函數(shù)。

remove_copy: 將所有不匹配元素復(fù)制到一個制定容器，返回OutputIterator指向被拷貝的末元素的下一個位置。

remove_if: 刪除指定范圍內(nèi)輸入操作結(jié)果為true的所有元素。

remove_copy_if: 將所有不匹配元素拷貝到一個指定容器。

replace: 將指定范圍內(nèi)所有等于vold的元素都用vnew代替。

replace_copy: 與replace類似，不過將結(jié)果寫入另一個容器。

replace_if: 將指定范圍內(nèi)所有操作結(jié)果為true的元素用新值代替。

replace_copy_if: 與replace_if，不過將結(jié)果寫入另一個容器。

swap: 交換存儲在兩個對象中的值。

swap_range: 將指定范圍內(nèi)的元素與另一個序列元素值進行交換。

unique: 清除序列中重復(fù)元素，和remove類似，它也不能真正刪除元素。重載版本使用自定義比較操作。

unique_copy: 與unique類似，不過把結(jié)果輸出到另一個容器。

<四>排列組合算法(2個)：提供計算給定集合按一定順序的所有可能排列組合

next_permutation: 取出當(dāng)前范圍內(nèi)的排列，并重新排序為下一個排列。重載版本使用自定義的比較操作。

prev_permutation: 取出指定范圍內(nèi)的序列并將它重新排序為上一個序列。如果不存在上一個序列則返回false。重載版本使用自定義的比較操作。

<五>算術(shù)算法(4個)

accumulate: iterator對標識的序列段元素之和，加到一個由val指定的初始值上。重載版本不再做加法，而是傳進來的二元操作符被應(yīng)用到元素上。

partial_sum: 創(chuàng)建一個新序列，其中每個元素值代表指定范圍內(nèi)該位置前所有元素之和。重載版本使用自定義操作代替加法。

inner_product: 對兩個序列做內(nèi)積(對應(yīng)元素相乘，再求和)并將內(nèi)積加到一個輸入的初始值上。重載版本使用用戶定義的操作。

adjacent_difference: 創(chuàng)建一個新序列，新序列中每個新值代表當(dāng)前元素與上一個元素的差。重載版本用指定二元操作計算相鄰元素的差。

<六>生成和異變算法(6個)

fill: 將輸入值賦給標志范圍內(nèi)的所有元素。

fill_n: 將輸入值賦給first到first+n范圍內(nèi)的所有元素。

for_each: 用指定函數(shù)依次對指定范圍內(nèi)所有元素進行迭代訪問，返回所指定的函數(shù)類型。該函數(shù)不得修改序列中的元素。

generate: 連續(xù)調(diào)用輸入的函數(shù)來填充指定的范圍。

generate_n: 與generate函數(shù)類似，填充從指定iterator開始的n個元素。

transform: 將輸入的操作作用與指定范圍內(nèi)的每個元素，并產(chǎn)生一個新的序列。重載版本將操作作用在一對元素上，另外一個元素來自輸入的另外一個序列。結(jié)果輸出到指定容器。

<七>關(guān)系算法(8個)

equal: 如果兩個序列在標志范圍內(nèi)元素都相等，返回true。重載版本使用輸入的操作符代替默認的等于操作符。

includes: 判斷第一個指定范圍內(nèi)的所有元素是否都被第二個范圍包含，使用底層元素的<操作符，成功返回 true。重載版本使用用戶輸入的函數(shù)。

lexicographical_compare: 比較兩個序列。重載版本使用用戶自定義比較操作。

max: 返回兩個元素中較大一個。重載版本使用自定義比較操作。

max_element: 返回一個ForwardIterator，指出序列中最大的元素。重載版本使用自定義比較操作。

min: 返回兩個元素中較小一個。重載版本使用自定義比較操作。

min_element: 返回一個ForwardIterator，指出序列中最小的元素。重載版本使用自定義比較操作。

mismatch: 并行比較兩個序列，指出第一個不匹配的位置，返回一對iterator，標志第一個不匹配元素位置。如果都匹配，返回每個容器的last。重載版本使用自定義的比較操作。

<八>集合算法(4個)

set_union: 構(gòu)造一個有序序列，包含兩個序列中所有的不重復(fù)元素。重載版本使用自定義的比較操作。

set_intersection: 構(gòu)造一個有序序列，其中元素在兩個序列中都存在。重載版本使用自定義的比較操作。

set_difference: 構(gòu)造一個有序序列，該序列僅保留第一個序列中存在的而第二個中不存在的元素。重載版本使用自定義的比較操作。

set_symmetric_difference: 構(gòu)造一個有序序列，該序列取兩個序列的對稱差集(并集-交集)。

<九>堆算法(4個)

make_heap: 把指定范圍內(nèi)的元素生成一個堆。重載版本使用自定義比較操作。

pop_heap: 并不真正把最大元素從堆中彈出，而是重新排序堆。它把first和last-1交換，然后重新生成一個堆。可使用容器的 back來訪問被"彈出"的元素或者使用pop_back進行真正的刪除。重載版本使用自定義的比較操作。

push_heap: 假設(shè)first到last-1是一個有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數(shù)前，必須先把元素插入容器后。重載版本使用指定的比較操作。

sort_heap: 對指定范圍內(nèi)的序列重新排序，它假設(shè)該序列是個有序堆。重載版本使用自定義比較操作。

2.4 仿函數(shù)

2.4.1 概述

仿函數(shù)(functor)，就是使一個類的使用看上去象一個函數(shù)。其實現(xiàn)就是類中實現(xiàn)一個operator()，這個類就有了類似函數(shù)的行為，就是一個仿函數(shù)類了。

有些功能的的代碼，會在不同的成員函數(shù)中用到，想復(fù)用這些代碼。

1）公共的函數(shù)，可以，這是一個解決方法，不過函數(shù)用到的一些變量，就可能成為公共的全局變量，再說為了復(fù)用這么一片代碼，就要單立出一個函數(shù)，也不是很好維護。

2）仿函數(shù)，寫一個簡單類，除了那些維護一個類的成員函數(shù)外，就只是實現(xiàn)一個operator()，在類實例化時，就將要用的，非參數(shù)的元素傳入類中。

2.4.2 仿函數(shù)(functor)在編程語言中的應(yīng)用

1）C語言使用函數(shù)指針和回調(diào)函數(shù)來實現(xiàn)仿函數(shù)，例如一個用來排序的函數(shù)可以這樣使用仿函數(shù)

#include < stdio.h >
#include < stdlib.h >
//int sort_function( const void *a, const void *b);
int sort_function( const void *a, const void *b)
{   
	return *(int*)a-*(int*)b;
}

int main()
{

   int list[5] = { 54, 21, 11, 67, 22 };
   qsort((void *)list, 5, sizeof(list[0]), sort_function);//起始地址，個數(shù)，元素大小，回調(diào)函數(shù) 
   int  x;
   for (x = 0; x < 5; x++)
		  printf("%in", list[x]);
			      
   return 0;
}

2）在C++里，我們通過在一個類中重載括號運算符的方法使用一個函數(shù)對象而不是一個普通函數(shù)。

#include < iostream >
#include < algorithm >

using namespace std;
template< typename T >
class display
{
public:
	void operator()(const T &x)
	{
		cout < < x < < " ";
	}
};
int main()
{
	int ia[] = { 1,2,3,4,5 };
	for_each(ia, ia + 5, display< int >());
	system("pause");
	return 0;
}

2.4.3 仿函數(shù)在STL中的定義

要使用STL內(nèi)建的仿函數(shù)，必須包含頭文件。而頭文件中包含的仿函數(shù)分類包括

1）算術(shù)類仿函數(shù)

加：plus

減：minus

乘：multiplies

除：divides

模取：modulus

否定：negate

例子：

#include < iostream >
#include < numeric >
#include < vector > 
#include < functional > 
using namespace std;

int main()
{
	int ia[] = { 1,2,3,4,5 };
	vector< int > iv(ia, ia + 5);
	//120
	cout < < accumulate(iv.begin(), iv.end(), 1, multiplies< int >()) < < endl;
	//15
	cout < < multiplies< int >()(3, 5) < < endl;

	modulus< int >  modulusObj;
	cout < < modulusObj(3, 5) < < endl; // 3 
	system("pause");
	return 0;
}

2）關(guān)系運算類仿函數(shù)

等于：equal_to

不等于：not_equal_to

大于：greater

大于等于：greater_equal

小于：less

小于等于：less_equal

從大到小排序：

#include < iostream >
#include < algorithm >
#include< functional >
#include < vector > 

using namespace std;

template < class T >
class display
{
public:
	void operator()(const T &x)
	{
		cout < < x < < " ";
	}
};
int main()
{
	int ia[] = { 1,5,4,3,2 };
	vector< int > iv(ia, ia + 5);
	sort(iv.begin(), iv.end(), greater< int >());
	for_each(iv.begin(), iv.end(), display< int >());
	system("pause");
	return 0;
}

3）邏輯運算仿函數(shù)

邏輯與：logical_and

邏輯或：logical_or

邏輯否：logical_no

除了使用STL內(nèi)建的仿函數(shù)，還可使用自定義的仿函數(shù)，具體實例見文章3.4.7.2小結(jié)

2.5 容器適配器

標準庫提供了三種順序容器適配器：queue(FIFO隊列)、priority_queue(優(yōu)先級隊列)、stack(棧)

什么是容器適配器

適配器是使一種事物的行為類似于另外一種事物行為的一種機制”，適配器對容器進行包裝，使其表現(xiàn)出另外一種行為。例如，stack >實現(xiàn)了棧的功能，但其內(nèi)部使用順序容器vector來存儲數(shù)據(jù)。（相當(dāng)于是vector表現(xiàn)出了棧的行為）。

容器適配器

要使用適配器，需要加入一下頭文件：

#include //stack

#include //queue、priority_queue

定義適配器

1、初始化

stack stk(dep);

2、覆蓋默認容器類型

stack > stk;

使用適配器

2.5.1 stack

stack< int > s;
stack< int, vector< int > > stk;  //覆蓋基礎(chǔ)容器類型，使用vector實現(xiàn)stk
s.empty();  //判斷stack是否為空，為空返回true，否則返回false
s.size();   //返回stack中元素的個數(shù)
s.pop();    //刪除棧頂元素，但不返回其值
s.top();    //返回棧頂元素的值，但不刪除此元素
s.push(item);   //在棧頂壓入新元素item

實例：括號匹配

#include< iostream >
#include< cstdio >
#include< string >
#include< stack >
using namespace std;
int main()
{
	string s;
	stack< char > ss;
	while (cin > > s) 
	{
		bool flag = true;
		for (char c : s)  //C++11新標準，即遍歷一次字符串s
		{
			if (c == '(' || c == '{' || c == '[')
			{
				ss.push(c);
				continue;
			}
			if (c == '}')
			{
				if (!ss.empty() && ss.top() == '{')
				{
					ss.pop();
					continue;
				}
				else
				{
					flag = false;
					break;
				}					
			}
			if (!ss.empty() && c == ']')
			{
				if (ss.top() == '[')
				{
					ss.pop();
					continue;
				}
				else
				{
					flag = false;
					break;
				}
			}
			if (!ss.empty() && c == ')')
			{
				if (ss.top() == '(')
				{
					ss.pop();
					continue;
				}
				else
				{
					flag = false;
					break;
				}
			}
		}
		if (flag)	cout < < "Match!" < < endl;
		else    cout < < "Not Match!" < < endl;
	}
}

2.5.2 queue & priority_queue

queue< int > q; //priority_queue< int > q;
q.empty();  //判斷隊列是否為空
q.size();   //返回隊列長度
q.push(item);   //對于queue，在隊尾壓入一個新元素
               //對于priority_queue，在基于優(yōu)先級的適當(dāng)位置插入新元素

//queue only:
q.front();  //返回隊首元素的值，但不刪除該元素
q.back();   //返回隊尾元素的值，但不刪除該元素

//priority_queue only:
q.top();    //返回具有最高優(yōu)先級的元素值，但不刪除該元素

3 常用容器用法介紹

3.1 vector

3.1.1 基本函數(shù)實現(xiàn)

1.構(gòu)造函數(shù)

vector():創(chuàng)建一個空vector
vector(int nSize):創(chuàng)建一個vector,元素個數(shù)為nSize
vector(int nSize,const t& t):創(chuàng)建一個vector，元素個數(shù)為nSize,且值均為t
vector(const vector&):復(fù)制構(gòu)造函數(shù)
vector(begin,end):復(fù)制[begin,end)區(qū)間內(nèi)另一個數(shù)組的元素到vector中

2.增加函數(shù)

void push_back(const T& x):向量尾部增加一個元素X
iterator insert(iterator it,const T& x):向量中迭代器指向元素前增加一個元素x
iterator insert(iterator it,int n,const T& x):向量中迭代器指向元素前增加n個相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last):向量中迭代器指向元素前插入另一個相同類型向量的[first,last)間的數(shù)據(jù)

3.刪除函數(shù)

iterator erase(iterator it):刪除向量中迭代器指向元素
iterator erase(iterator first,iterator last):刪除向量中[first,last)中元素
void pop_back():刪除向量中最后一個元素
void clear():清空向量中所有元素

4.遍歷函數(shù)

reference at(int pos):返回pos位置元素的引用
reference front():返回首元素的引用
reference back():返回尾元素的引用
iterator begin():返回向量頭指針，指向第一個元素
iterator end():返回向量尾指針，指向向量最后一個元素的下一個位置
reverse_iterator rbegin():反向迭代器，指向最后一個元素
reverse_iterator rend():反向迭代器，指向第一個元素之前的位置

5.判斷函數(shù)

bool empty() const:判斷向量是否為空，若為空，則向量中無元素

6.大小函數(shù)

int size() const:返回向量中元素的個數(shù)
int capacity() const:返回當(dāng)前向量張紅所能容納的最大元素值
int max_size() const:返回最大可允許的vector元素數(shù)量值

7.其他函數(shù)

void swap(vector&):交換兩個同類型向量的數(shù)據(jù)
void assign(int n,const T& x):設(shè)置向量中第n個元素的值為x
void assign(const_iterator first,const_iterator last):向量中[first,last)中元素設(shè)置成當(dāng)前向量元素

8.看著清楚

1.push_back 在數(shù)組的最后添加一個數(shù)據(jù)

2.pop_back 去掉數(shù)組的最后一個數(shù)據(jù)

.at-Domain Parked 得到編號位置的數(shù)據(jù)

4.begin 得到數(shù)組頭的指針

5.end 得到數(shù)組的最后一個單元+1的指針

6．front 得到數(shù)組頭的引用

7.back 得到數(shù)組的最后一個單元的引用

8.max_size 得到vector最大可以是多大

9.capacity 當(dāng)前vector分配的大小

10.size 當(dāng)前使用數(shù)據(jù)的大小

11.resize 改變當(dāng)前使用數(shù)據(jù)的大小，如果它比當(dāng)前使用的大，者填充默認值

12.reserve 改變當(dāng)前vecotr所分配空間的大小

13.erase 刪除指針指向的數(shù)據(jù)項

14.clear 清空當(dāng)前的vector

15.rbegin 將vector反轉(zhuǎn)后的開始指針返回(其實就是原來的end-1)

16.rend 將vector反轉(zhuǎn)構(gòu)的結(jié)束指針返回(其實就是原來的begin-1)

17.empty 判斷vector是否為空

18.swap 與另一個vector交換數(shù)據(jù)

3.1.2 基本用法

#include < vector > 
using namespace std;

3.1.3 簡單介紹

Vector<類型>標識符
Vector<類型>標識符(最大容量)
Vector<類型>標識符(最大容量,初始所有值)
Int i[5]={1,2,3,4,5}
Vector<類型>vi(I,i+2);//得到i索引值為3以后的值
Vector< vector< int> >v; 二維向量//這里最外的<>要有空格。否則在比較舊的編譯器下無法通過

3.1.4 實例

3.1.4.1 pop_back()&push_back(elem)實例在容器最后移除和插入數(shù)據(jù)

#include < string.h >
#include < vector >
#include < iostream >
using namespace std;

int main()
{
    vector< int >obj;//創(chuàng)建一個向量存儲容器 int
    for(int i=0;i< 10;i++) // push_back(elem)在數(shù)組最后添加數(shù)據(jù) 
    {
        obj.push_back(i);
        cout<

輸出結(jié)果為：

0,1,2,3,4,5,6,7,8,9,

0,1,2,3,4,

3.1.4.2 clear()清除容器中所有數(shù)據(jù)

#include < string.h >
#include < vector >
#include < iostream >
using namespace std;

int main()
{
    vector< int >obj;
    for(int i=0;i< 10;i++)//push_back(elem)在數(shù)組最后添加數(shù)據(jù) 
    {
        obj.push_back(i);
        cout<

輸出結(jié)果為：

0,1,2,3,4,5,6,7,8,9,

3.1.4.3 排序

#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;

int main()
{
    vector< int >obj;

    obj.push_back(1);
    obj.push_back(3);
    obj.push_back(0);

    sort(obj.begin(),obj.end());//從小到大

    cout< "從小到大:"<

輸出結(jié)果為：

從小到大:
0,1,3,

從大到小:
3,1,0,

1.注意 sort 需要頭文件 #include

2.如果想 sort 來降序，可重寫 sort

bool compare(int a,int b) 
{ 
    return a< b; //升序排列，如果改為return a >b，則為降序 
} 
int a[20]={2,4,1,23,5,76,0,43,24,65},i; 
for(i=0;i< 20;i++) 
    cout< < a[i]< < endl; 
sort(a,a+20,compare);

3.1.4.4 訪問（直接數(shù)組訪問&迭代器訪問）

#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;

int main()
{
    //順序訪問
    vector< int >obj;
    for(int i=0;i< 10;i++)
    {
        obj.push_back(i);   
    } 

    cout< "直接利用數(shù)組："; 
    for(int i=0;i< 10;i++)//方法一 
    {
        cout<

輸出結(jié)果為：

直接利用數(shù)組：0 1 2 3 4 5 6 7 8 9 
利用迭代器：0 1 2 3 4 5 6 7 8 9

3.1.4.5 二維數(shù)組兩種定義方法（結(jié)果一樣）

方法一

#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;


int main()
{
    int N=5, M=6; 
    vector< vector< int > > obj(N); //定義二維動態(tài)數(shù)組大小5行 
    for(int i =0; i< obj.size(); i++)//動態(tài)二維數(shù)組為5行6列，值全為0 
    { 
        obj[i].resize(M); 
    } 

    for(int i=0; i< obj.size(); i++)//輸出二維動態(tài)數(shù)組 
    {
        for(int j=0;j< obj[i].size();j++)
        {
            cout<

方法二

#include < string.h >
#include < vector >
#include < iostream >
#include < algorithm >
using namespace std;


int main()
{
    int N=5, M=6; 
    vector< vector< int > > obj(N, vector< int >(M)); //定義二維動態(tài)數(shù)組5行6列 

    for(int i=0; i< obj.size(); i++)//輸出二維動態(tài)數(shù)組 
    {
        for(int j=0;j< obj[i].size();j++)
        {
            cout<

輸出結(jié)果為：

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

3.2 deque

所謂的deque是”double ended queue”的縮寫，雙端隊列不論在尾部或頭部插入元素，都十分迅速。而在中間插入元素則會比較費時，因為必須移動中間其他的元素。雙端隊列是一種隨機訪問的數(shù)據(jù)類型，提供了在序列兩端快速插入和刪除操作的功能，它可以在需要的時候改變自身大小，完成了標準的C++數(shù)據(jù)結(jié)構(gòu)中隊列的所有功能。

Vector是單向開口的連續(xù)線性空間，deque則是一種雙向開口的連續(xù)線性空間。deque對象在隊列的兩端放置元素和刪除元素是高效的，而向量vector只是在插入序列的末尾時操作才是高效的。deque和vector的最大差異，一在于deque允許于常數(shù)時間內(nèi)對頭端進行元素的插入或移除操作，二在于deque沒有所謂的capacity觀念，因為它是動態(tài)地以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接起來。換句話說，像vector那樣“因舊空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間”這樣的事情在deque中是不會發(fā)生的。也因此，deque沒有必要提供所謂的空間預(yù)留（reserved）功能。

雖然deque也提供Random Access Iterator，但它的迭代器并不是普通指針，其復(fù)雜度和vector不可同日而語，這當(dāng)然涉及到各個運算層面。因此，除非必要，我們應(yīng)盡可能選擇使用vector而非deque。對deque進行的排序操作，為了最高效率，可將deque先完整復(fù)制到一個vector身上，將vector排序后（利用STL的sort算法），再復(fù)制回deque。

deque是一種優(yōu)化了的對序列兩端元素進行添加和刪除操作的基本序列容器。通常由一些獨立的區(qū)塊組成，第一區(qū)塊朝某方向擴展，最后一個區(qū)塊朝另一方向擴展。它允許較為快速地隨機訪問但它不像vector一樣把所有對象保存在一個連續(xù)的內(nèi)存塊，而是多個連續(xù)的內(nèi)存塊。并且在一個映射結(jié)構(gòu)中保存對這些塊以及順序的跟蹤。

3.2.1 聲明deque容器

#include< deque >  // 頭文件
deque< type > deq;  // 聲明一個元素類型為type的雙端隊列que
deque< type > deq(size);  // 聲明一個類型為type、含有size個默認值初始化元素的的雙端隊列que
deque< type > deq(size, value);  // 聲明一個元素類型為type、含有size個value元素的雙端隊列que
deque< type > deq(mydeque);  // deq是mydeque的一個副本
deque< type > deq(first, last);  // 使用迭代器first、last范圍內(nèi)的元素初始化deq

3.2.2 deque的常用成員函數(shù)

deque< int > deq;

deq[ ]：用來訪問雙向隊列中單個的元素。
deq.front()：返回第一個元素的引用。
deq.back()：返回最后一個元素的引用。
deq.push_front(x)：把元素x插入到雙向隊列的頭部。
deq.pop_front()：彈出雙向隊列的第一個元素。
deq.push_back(x)：把元素x插入到雙向隊列的尾部。
deq.pop_back()：彈出雙向隊列的最后一個元素。

3.2.3 deque的一些特點

支持隨機訪問，即支持[ ]以及at()，但是性能沒有vector好。
可以在內(nèi)部進行插入和刪除操作，但性能不及l(fā)ist。
deque兩端都能夠快速插入和刪除元素，而vector只能在尾端進行。
deque的元素存取和迭代器操作會稍微慢一些，因為deque的內(nèi)部結(jié)構(gòu)會多一個間接過程。
deque迭代器是特殊的智能指針，而不是一般指針，它需要在不同的區(qū)塊之間跳轉(zhuǎn)。
deque可以包含更多的元素，其max_size可能更大，因為不止使用一塊內(nèi)存。
deque不支持對容量和內(nèi)存分配時機的控制。
在除了首尾兩端的其他地方插入和刪除元素，都將會導(dǎo)致指向deque元素的任何pointers、references、iterators失效。不過，deque的內(nèi)存重分配優(yōu)于vector，因為其內(nèi)部結(jié)構(gòu)顯示不需要復(fù)制所有元素。
deque的內(nèi)存區(qū)塊不再被使用時，會被釋放，deque的內(nèi)存大小是可縮減的。不過，是不是這么做以及怎么做由實際操作版本定義。
deque不提供容量操作：capacity()和reverse()，但是vector可以。

3.2.4 實例

#include< iostream >
#include< stdio.h >
#include< deque >
using namespace std;
int main(void)
{
	int i;
	int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
	deque< int > q;
	for (i = 0; i <= 9; i++)
	{
		if (i % 2 == 0)
			q.push_front(a[i]);
		else
			q.push_back(a[i]);
	}                                  /*此時隊列里的內(nèi)容是: {8,6,4,2,0,1,3,5,7,9}*/
	q.pop_front();
	printf("%dn", q.front());    /*清除第一個元素后輸出第一個(6)*/
	q.pop_back();
	printf("%dn", q.back());     /*清除最后一個元素后輸出最后一個(7)*/
	deque< int >::iterator it;
	for (it = q.begin(); it != q.end(); it++) {
		cout < < *it < < 't';
	}
	cout < < endl;
	system("pause");
	return 0;
}

輸出結(jié)果：

3.3 list

3.3.1 list定義

List是stl實現(xiàn)的雙向鏈表，與向量(vectors)相比, 它允許快速的插入和刪除，但是隨機訪問卻比較慢。使用時需要添加頭文件

#include

3.3.2 list定義和初始化

listlst1; //創(chuàng)建空list

list lst2(5); //創(chuàng)建含有5個元素的list

listlst3(3,2); //創(chuàng)建含有3個元素的list

listlst4(lst2); //使用lst2初始化lst4

listlst5(lst2.begin(),lst2.end()); //同lst4

3.3.3 list常用操作函數(shù)

Lst1.assign() 給list賦值

Lst1.back() 返回最后一個元素

Lst1.begin() 返回指向第一個元素的迭代器

Lst1.clear() 刪除所有元素

Lst1.empty() 如果list是空的則返回true

Lst1.end() 返回末尾的迭代器

Lst1.erase() 刪除一個元素

Lst1.front() 返回第一個元素

Lst1.get_allocator() 返回list的配置器

Lst1.insert() 插入一個元素到list中

Lst1.max_size() 返回list能容納的最大元素數(shù)量

Lst1.merge() 合并兩個list

Lst1.pop_back() 刪除最后一個元素

Lst1.pop_front() 刪除第一個元素

Lst1.push_back() 在list的末尾添加一個元素

Lst1.push_front() 在list的頭部添加一個元素

Lst1.rbegin() 返回指向第一個元素的逆向迭代器

Lst1.remove() 從list刪除元素

Lst1.remove_if() 按指定條件刪除元素

Lst1.rend() 指向list末尾的逆向迭代器

Lst1.resize() 改變list的大小

Lst1.reverse() 把list的元素倒轉(zhuǎn)

Lst1.size() 返回list中的元素個數(shù)

Lst1.sort() 給list排序

Lst1.splice() 合并兩個list

Lst1.swap() 交換兩個list

Lst1.unique() 刪除list中相鄰重復(fù)的元素

3.3.4 List使用實例

3.3.4.1 迭代器遍歷list

for(list< int >::const_iteratoriter = lst1.begin();iter != lst1.end();iter++)
    {
      cout< iter;
    }
    cout<

3.3.4.2 綜合實例1

#include < iostream >
#include < list >
#include < numeric >
#include < algorithm >
using namespace std;

typedef list< int > LISTINT;
typedef list< int > LISTCHAR;

void main()
{
	//用LISTINT創(chuàng)建一個list對象
	LISTINT listOne;
	//聲明i為迭代器
	LISTINT::iterator i;

	listOne.push_front(3);
	listOne.push_front(2);
	listOne.push_front(1);

	listOne.push_back(4);
	listOne.push_back(5);
	listOne.push_back(6);

	cout < < "listOne.begin()--- listOne.end():" < < endl;
	for (i = listOne.begin(); i != listOne.end(); ++i)
		cout < < *i < < " ";
	cout < < endl;

	LISTINT::reverse_iterator ir;
	cout < < "listOne.rbegin()---listOne.rend():" < < endl;
	for (ir = listOne.rbegin(); ir != listOne.rend(); ir++) {
		cout < < *ir < < " ";
	}
	cout < < endl;

	int result = accumulate(listOne.begin(), listOne.end(), 0);
	cout < < "Sum=" < < result < < endl;
	cout < < "------------------" < < endl;

	//用LISTCHAR創(chuàng)建一個list對象
	LISTCHAR listTwo;
	//聲明i為迭代器
	LISTCHAR::iterator j;

	listTwo.push_front('C');
	listTwo.push_front('B');
	listTwo.push_front('A');

	listTwo.push_back('D');
	listTwo.push_back('E');
	listTwo.push_back('F');

	cout < < "listTwo.begin()---listTwo.end():" < < endl;
	for (j = listTwo.begin(); j != listTwo.end(); ++j)
		cout < < char(*j) < < " ";
	cout < < endl;

	j = max_element(listTwo.begin(), listTwo.end());
	cout < < "The maximum element in listTwo is: " < < char(*j) < < endl;
	system("pause");
}

輸出結(jié)果

3.3.4.3 綜合實例2

#include < iostream > 
#include < list > 

using namespace std;
typedef list< int > INTLIST;

//從前向后顯示list隊列的全部元素 
void put_list(INTLIST list, char *name)
{
	INTLIST::iterator plist;

	cout < < "The contents of " < < name < < " : ";
	for (plist = list.begin(); plist != list.end(); plist++)
		cout < < *plist < < " ";
	cout < < endl;
}

//測試list容器的功能 
void main(void)
{
	//list1對象初始為空 
	INTLIST list1;
	INTLIST list2(5, 1);
	INTLIST list3(list2.begin(), --list2.end());

	//聲明一個名為i的雙向迭代器 
	INTLIST::iterator i;

	put_list(list1, "list1");
	put_list(list2, "list2");
	put_list(list3, "list3");

	list1.push_back(7);
	list1.push_back(8);
	cout < < "list1.push_back(7) and list1.push_back(8):" < < endl;
	put_list(list1, "list1");

	list1.push_front(6);
	list1.push_front(5);
	cout < < "list1.push_front(6) and list1.push_front(5):" < < endl;
	put_list(list1, "list1");

	list1.insert(++list1.begin(), 3, 9);
	cout < < "list1.insert(list1.begin()+1,3,9):" < < endl;
	put_list(list1, "list1");

	//測試引用類函數(shù) 
	cout < < "list1.front()=" < < list1.front() < < endl;
	cout < < "list1.back()=" < < list1.back() < < endl;

	list1.pop_front();
	list1.pop_back();
	cout < < "list1.pop_front() and list1.pop_back():" < < endl;
	put_list(list1, "list1");

	list1.erase(++list1.begin());
	cout < < "list1.erase(++list1.begin()):" < < endl;
	put_list(list1, "list1");

	list2.assign(8, 1);
	cout < < "list2.assign(8,1):" < < endl;
	put_list(list2, "list2");

	cout < < "list1.max_size(): " < < list1.max_size() < < endl;
	cout < < "list1.size(): " < < list1.size() < < endl;
	cout < < "list1.empty(): " < < list1.empty() < < endl;

	put_list(list1, "list1");
	put_list(list3, "list3");
	cout < < "list1 >list3: " < < (list1 > list3) < < endl;
	cout < < "list1< list3: " < < (list1 < list3) < < endl;

	list1.sort();
	put_list(list1, "list1");

	list1.splice(++list1.begin(), list3);
	put_list(list1, "list1");
	put_list(list3, "list3");
	system("pause");
}

輸出結(jié)果：

3.4 map/multimap

map和multimap都需要#include，唯一的不同是，map的鍵值key不可重復(fù)，而multimap可以，也正是由于這種區(qū)別，map支持[ ]運算符，multimap不支持[ ]運算符。在用法上沒什么區(qū)別。

C++中map提供的是一種鍵值對容器，里面的數(shù)據(jù)都是成對出現(xiàn)的,如下圖：每一對中的第一個值稱之為關(guān)鍵字(key)，每個關(guān)鍵字只能在map中出現(xiàn)一次；第二個稱之為該關(guān)鍵字的對應(yīng)值。

Map是STL的一個關(guān)聯(lián)容器，它提供一對一（其中第一個可以稱為關(guān)鍵字，每個關(guān)鍵字只能在map中出現(xiàn)一次，第二個可能稱為該關(guān)鍵字的值）的數(shù)據(jù) 處理能力，由于這個特性，它完成有可能在我們處理一對一數(shù)據(jù)的時候，在編程上提供快速通道。這里說下map內(nèi)部數(shù)據(jù)的組織，map內(nèi)部自建一顆紅黑樹(一種非嚴格意義上的平衡二叉樹)，這顆樹具有對數(shù)據(jù)自動排序的功能，所以在map內(nèi)部所有的數(shù)據(jù)都是有序的。

3.4.1 基本操作函數(shù)

begin() 返回指向map頭部的迭代器

clear(）刪除所有元素

count() 返回指定元素出現(xiàn)的次數(shù)

empty() 如果map為空則返回true

end() 返回指向map末尾的迭代器

equal_range() 返回特殊條目的迭代器對

erase() 刪除一個元素

find() 查找一個元素

get_allocator() 返回map的配置器

insert() 插入元素

key_comp() 返回比較元素key的函數(shù)

lower_bound() 返回鍵值>=給定元素的第一個位置

max_size() 返回可以容納的最大元素個數(shù)

rbegin() 返回一個指向map尾部的逆向迭代器

rend() 返回一個指向map頭部的逆向迭代器

size() 返回map中元素的個數(shù)

swap() 交換兩個map

upper_bound() 返回鍵值>給定元素的第一個位置

value_comp() 返回比較元素value的函數(shù)

3.4.2 聲明

//頭文件
#include< map >

map< int, string > ID_Name;

// 使用{}賦值是從c++11開始的，因此編譯器版本過低時會報錯，如visual studio 2012
map< int, string > ID_Name = {
                { 2015, "Jim" },
                { 2016, "Tom" },
                { 2017, "Bob" } };

3.4.3 迭代器

共有八個獲取迭代器的函數(shù)：* begin, end, rbegin,rend* 以及對應(yīng)的 * cbegin, cend, crbegin,crend*。

二者的區(qū)別在于，后者一定返回 const_iterator，而前者則根據(jù)map的類型返回iterator 或者 const_iterator。const情況下，不允許對值進行修改。如下面代碼所示：

map< int,int >::iterator it;
map< int,int > mmap;
const map< int,int > const_mmap;

it = mmap.begin(); //iterator
mmap.cbegin(); //const_iterator

const_mmap.begin(); //const_iterator
const_mmap.cbegin(); //const_iterator

返回的迭代器可以進行加減操作，此外，如果map為空，則 begin = end。

3.4.4 插入操作

3.4.4.1 用insert插入pair數(shù)據(jù)

//數(shù)據(jù)的插入--第一種：用insert函數(shù)插入pair數(shù)據(jù)  
#include < map >    
#include < string >  
#include < iostream >  
using namespace std;  

int main()  
{  
    map< int, string > mapStudent;  
    mapStudent.insert(pair< int, string >(1, "student_one"));  
    mapStudent.insert(pair< int, string >(2, "student_two"));  
    mapStudent.insert(pair< int, string >(3, "student_three"));  
    map< int, string >::iterator iter;  
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
       cout<

3.4.4.2 用insert函數(shù)插入value_type數(shù)據(jù)

//第二種：用insert函數(shù)插入value_type數(shù)據(jù)，下面舉例說明  

#include < map >    
#include < string >    
#include < iostream >    
using namespace std;  

int main()    
{    
    map< int, string > mapStudent;    
    mapStudent.insert(map< int, string >::value_type (1, "student_one"));    
    mapStudent.insert(map< int, string >::value_type (2, "student_two"));    
    mapStudent.insert(map< int, string >::value_type (3, "student_three"));    
    map< int, string >::iterator iter;    
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
         cout<

3.4.4.3 用insert函數(shù)進行多個插入

insert共有4個重載函數(shù)：

// 插入單個鍵值對，并返回插入位置和成功標志，插入位置已經(jīng)存在值時，插入失敗
pair< iterator,bool > insert (const value_type& val);

//在指定位置插入，在不同位置插入效率是不一樣的，因為涉及到重排
iterator insert (const_iterator position, const value_type& val);

// 插入多個
void insert (InputIterator first, InputIterator last);

//c++11開始支持，使用列表插入多個   
void insert (initializer_list< value_type > il);

下面是具體使用示例：

#include < iostream >
#include < map >

int main()
{
    std::map< char, int > mymap;

    // 插入單個值
    mymap.insert(std::pair< char, int >('a', 100));
    mymap.insert(std::pair< char, int >('z', 200));

    //返回插入位置以及是否插入成功
    std::pair< std::map< char, int >::iterator, bool > ret;
    ret = mymap.insert(std::pair< char, int >('z', 500));
    if (ret.second == false) {
        std::cout < < "element 'z' already existed";
        std::cout < < " with a value of " < < ret.first- >second < < 'n';
    }

    //指定位置插入
    std::map< char, int >::iterator it = mymap.begin();
    mymap.insert(it, std::pair< char, int >('b', 300));  //效率更高
    mymap.insert(it, std::pair< char, int >('c', 400));  //效率非最高

    //范圍多值插入
    std::map< char, int > anothermap;
    anothermap.insert(mymap.begin(), mymap.find('c'));

    // 列表形式插入
    anothermap.insert({ { 'd', 100 }, {'e', 200} });

    return 0;
}

3.4.4.4 用數(shù)組方式插入數(shù)據(jù)

//第三種：用數(shù)組方式插入數(shù)據(jù)，下面舉例說明  

#include < map >    
#include < string >    
#include < iostream >    
using namespace std;  

int main()    
{    
    map< int, string > mapStudent;    
    mapStudent[1] = "student_one";   
    mapStudent[2] = "student_two";    
    mapStudent[3] = "student_three";    
    map< int, string >::iterator iter;    
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)    
        cout<

以上三種用法，雖然都可以實現(xiàn)數(shù)據(jù)的插入，但是它們是有區(qū)別的，當(dāng)然了第一種和第二種在效果上是完成一樣的，用insert函數(shù)插入數(shù)據(jù)，在數(shù)據(jù)的插入上涉及到集合的唯一性這個概念，即當(dāng)map中有這個關(guān)鍵字時，insert操作是插入數(shù)據(jù)不了的，但是用數(shù)組方式就不同了，它可以覆蓋以前該關(guān)鍵字對應(yīng)的值，用程序說明

mapStudent.insert(map::value_type (1, "student_one"));

mapStudent.insert(map::value_type (1, "student_two"));

上面這兩條語句執(zhí)行后，map中1這個關(guān)鍵字對應(yīng)的值是“student_one”，第二條語句并沒有生效，那么這就涉及到我們怎么知道insert語句是否插入成功的問題了，可以用pair來獲得是否插入成功，程序如下

pair::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map::value_type (1, "student_one"));

我們通過pair的第二個變量來知道是否插入成功，它的第一個變量返回的是一個map的迭代器，如果插入成功的話Insert_Pair.second應(yīng)該是true的，否則為false。

下面給出完成代碼，演示插入成功與否問題

//驗證插入函數(shù)的作用效果  
#include < map >    
#include < string >    
#include < iostream >    
using namespace std;  

int main()    
{  
    map< int, string > mapStudent;  
    pair< map< int, string >::iterator, bool > Insert_Pair;    
    Insert_Pair = mapStudent.insert(pair< int, string >(1, "student_one"));    
    if(Insert_Pair.second == true)  
        cout< "Insert Successfully"<

大家可以用如下程序，看下用數(shù)組插入在數(shù)據(jù)覆蓋上的效果

//驗證數(shù)組形式插入數(shù)據(jù)的效果   
#include < map >    
#include < string >    
#include < iostream >    
using namespace std;  

int main()    
{    
    map< int, string > mapStudent;    
    mapStudent[1] = "student_one";    
    mapStudent[1] = "student_two";    
    mapStudent[2] = "student_three";    
    map< int, string >::iterator iter;    
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)    
       cout<

3.4.5 查找、刪除、交換

查找

// 關(guān)鍵字查詢，找到則返回指向該關(guān)鍵字的迭代器，否則返回指向end的迭代器
// 根據(jù)map的類型，返回的迭代器為 iterator 或者 const_iterator
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

刪除

// 刪除迭代器指向位置的鍵值對，并返回一個指向下一元素的迭代器
iterator erase( iterator pos )

// 刪除一定范圍內(nèi)的元素，并返回一個指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );

// 根據(jù)Key來進行刪除， 返回刪除的元素數(shù)量，在map里結(jié)果非0即1
size_t erase( const key_type& key );

// 清空map，清空后的size為0
void clear();

交換

// 就是兩個map的內(nèi)容互換
void swap( map& other );

3.4.6 容量

// 查詢map是否為空
bool empty();

// 查詢map中鍵值對的數(shù)量
size_t size();

// 查詢map所能包含的最大鍵值對數(shù)量，和系統(tǒng)和應(yīng)用庫有關(guān)。
// 此外，這并不意味著用戶一定可以存這么多，很可能還沒達到就已經(jīng)開辟內(nèi)存失敗了
size_t max_size();

// 查詢關(guān)鍵字為key的元素的個數(shù)，在map里結(jié)果非0即1
size_t count( const Key& key ) const; //

3.4.7 排序

map中的元素是自動按Key升序排序，所以不能對map用sort函數(shù)；

這里要講的是一點比較高深的用法了,排序問題，STL中默認是采用小于號來排序的，以上代碼在排序上是不存在任何問題的，因為上面的關(guān)鍵字是int 型，它本身支持小于號運算，在一些特殊情況，比如關(guān)鍵字是一個結(jié)構(gòu)體或者自定義類，涉及到排序就會出現(xiàn)問題，因為它沒有小于號操作，insert等函數(shù)在編譯的時候過不去，下面給出兩個方法解決這個問題。

3.4.7.1 小于號 < 重載

#include < iostream >  
#include < string >  
#include < map >  
using namespace std;

typedef struct tagStudentinfo
{
	int      niD;
	string   strName;
	bool operator < (tagStudentinfo const& _A) const
	{     //這個函數(shù)指定排序策略，按niD排序，如果niD相等的話，按strName排序  
		if (niD < _A.niD) return true;
		if (niD == _A.niD)
			return strName.compare(_A.strName) < 0;
		return false;
	}
}Studentinfo, *PStudentinfo; //學(xué)生信息  

int main()
{
	int nSize;   //用學(xué)生信息映射分數(shù)  
	map< Studentinfo, int >mapStudent;
	map< Studentinfo, int >::iterator iter;
	Studentinfo studentinfo;
	studentinfo.niD = 1;
	studentinfo.strName = "student_one";
	mapStudent.insert(pair< Studentinfo, int >(studentinfo, 90));
	studentinfo.niD = 2;
	studentinfo.strName = "student_two";
	mapStudent.insert(pair< Studentinfo, int >(studentinfo, 80));
	for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
		cout < < iter- >first.niD < < ' ' < < iter- >first.strName < < ' ' < < iter- >second < < endl;
	return 0;
}

3.4.7.2 仿函數(shù)的應(yīng)用，這個時候結(jié)構(gòu)體中沒有直接的小于號重載

//第二種：仿函數(shù)的應(yīng)用，這個時候結(jié)構(gòu)體中沒有直接的小于號重載，程序說明  

#include < iostream >  
#include < map >  
#include < string >  
using namespace std;

typedef struct tagStudentinfo
{
	int      niD;
	string   strName;
}Studentinfo, *PStudentinfo; //學(xué)生信息  

class sort
{
public:
	bool operator() (Studentinfo const &_A, Studentinfo const &_B) const
	{
		if (_A.niD < _B.niD)
			return true;
		if (_A.niD == _B.niD)
			return _A.strName.compare(_B.strName) < 0;
		return false;
	}
};

int main()
{   
	//用學(xué)生信息映射分數(shù)  
	map< Studentinfo, int, sort >mapStudent;
	map< Studentinfo, int >::iterator iter;
	Studentinfo studentinfo;
	studentinfo.niD = 1;
	studentinfo.strName = "student_one";
	mapStudent.insert(pair< Studentinfo, int >(studentinfo, 90));
	studentinfo.niD = 2;
	studentinfo.strName = "student_two";
	mapStudent.insert(pair< Studentinfo, int >(studentinfo, 80));
	for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
		cout < < iter- >first.niD < < ' ' < < iter- >first.strName < < ' ' < < iter- >second < < endl;
	system("pause");
}

3.4.8 unordered_map

在c++11標準前，c++標準庫中只有一種map，但是它的底層實現(xiàn)并不是適合所有的場景，如果我們需要其他適合的map實現(xiàn)就不得不使用比如boost庫等三方的實現(xiàn)，在c++11中加了一種map unordered_map,unordered_set,他們的實現(xiàn)有什么不同呢？

map底層采用的是紅黑樹的實現(xiàn)查詢的時間復(fù)雜度為O(logn),看起來并沒有unordered_map快，但是也要看實際的數(shù)據(jù)量，雖然unordered_map的查詢從算法上分析比map快，但是它有一些其它的消耗，比如哈希函數(shù)的構(gòu)造和分析，還有如果出現(xiàn)哈希沖突解決哈希沖突等等都有一定的消耗，因此unordered_map的效率在很大的程度上由它的hash函數(shù)算法決定，而紅黑樹的效率是一個穩(wěn)定值。

unordered_map的底層采用哈希表的實現(xiàn)，查詢的時間復(fù)雜度為是O(1)。所以unordered_map內(nèi)部就是無序的，數(shù)據(jù)是按散列函數(shù)插入到槽里面去的，數(shù)據(jù)之間無順序可言，如果我們不需要內(nèi)部有序，這種實現(xiàn)是沒有問題的。unordered_map屬于關(guān)聯(lián)式容器，采用std::pair保存key-value形式的數(shù)據(jù)。用法與map一致。特別的是，STL中的map因為是有序的二叉樹存儲，所以對key值需要有大小的判斷，當(dāng)使用內(nèi)置類型時，無需重載operator < ；但是用用戶自定義類型的話，就需要重載operator < 。 unoredered_map全程使用不需要比較元素的key值的大小，但是，對于元素的==要有判斷，又因為需要使用hash映射，所以，對于非內(nèi)部類型，需要程序員為其定義這二者的內(nèi)容，對于內(nèi)部類型，就不需要了。unordered庫使用“桶”來存儲元素，散列值相同的被存儲在一個桶里。當(dāng)散列容器中有大量數(shù)據(jù)時，同一個桶里的數(shù)據(jù)也會增多，造成訪問沖突，降低性能。為了提高散列容器的性能，unordered庫會在插入元素是自動增加桶的數(shù)量，不需要用戶指定。但是，用戶也可以在構(gòu)造函數(shù)或者rehash()函數(shù)中，指定最小的桶的數(shù)量。

還有另外一點從占用內(nèi)存上來說因為unordered_map才用hash結(jié)構(gòu)會有一定的內(nèi)存損失，它的內(nèi)存占用回高于map。

最后就是她們的場景了，首先如果你需要對map中的數(shù)據(jù)排序，就首選map，他會把你的數(shù)據(jù)按照key的自然排序排序（由于它的底層實現(xiàn)紅黑樹機制所以會排序），如果不需要排序，就看你對內(nèi)存和cpu的選擇了，不過一般都會選擇unordered_map，它的查找效率會更高。

至于使用方法和函數(shù)，兩者差不多，由于篇幅限制這里不再贅述，unordered_multimap用法亦可類推。

3.5 set/multiset

std::set 是關(guān)聯(lián)容器，含有 Key 類型對象的已排序集。用比較函數(shù)compare進行排序。搜索、移除和插入擁有對數(shù)復(fù)雜度。 set 通常以紅黑樹實現(xiàn)。

set容器內(nèi)的元素會被自動排序，set與map不同，set中的元素即是鍵值又是實值，set不允許兩個元素有相同的鍵值。不能通過set的迭代器去修改set元素，原因是修改元素會破壞set組織。當(dāng)對容器中的元素進行插入或者刪除時，操作之前的所有迭代器在操作之后依然有效。

由于set元素是排好序的，且默認為升序，因此當(dāng)set集合中的元素為結(jié)構(gòu)體或自定義類時，該結(jié)構(gòu)體或自定義類必須實現(xiàn)運算符‘<’的重載。

multiset特性及用法和set完全相同，唯一的差別在于它允許鍵值重復(fù)。

set和multiset的底層實現(xiàn)是一種高效的平衡二叉樹，即紅黑樹（Red-Black Tree）。

3.5.1 set常用成員函數(shù)

begin()--返回指向第一個元素的迭代器
clear()--清除所有元素
count()--返回某個值元素的個數(shù)
empty()--如果集合為空，返回true
end()--返回指向最后一個元素的迭代器
equal_range()--返回集合中與給定值相等的上下限的兩個迭代器
erase()--刪除集合中的元素
find()--返回一個指向被查找到元素的迭代器
get_allocator()--返回集合的分配器
insert()--在集合中插入元素
lower_bound()--返回指向大于（或等于）某值的第一個元素的迭代器
key_comp()--返回一個用于元素間值比較的函數(shù)
max_size()--返回集合能容納的元素的最大限值
rbegin()--返回指向集合中最后一個元素的反向迭代器
rend()--返回指向集合中第一個元素的反向迭代器
size()--集合中元素的數(shù)目
swap()--交換兩個集合變量
upper_bound()--返回大于某個值元素的迭代器
value_comp()--返回一個用于比較元素間的值的函數(shù)

3.5.2 代碼示例

以下代碼涉及的內(nèi)容：

1、set容器中，元素類型為基本類型，如何讓set按照用戶意愿來排序？

2、set容器中，如何讓元素類型為自定義類型？

3、set容器的insert函數(shù)的返回值為什么類型？

#include < iostream >
#include < string >
#include < set >
using namespace std;

/* 仿函數(shù)CompareSet，在test02使用 */
class CompareSet
{
public:
    //從大到小排序
    bool operator()(int v1, int v2)
{
        return v1 > v2;
    }
    //從小到大排序
    //bool operator()(int v1, int v2)
    //{
    //    return v1 < v2;
    //}
};

/* Person類，用于test03 */
class Person
{
    friend ostream &operator< const Person &person);
public:
    Person(string name, int age)
    {
        mName = name;
        mAge = age;
    }
public:
    string mName;
    int mAge;
};

ostream &operator< const Person &person)
{
    out < < "name:" < < person.mName < < " age:" < < person.mAge < < endl;
    return out;
}

/* 仿函數(shù)ComparePerson,用于test03 */
class ComparePerson
{
public:
    //名字大的在前面，如果名字相同，年齡大的排前面
    bool operator()(const Person &p1, const Person &p2)
{
        if (p1.mName == p2.mName)
        {
            return p1.mAge > p2.mAge;
        }
        return p1.mName > p2.mName;
    }
};

/* 打印set類型的函數(shù)模板 */
template< typename T >
void PrintSet(T &s)
{
    for (T::iterator iter = s.begin(); iter != s.end(); ++iter)
        cout < < *iter < < " ";
    cout < < endl;
}

void test01()
{
    //set容器默認從小到大排序
    set< int > s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    //輸出set
    PrintSet(s);
    //結(jié)果為:10 20 30

    /* set的insert函數(shù)返回值為一個對組(pair)。
       對組的第一個值first為set類型的迭代器：
       1、若插入成功，迭代器指向該元素。
       2、若插入失敗，迭代器指向之前已經(jīng)存在的元素
       對組的第二個值seconde為bool類型：
       1、若插入成功，bool值為true
       2、若插入失敗，bool值為false
    */
    pair< set< int >::iterator, bool > ret = s.insert(40);
    if (true == ret.second)
        cout < < *ret.first < < " 插入成功" < < endl;
    else
        cout < < *ret.first < < " 插入失敗" < < endl;
}

void test02()
{
    /* 如果想讓set容器從大到小排序，需要給set容
       器提供一個仿函數(shù),本例的仿函數(shù)為CompareSet
    */
    set< int, CompareSet > s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    //打印set
    PrintSet(s);
    //結(jié)果為:30,20,10
}

void test03()
{
    /* set元素類型為Person，當(dāng)set元素類型為自定義類型的時候
       必須給set提供一個仿函數(shù)，用于比較自定義類型的大小，
       否則無法通過編譯 
    */
    set< Person,ComparePerson > s;
    s.insert(Person("John", 22));
    s.insert(Person("Peter", 25));
    s.insert(Person("Marry", 18));
    s.insert(Person("Peter", 36));

    //打印set
    PrintSet(s);
}

int main(void)
{
    //test01();
    //test02();
    //test03();
    return 0;
}

multiset容器的insert函數(shù)返回值為什么？

#include < iostream >
#include < set >
using namespace std;

/* 打印set類型的函數(shù)模板 */
template< typename T >
void PrintSet(T &s)
{
    for (T::iterator iter = s.begin(); iter != s.end(); ++iter)
        cout < < *iter < < " ";
    cout < < endl;
}

void test(void)
{
    multiset< int > s;
    s.insert(10);
    s.insert(20);
    s.insert(30);

    //打印multiset
    PrintSet(s);

    /* multiset的insert函數(shù)返回值為multiset類型的迭代器，
       指向新插入的元素。multiset允許插入相同的值，因此
       插入一定成功，因此不需要返回bool類型。
    */
    multiset< int >::iterator iter = s.insert(10);

    cout < < *iter < < endl;    
}

int main(void)
{
    test();
    return 0;
}

3.5.3 unordered_set

C++ 11中出現(xiàn)了兩種新的關(guān)聯(lián)容器:unordered_set和unordered_map，其內(nèi)部實現(xiàn)與set和map大有不同，set和map內(nèi)部實現(xiàn)是基于RB-Tree，而unordered_set和unordered_map內(nèi)部實現(xiàn)是基于哈希表(hashtable)，由于unordered_set和unordered_map內(nèi)部實現(xiàn)的公共接口大致相同，所以本文以unordered_set為例。

unordered_set是基于哈希表，因此要了解unordered_set，就必須了解哈希表的機制。哈希表是根據(jù)關(guān)鍵碼值而進行直接訪問的數(shù)據(jù)結(jié)構(gòu)，通過相應(yīng)的哈希函數(shù)(也稱散列函數(shù))處理關(guān)鍵字得到相應(yīng)的關(guān)鍵碼值，關(guān)鍵碼值對應(yīng)著一個特定位置，用該位置來存取相應(yīng)的信息，這樣就能以較快的速度獲取關(guān)鍵字的信息。比如：現(xiàn)有公司員工的個人信息（包括年齡），需要查詢某個年齡的員工個數(shù)。由于人的年齡范圍大約在[0，200]，所以可以開一個200大小的數(shù)組，然后通過哈希函數(shù)得到key對應(yīng)的key-value，這樣就能完成統(tǒng)計某個年齡的員工個數(shù)。而在這個例子中，也存在這樣一個問題，兩個員工的年齡相同，但其他信息（如：名字、身份證）不同，通過前面說的哈希函數(shù)，會發(fā)現(xiàn)其都位于數(shù)組的相同位置，這里，就涉及到“沖突”。準確來說，沖突是不可避免的，而解決沖突的方法常見的有：開發(fā)地址法、再散列法、鏈地址法(也稱拉鏈法)。而unordered_set內(nèi)部解決沖突采用的是----鏈地址法，當(dāng)用沖突發(fā)生時把具有同一關(guān)鍵碼的數(shù)據(jù)組成一個鏈表。下圖展示了鏈地址法的使用:

使用unordered_set需要包含#include頭文件，同unordered_map類似，用法沒有什么太大的區(qū)別，參考set/multiset。

除此之外unordered_multiset也是一種可選的容器。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。舉報投訴

C++

C++

+關(guān)注

關(guān)注
22

文章
2120

瀏覽量
76577
STL

STL

+關(guān)注

關(guān)注
0

文章
86

瀏覽量
19080
數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)

+關(guān)注

關(guān)注
3

文章
573

瀏覽量
41233
程序設(shè)計

程序設(shè)計

+關(guān)注

關(guān)注
3

文章
263

瀏覽量
31492