C++STL教程

2020 年 12 月 24 日
筆記
C++STL的使用

1 什麼是STL？

STL（Standard Template Library），即標準模板庫，是一個具有工業強度的，高效的C++程式庫。它被容納於C++標準程式庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在電腦科學領域裡所常用的基本數據結構和基本演算法。為廣大C++程式設計師們提供了一個可擴展的應用框架，高度體現了軟體的可復用性。

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

STL另一個重要特性是它不是面向對象的。為了具有足夠通用性，STL主要依賴於模板而不是封裝，繼承和虛函數（多態性）——OOP的三個要素。你在STL中找不到任何明顯的類繼承關係。這好像是一種倒退，但這正好是使得STL的組件具有廣泛通用性的底層特徵。另外，由於STL是基於模板，內聯函數的使用使得生成的程式碼短小高效；

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

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

2 STL內容介紹

STL中六大組件：

容器（Container），是一種數據結構，如list，vector，和deques ，以模板類的方法提供。為了訪問容器中的數據，可以使用由容器類輸出的迭代器；
迭代器（Iterator），提供了訪問容器中對象的方法。例如，可以使用一對迭代器指定list或vector中的一定範圍的對象。迭代器就如同一個指針。事實上，C++的指針也是一種迭代器。但是，迭代器也可以是那些定義了operator*()以及其他類似於指針的操作符地方法的類對象；
演算法（Algorithm），是用來操作容器中的數據的模板函數。例如，STL用sort()來對一個vector中的數據進行排序，用find()來搜索一個list中的對象，函數本身與他們操作的數據的結構和類型無關，因此他們可以在從簡單數組到高度複雜容器的任何數據結構上使用；
仿函數（Functor）
適配器（Adaptor）
分配器（allocator）

2.1 容器

STL中的容器有隊列容器和關聯容器，容器適配器（congtainer adapters：stack,queue，priority queue），位集（bit_set），串包(string_package)等等。
（1）序列式容器（Sequence containers），每個元素都有固定位置－－取決於插入時機和地點，和元素值無關，vector、deque、list；
Vector：將元素置於一個動態數組中加以管理，可以隨機存取元素（用索引直接存取），數組尾部添加或移除元素非常快速。但是在中部或頭部安插元素比較費時；
Deque：是「double-ended queue」的縮寫，可以隨機存取元素（用索引直接存取），數組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費時；
List：雙向鏈表，不提供隨機存取（按順序走到需存取的元素，O(n)），在任何位置上執行插入或刪除動作都非常迅速，內部只需調整一下指針；
（2）關聯式容器（Associated containers），元素位置取決於特定的排序準則，和插入順序無關，set、multiset、map、multimap等。
Set/Multiset：內部的元素依據其值自動排序，Set內的相同數值的元素只能出現一次，Multisets內可包含多個數值相同的元素，內部由二叉樹實現，便於查找；
Map/Multimap：Map的元素是成對的鍵值/實值，內部的元素依據其值自動排序，Map內的相同數值的元素只能出現一次，Multimaps內可包含多個數值相同的元素，內部由二叉樹實現，便於查找；

容器類自動申請和釋放記憶體，無需new和delete操作。

2.2 STL迭代器

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

迭代器的作用：能夠讓迭代器與演算法不干擾的相互發展，最後又能無間隙的粘合起來，重載了*，＋＋，＝＝，！＝，＝運算符。用以操作複雜的數據結構，容器提供迭代器，演算法使用迭代器；常見的一些迭代器類型：iterator、const_iterator、reverse_iterator和const_reverse_iterator.

2.3 演算法

函數庫對數據類型的選擇對其可重用性起著至關重要的作用。舉例來說，一個求方根的函數，在使用浮點數作為其參數類型的情況下的可重用性肯定比使用整型作為它的參數類性要高。而C++通過模板的機制允許推遲對某些類型的選擇，直到真正想使用模板或者說對模板進行特化的時候，STL就利用了這一點提供了相當多的有用演算法。它是在一個有效的框架中完成這些演算法的——你可以將所有的類型劃分為少數的幾類，然後就可以在模版的參數中使用一種類型替換掉同一種類中的其他類型。
STL提供了大約100個實現演算法的模版函數，比如演算法for_each將為指定序列中的每一個元素調用指定的函數，stable_sort以你所指定的規則對序列進行穩定性排序等等。只要我們熟悉了STL之後，許多程式碼可以被大大的化簡，只需要通過調用一兩個演算法模板，就可以完成所需要的功能並大大地提升效率。
演算法部分主要由頭文件<algorithm>，<numeric>和<functional>組成。
<algorithm>是所有STL頭文件中最大的一個（儘管它很好理解），它是由一大堆模版函數組成的，可以認為每個函數在很大程度上都是獨立的，其中常用到的功能範圍涉及到比較、交換、查找、遍歷操作、複製、修改、移除、反轉、排序、合併等等。
<numeric>體積很小，只包括幾個在序列上面進行簡單數學運算的模板函數，包括加法和乘法在序列上的一些操作。
<functional>中則定義了一些模板類，用以聲明函數對象。
STL中演算法大致分為四類：

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

以下對所有演算法進行細緻分類並標明功能：
<一>查找演算法(13個)：判斷容器中是否包含某個值
adjacent_find: 在iterator對標識元素範圍內，查找一對相鄰重複元素，找到則返回指向這對元素的第一個元素的ForwardIterator。否則返回last。重載版本使用輸入的二元操作符代替相等的判斷。
binary_search: 在有序序列中查找value，找到返回true。重載的版本實用指定的比較函數對象或函數指針來判斷相等。
count: 利用等於操作符，把標誌範圍內的元素與輸入值比較，返回相等元素個數。
count_if: 利用輸入的操作符，對標誌範圍內的元素進行操作，返回結果為true的個數。
equal_range: 功能類似equal，返回一對iterator，第一個表示lower_bound，第二個表示upper_bound。
find: 利用底層元素的等於操作符，對指定範圍內的元素與輸入值進行比較。當匹配時，結束搜索，返回該元素的一個InputIterator。
find_end: 在指定範圍內查找”由輸入的另外一對iterator標誌的第二個序列”的最後一次出現。找到則返回最後一對的第一個ForwardIterator，否則返回輸入的”另外一對”的第一個ForwardIterator。重載版本使用用戶輸入的操作符代替等於操作。
find_first_of: 在指定範圍內查找”由輸入的另外一對iterator標誌的第二個序列”中任意一個元素的第一次出現。重載版本中使用了用戶自定義操作符。
find_if: 使用輸入的函數代替等於操作符執行find。
lower_bound: 返回一個ForwardIterator，指向在有序序列範圍內的可以插入指定值而不破壞容器順序的第一個位置。重載函數使用自定義比較操作。
upper_bound: 返回一個ForwardIterator，指向在有序序列範圍內插入value而不破壞容器順序的最後一個位置，該位置標誌一個大於value的值。重載函數使用自定義比較操作。
search:   給出兩個範圍，返回一個ForwardIterator，查找成功指向第一個範圍內第一次出現子序列(第二個範圍)的位置，查找失敗指向last1。重載版本使用自定義的比較操作。
search_n:   在指定範圍內查找val出現n次的子序列。重載版本使用自定義的比較操作。
<二>排序和通用演算法(14個)：提供元素排序策略
inplace_merge: 合併兩個有序序列，結果序列覆蓋兩端範圍。重載版本使用輸入的操作進行排序。
merge: 合併兩個有序序列，存放到另一個序列。重載版本使用自定義的比較。
nth_element:   將範圍內的序列重新排序，使所有小於第n個元素的元素都出現在它前面，而大於它的都出現在後面。重載版本使用自定義的比較操作。
partial_sort:   對序列做部分排序，被排序元素個數正好可以被放到範圍內。重載版本使用自定義的比較操作。
partial_sort_copy: 與partial_sort類似，不過將經過排序的序列複製到另一個容器。
partition: 對指定範圍內元素重新排序，使用輸入的函數，把結果為true的元素放在結果為false的元素之前。
random_shuffle: 對指定範圍內的元素隨機調整次序。重載版本輸入一個隨機數產生操作。
reverse: 將指定範圍內元素重新反序排序。
reverse_copy: 與reverse類似，不過將結果寫入另一個容器。
rotate: 將指定範圍內元素移到容器末尾，由middle指向的元素成為容器第一個元素。
rotate_copy: 與rotate類似，不過將結果寫入另一個容器。
sort: 以升序重新排列指定範圍內的元素。重載版本使用自定義的比較操作。
stable_sort: 與sort類似，不過保留相等元素之間的順序關係。
stable_partition: 與partition類似，不過不保證保留容器中的相對順序。
<三>刪除和替換演算法(15個)
copy: 複製序列
copy_backward: 與copy相同，不過元素是以相反順序被拷貝。
iter_swap: 交換兩個ForwardIterator的值。
remove: 刪除指定範圍內所有等於指定元素的元素。注意，該函數不是真正刪除函數。內置函數不適合使用remove和 remove_if函數。
remove_copy:    將所有不匹配元素複製到一個制定容器，返回OutputIterator指向被拷貝的末元素的下一個位置。
remove_if: 刪除指定範圍內輸入操作結果為true的所有元素。
remove_copy_if: 將所有不匹配元素拷貝到一個指定容器。
replace: 將指定範圍內所有等於vold的元素都用vnew代替。
replace_copy: 與replace類似，不過將結果寫入另一個容器。
replace_if: 將指定範圍內所有操作結果為true的元素用新值代替。
replace_copy_if: 與replace_if，不過將結果寫入另一個容器。
swap: 交換存儲在兩個對象中的值。
swap_range: 將指定範圍內的元素與另一個序列元素值進行交換。
unique: 清除序列中重複元素，和remove類似，它也不能真正刪除元素。重載版本使用自定義比較操作。
unique_copy: 與unique類似，不過把結果輸出到另一個容器。
<四>排列組合演算法(2個)：提供計算給定集合按一定順序的所有可能排列組合
next_permutation: 取出當前範圍內的排列，並重新排序為下一個排列。重載版本使用自定義的比較操作。
prev_permutation: 取出指定範圍內的序列並將它重新排序為上一個序列。如果不存在上一個序列則返回false。重載版本使用自定義的比較操作。
<五>算術演算法(4個)
accumulate: iterator對標識的序列段元素之和，加到一個由val指定的初始值上。重載版本不再做加法，而是傳進來的二元操作符被應用到元素上。
partial_sum: 創建一個新序列，其中每個元素值代表指定範圍內該位置前所有元素之和。重載版本使用自定義操作代替加法。
inner_product: 對兩個序列做內積(對應元素相乘，再求和)並將內積加到一個輸入的初始值上。重載版本使用用戶定義的操作。
adjacent_difference: 創建一個新序列，新序列中每個新值代表當前元素與上一個元素的差。重載版本用指定二元操作計算相鄰元素的差。
<六>生成和異變演算法(6個)
fill: 將輸入值賦給標誌範圍內的所有元素。
fill_n: 將輸入值賦給first到first+n範圍內的所有元素。
for_each: 用指定函數依次對指定範圍內所有元素進行迭代訪問，返回所指定的函數類型。該函數不得修改序列中的元素。
generate: 連續調用輸入的函數來填充指定的範圍。
generate_n: 與generate函數類似，填充從指定iterator開始的n個元素。
transform: 將輸入的操作作用與指定範圍內的每個元素，併產生一個新的序列。重載版本將操作作用在一對元素上，另外一個元素來自輸入的另外一個序列。結果輸出到指定容器。
<七>關係演算法(8個)
equal: 如果兩個序列在標誌範圍內元素都相等，返回true。重載版本使用輸入的操作符代替默認的等於操作符。
includes: 判斷第一個指定範圍內的所有元素是否都被第二個範圍包含，使用底層元素的<操作符，成功返回 true。重載版本使用用戶輸入的函數。
lexicographical_compare: 比較兩個序列。重載版本使用用戶自定義比較操作。
max: 返回兩個元素中較大一個。重載版本使用自定義比較操作。
max_element: 返回一個ForwardIterator，指出序列中最大的元素。重載版本使用自定義比較操作。
min: 返回兩個元素中較小一個。重載版本使用自定義比較操作。
min_element: 返回一個ForwardIterator，指出序列中最小的元素。重載版本使用自定義比較操作。
mismatch: 並行比較兩個序列，指出第一個不匹配的位置，返回一對iterator，標誌第一個不匹配元素位置。如果都匹配，返回每個容器的last。重載版本使用自定義的比較操作。
<八>集合演算法(4個)
set_union:   構造一個有序序列，包含兩個序列中所有的不重複元素。重載版本使用自定義的比較操作。
set_intersection:    構造一個有序序列，其中元素在兩個序列中都存在。重載版本使用自定義的比較操作。
set_difference:   構造一個有序序列，該序列僅保留第一個序列中存在的而第二個中不存在的元素。重載版本使用自定義的比較操作。
set_symmetric_difference: 構造一個有序序列，該序列取兩個序列的對稱差集(並集-交集)。
<九>堆演算法(4個)
make_heap: 把指定範圍內的元素生成一個堆。重載版本使用自定義比較操作。
pop_heap: 並不真正把最大元素從堆中彈出，而是重新排序堆。它把first和last-1交換，然後重新生成一個堆。可使用容器的 back來訪問被”彈出”的元素或者使用pop_back進行真正的刪除。重載版本使用自定義的比較操作。
push_heap: 假設first到last-1是一個有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向該函數前，必須先把元素插入容器後。重載版本使用指定的比較操作。
sort_heap: 對指定範圍內的序列重新排序，它假設該序列是個有序堆。重載版本使用自定義比較操作。

2.4 仿函數

2.4.1 概述

仿函數(functor)，就是使一個類的使用看上去象一個函數。其實現就是類中實現一個operator()，這個類就有了類似函數的行為，就是一個仿函數類了。
　　有些功能的的程式碼，會在不同的成員函數中用到，想復用這些程式碼。

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

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

2.4.2 仿函數(functor)在程式語言中的應用

1）C語言使用函數指針和回調函數來實現仿函數，例如一個用來排序的函數可以這樣使用仿函數

#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);//起始地址，個數，元素大小，回調函數
int x;
for (x = 0; x < 5; x++)
printf(“%i\n”, list[x]);
return 0;
}

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

#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 仿函數在STL中的定義

要使用STL內建的仿函數，必須包含<functional>頭文件。而頭文件中包含的仿函數分類包括

1）算術類仿函數

加：plus<T>

減：minus<T>

乘：multiplies<T>

除：divides<T>

模取：modulus<T>

否定：negate<T>

例子：

#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）關係運算類仿函數

等於：equal_to<T>

不等於：not_equal_to<T>

大於：greater<T>

大於等於：greater_equal<T>

小於：less<T>

小於等於：less_equal<T>

從大到小排序：

#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）邏輯運算仿函數

邏輯與：logical_and<T>

邏輯或：logical_or<T>

邏輯否：logical_no<T>

除了使用STL內建的仿函數，還可使用自定義的仿函數，具體實例見文章3.4.7.2小結

2.5 容器適配器

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

什麼是容器適配器

」適配器是使一種事物的行為類似於另外一種事物行為的一種機制」，適配器對容器進行包裝，使其表現出另外一種行為。例如，stack<int, vector<int> >實現了棧的功能，但其內部使用順序容器vector<int>來存儲數據。（相當於是vector<int>表現出了棧的行為）。

容器適配器

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

#include <stack> //stack

#include<queue> //queue、priority_queue

種類	默認順序容器	可用順序容器	說明
stack	deque	vector、list、deque
queue	deque	list、deque	基礎容器必須提供push_front()運算
priority_queue	vector	vector、deque	基礎容器必須提供隨機訪問功能

定義適配器

1、初始化

stack<int> stk(dep);

2、覆蓋默認容器類型

stack<int,vector<int> > stk;

使用適配器

2.5.1 stack

stack<int> s;
stack< int, vector<int> > stk; //覆蓋基礎容器類型，使用vector實現stk
s.empty(); //判斷stack是否為空，為空返回true，否則返回false
s.size(); //返回stack中元素的個數
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，在基於優先順序的適當位置插入新元素
//queue only:
q.front(); //返回隊首元素的值，但不刪除該元素
q.back(); //返回隊尾元素的值，但不刪除該元素
//priority_queue only:
q.top(); //返回具有最高優先順序的元素值，但不刪除該元素

3 常用容器用法介紹

3.1 vector

3.1.1 基本函數實現

1.構造函數

vector():創建一個空vector
vector(int nSize):創建一個vector,元素個數為nSize
vector(int nSize,const t& t):創建一個vector，元素個數為nSize,且值均為t
vector(const vector&):複製構造函數
vector(begin,end):複製[begin,end)區間內另一個數組的元素到vector中

2.增加函數

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)間的數據

3.刪除函數

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

4.遍歷函數

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

5.判斷函數

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

6.大小函數

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

7.其他函數

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

8.看著清楚

1.push_back 在數組的最後添加一個數據

2.pop_back 去掉數組的最後一個數據

3.at 得到編號位置的數據

4.begin 得到數組頭的指針

5.end 得到數組的最後一個單元+1的指針

6．front 得到數組頭的引用

7.back 得到數組的最後一個單元的引用

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

9.capacity 當前vector分配的大小

10.size 當前使用數據的大小

11.resize 改變當前使用數據的大小，如果它比當前使用的大，者填充默認值

12.reserve 改變當前vecotr所分配空間的大小

13.erase 刪除指針指向的數據項

14.clear 清空當前的vector

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

16.rend 將vector反轉構的結束指針返回(其實就是原來的begin-1)

17.empty 判斷vector是否為空

18.swap 與另一個vector交換數據

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)實例在容器最後移除和插入數據

#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int>obj;//創建一個向量存儲容器 int
for(int i=0;i<10;i++) // push_back(elem)在數組最後添加數據
{
obj.push_back(i);
cout<<obj[i]<<“,”;
}
for(int i=0;i<5;i++)//去掉數組最後一個數據
{
obj.pop_back();
}
cout<<“\n”<<endl;
for(int i=0;i<obj.size();i++)//size()容器中實際數據個數
{
cout<<obj[i]<<“,”;
}
return 0;
}

輸出結果為：

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

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

#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)在數組最後添加數據
{
obj.push_back(i);
cout<<obj[i]<<“,”;
}
obj.clear();//清除容器中所以數據
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<endl;
}
return 0;
}

輸出結果為：

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<<“從小到大:”<<endl;
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<“,”;
}
cout<<“\n”<<endl;
cout<<“從大到小:”<<endl;
reverse(obj.begin(),obj.end());//從大到小
for(int i=0;i<obj.size();i++)
{
cout<<obj[i]<<“,”;
}
return 0;
}

輸出結果為：

從小到大:
0,1,3,
從大到小:
3,1,0,

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

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 訪問（直接數組訪問&迭代器訪問）

#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<<“直接利用數組：”;
for(int i=0;i<10;i++)//方法一
{
cout<<obj[i]<<” “;
}
cout<<endl;
cout<<“利用迭代器：” ;
//方法二，使用迭代器將容器中數據輸出
vector<int>::iterator it;//聲明一個迭代器，來訪問vector容器，作用：遍歷或者指向vector容器的元素
for(it=obj.begin();it!=obj.end();it++)
{
cout<<*it<<” “;
}
return 0;
}

輸出結果為：

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

3.1.4.5 二維數組兩種定義方法（結果一樣）

方法一

#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N=5, M=6;
vector<vector<int> > obj(N); //定義二維動態數組大小5行
for(int i =0; i< obj.size(); i++)//動態二維數組為5行6列，值全為0
{
obj[i].resize(M);
}
for(int i=0; i< obj.size(); i++)//輸出二維動態數組
{
for(int j=0;j<obj[i].size();j++)
{
cout<<obj[i][j]<<” “;
}
cout<<“\n”;
}
return 0;
}

方法二

#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)); //定義二維動態數組5行6列
for(int i=0; i< obj.size(); i++)//輸出二維動態數組
{
for(int j=0;j<obj[i].size();j++)
{
cout<<obj[i][j]<<” “;
}
cout<<“\n”;
}
return 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 0

3.2 deque

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

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

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

deque是一種優化了的對序列兩端元素進行添加和刪除操作的基本序列容器。通常由一些獨立的區塊組成，第一區塊朝某方向擴展，最後一個區塊朝另一方向擴展。它允許較為快速地隨機訪問但它不像vector一樣把所有對象保存在一個連續的記憶體塊，而是多個連續的記憶體塊。並且在一個映射結構中保存對這些塊以及順序的跟蹤。

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範圍內的元素初始化deq

3.2.2 deque的常用成員函數

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好。
可以在內部進行插入和刪除操作，但性能不及list。
deque兩端都能夠快速插入和刪除元素，而vector只能在尾端進行。
deque的元素存取和迭代器操作會稍微慢一些，因為deque的內部結構會多一個間接過程。
deque迭代器是特殊的智慧指針，而不是一般指針，它需要在不同的區塊之間跳轉。
deque可以包含更多的元素，其max_size可能更大，因為不止使用一塊記憶體。
deque不支援對容量和記憶體分配時機的控制。
在除了首尾兩端的其他地方插入和刪除元素，都將會導致指向deque元素的任何pointers、references、iterators失效。不過，deque的記憶體重分配優於vector，因為其內部結構顯示不需要複製所有元素。
deque的記憶體區塊不再被使用時，會被釋放，deque的記憶體大小是可縮減的。不過，是不是這麼做以及怎麼做由實際操作版本定義。
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]);
} /*此時隊列里的內容是: {8,6,4,2,0,1,3,5,7,9}*/
q.pop_front();
printf(“%d\n”, q.front()); /*清除第一個元素後輸出第一個(6)*/
q.pop_back();
printf(“%d\n”, q.back()); /*清除最後一個元素後輸出最後一個(7)*/
deque<int>::iterator it;
for (it = q.begin(); it != q.end(); it++) {
cout << *it << ‘\t’;
}
cout << endl;
system(“pause”);
return 0;
}

輸出結果：

3.3 list

3.3.1 list定義

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

#include <list>

3.3.2 list定義和初始化

list<int>lst1; //創建空list

list<int> lst2(5); //創建含有5個元素的list

list<int>lst3(3,2); //創建含有3個元素的list

list<int>lst4(lst2); //使用lst2初始化lst4

list<int>lst5(lst2.begin(),lst2.end()); //同lst4

3.3.3 list常用操作函數

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能容納的最大元素數量
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的元素倒轉
Lst1.size() 返回list中的元素個數
Lst1.sort() 給list排序
Lst1.splice() 合併兩個list
Lst1.swap() 交換兩個list
Lst1.unique() 刪除list中相鄰重複的元素

3.3.4 List使用實例

3.3.4.1 迭代器遍歷list

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

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創建一個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創建一個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”);
}

輸出結果

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”);
//測試引用類函數
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”);
}

輸出結果：

3.4 map/multimap

map和multimap都需要#include<map>，唯一的不同是，map的鍵值key不可重複，而multimap可以，也正是由於這種區別，map支援[ ]運算符，multimap不支援[ ]運算符。在用法上沒什麼區別。

C++中map提供的是一種鍵值對容器，裡面的數據都是成對出現的,如下圖：每一對中的第一個值稱之為關鍵字(key)，每個關鍵字只能在map中出現一次；第二個稱之為該關鍵字的對應值。

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

3.4.1 基本操作函數

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

clear(）刪除所有元素

count() 返回指定元素出現的次數

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

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

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

erase() 刪除一個元素

find() 查找一個元素

get_allocator() 返回map的配置器

insert() 插入元素

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

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

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

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

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

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

swap() 交換兩個map

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

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

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 迭代器

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

二者的區別在於，後者一定返回 const_iterator，而前者則根據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數據

//數據的插入–第一種：用insert函數插入pair數據
#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<<iter->first<<‘ ‘<<iter->second<<endl;
}

3.4.4.2 用insert函數插入value_type數據

//第二種：用insert函數插入value_type數據，下面舉例說明
#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<<iter->first<<‘ ‘<<iter->second<<endl;
}

3.4.4.3 用insert函數進行多個插入

insert共有4個重載函數：

// 插入單個鍵值對，並返回插入位置和成功標誌，插入位置已經存在值時，插入失敗
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 用數組方式插入數據

//第三種：用數組方式插入數據，下面舉例說明
#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<<iter->first<<‘ ‘<<iter->second<<endl;
}

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

mapStudent.insert(map<int, string>::value_type (1, “student_one”));

mapStudent.insert(map<int, string>::value_type (1, “student_two”));

上面這兩條語句執行後，map中1這個關鍵字對應的值是「student_one」，第二條語句並沒有生效，那麼這就涉及到我們怎麼知道insert語句是否插入成功的問題了，可以用pair來獲得是否插入成功，程式如下

pair<map<int, string>::iterator, bool> Insert_Pair;

Insert_Pair = mapStudent.insert(map<int, string>::value_type (1, “student_one”));

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

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

//驗證插入函數的作用效果
#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”<<endl;
else
cout<<“Insert Failure”<<endl;
Insert_Pair = mapStudent.insert(pair<int, string>(1, “student_two”));
if(Insert_Pair.second == true)
cout<<“Insert Successfully”<<endl;
else
cout<<“Insert Failure”<<endl;
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
cout<<iter->first<<‘ ‘<<iter->second<<endl;
}

大家可以用如下程式，看下用數組插入在數據覆蓋上的效果

//驗證數組形式插入數據的效果
#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<<iter->first<<‘ ‘<<iter->second<<endl;
}

3.4.5 查找、刪除、交換

查找

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

刪除

// 刪除迭代器指向位置的鍵值對，並返回一個指向下一元素的迭代器
iterator erase( iterator pos )
// 刪除一定範圍內的元素，並返回一個指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );
// 根據Key來進行刪除，返回刪除的元素數量，在map里結果非0即1
size_t erase( const key_type& key );
// 清空map，清空後的size為0
void clear();

交換

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

3.4.6 容量

// 查詢map是否為空
bool empty();
// 查詢map中鍵值對的數量
size_t size();
// 查詢map所能包含的最大鍵值對數量，和系統和應用庫有關。
// 此外，這並不意味著用戶一定可以存這麼多，很可能還沒達到就已經開闢記憶體失敗了
size_t max_size();
// 查詢關鍵字為key的元素的個數，在map里結果非0即1
size_t count( const Key& key ) const; //

3.4.7 排序

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

這裡要講的是一點比較高深的用法了,排序問題，STL中默認是採用小於號來排序的，以上程式碼在排序上是不存在任何問題的，因為上面的關鍵字是int 型，它本身支援小於號運算，在一些特殊情況，比如關鍵字是一個結構體或者自定義類，涉及到排序就會出現問題，因為它沒有小於號操作，insert等函數在編譯的時候過不去，下面給出兩個方法解決這個問題。

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
{ //這個函數指定排序策略，按niD排序，如果niD相等的話，按strName排序
if (niD < _A.niD) return true;
if (niD == _A.niD)
return strName.compare(_A.strName) < 0;
return false;
}
}Studentinfo, *PStudentinfo; //學生資訊
int main()
{
int nSize; //用學生資訊映射分數
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 仿函數的應用，這個時候結構體中沒有直接的小於號重載

//第二種：仿函數的應用，這個時候結構體中沒有直接的小於號重載，程式說明
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
}Studentinfo, *PStudentinfo; //學生資訊
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()
{
//用學生資訊映射分數
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，但是它的底層實現並不是適合所有的場景，如果我們需要其他適合的map實現就不得不使用比如boost庫等三方的實現，在c++11中加了一種map unordered_map,unordered_set,他們的實現有什麼不同呢？

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

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

還有另外一點從佔用記憶體上來說因為unordered_map才用hash結構會有一定的記憶體損失，它的記憶體佔用回高於map。

最後就是她們的場景了，首先如果你需要對map中的數據排序，就首選map，他會把你的數據按照key的自然排序排序（由於它的底層實現紅黑樹機制所以會排序），如果不需要排序，就看你對記憶體和cpu的選擇了，不過一般都會選擇unordered_map，它的查找效率會更高。

至於使用方法和函數，兩者差不多，由於篇幅限制這裡不再贅述，unordered_multimap用法亦可類推。

3.5 set/multiset

std::set 是關聯容器，含有 Key 類型對象的已排序集。用比較函數compare進行排序。搜索、移除和插入擁有對數複雜度。 set 通常以紅黑樹實現。

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

由於set元素是排好序的，且默認為升序，因此當set集合中的元素為結構體或自定義類時，該結構體或自定義類必須實現運算符『<』的重載。

　　multiset特性及用法和set完全相同，唯一的差別在於它允許鍵值重複。

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

3.5.1 set常用成員函數

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

2. clear()–清除所有元素

3. count()–返回某個值元素的個數

4. empty()–如果集合為空，返回true

5. end()–返回指向最後一個元素的迭代器

6. equal_range()–返回集合中與給定值相等的上下限的兩個迭代器

7. erase()–刪除集合中的元素

8. find()–返回一個指向被查找到元素的迭代器

9. get_allocator()–返回集合的分配器

10. insert()–在集合中插入元素

11. lower_bound()–返回指向大於（或等於）某值的第一個元素的迭代器

12. key_comp()–返回一個用於元素間值比較的函數

13. max_size()–返回集合能容納的元素的最大限值

14. rbegin()–返回指向集合中最後一個元素的反向迭代器

15. rend()–返回指向集合中第一個元素的反向迭代器

16. size()–集合中元素的數目

17. swap()–交換兩個集合變數

18. upper_bound()–返回大於某個值元素的迭代器

19. value_comp()–返回一個用於比較元素間的值的函數

3.5.2 程式碼示例

以下程式碼涉及的內容：

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

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

3、set容器的insert函數的返回值為什麼類型？

#include <iostream>
#include <string>
#include <set>
using namespace std;
/* 仿函數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<<(ostream &out, const Person &person);
public:
Person(string name, int age)
{
mName = name;
mAge = age;
}
public:
string mName;
int mAge;
};
ostream &operator<<(ostream &out, const Person &person)
{
out << “name:” << person.mName << ” age:” << person.mAge << endl;
return out;
}
/* 仿函數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類型的函數模板 */
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);
//結果為:10 20 3
/* set的insert函數返回值為一個對組(pair)。
對組的第一個值first為set類型的迭代器：
1、若插入成功，迭代器指向該元素。
2、若插入失敗，迭代器指向之前已經存在的元素
對組的第二個值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容
器提供一個仿函數,本例的仿函數為CompareSet
*/
set<int, CompareSet> s;
s.insert(10);
s.insert(20);
s.insert(30);
//列印set
PrintSet(s);
//結果為:30,20,10
}
void test03()
{
/* set元素類型為Person，當set元素類型為自定義類型的時候
必須給set提供一個仿函數，用於比較自定義類型的大小，
否則無法通過編譯
*/
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函數返回值為什麼？

#include <iostream>
#include <set>
using namespace std;
/* 列印set類型的函數模板 */
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函數返回值為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中出現了兩種新的關聯容器:unordered_set和unordered_map，其內部實現與set和map大有不同，set和map內部實現是基於RB-Tree，而unordered_set和unordered_map內部實現是基於哈希表(hashtable)，由於unordered_set和unordered_map內部實現的公共介面大致相同，所以本文以unordered_set為例。

unordered_set是基於哈希表，因此要了解unordered_set，就必須了解哈希表的機制。哈希表是根據關鍵碼值而進行直接訪問的數據結構，通過相應的哈希函數(也稱散列函數)處理關鍵字得到相應的關鍵碼值，關鍵碼值對應著一個特定位置，用該位置來存取相應的資訊，這樣就能以較快的速度獲取關鍵字的資訊。比如：現有公司員工的個人資訊（包括年齡），需要查詢某個年齡的員工個數。由於人的年齡範圍大約在[0，200]，所以可以開一個200大小的數組，然後通過哈希函數 $f(key)=key$ 得到key對應的key-value，這樣就能完成統計某個年齡的員工個數。而在這個例子中，也存在這樣一個問題，兩個員工的年齡相同，但其他資訊（如：名字、身份證）不同，通過前面說的哈希函數，會發現其都位於數組的相同位置，這裡，就涉及到「衝突」。準確來說，衝突是不可避免的，而解決衝突的方法常見的有：開發地址法、再散列法、鏈地址法(也稱拉鏈法)。而unordered_set內部解決衝突採用的是—-鏈地址法，當用衝突發生時把具有同一關鍵碼的數據組成一個鏈表。下圖展示了鏈地址法的使用:

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

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

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　改變自己，從現在做起———–久館

Tags: C++STL的使用

C++STL教程

1 什麼是STL？

2 STL內容介紹

2.1 容器

2.2 STL迭代器

2.3 演算法

2.4 仿函數

2.4.1 概述

2.4.2 仿函數(functor)在程式語言中的應用

2.4.3 仿函數在STL中的定義

2.5 容器適配器

2.5.1 stack

2.5.2 queue & priority_queue

3 常用容器用法介紹

3.1 vector

3.1.1 基本函數實現

3.1.2 基本用法

3.1.3 簡單介紹

3.1.4 實例

3.2 deque

3.2.1 聲明deque容器

3.2.2 deque的常用成員函數

3.2.3 deque的一些特點

3.2.4 實例

3.3 list

3.3.1 list定義

3.3.2 list定義和初始化

3.3.3 list常用操作函數

3.3.4 List使用實例

3.4 map/multimap

3.4.1 基本操作函數

3.4.2 聲明

3.4.3 迭代器

3.4.4 插入操作

3.4.5 查找、刪除、交換

3.4.6 容量

3.4.7 排序

3.4.8 unordered_map

3.5 set/multiset

3.5.1 set常用成員函數

3.5.2 程式碼示例

3.5.3 unordered_set

分享此文：

Related Posts

第24次文章：結構性模式（續）

源碼中的設計模式–裝飾器模式

空指針的傳說

支援iPhone 12！有鎖蘋果手機全系黑解突然開放：能5G

VirMach 便宜 VPS

QNews

熱門搜尋