(2020.12.08 Tues)
STL容器允許重復(fù)利用已有的實(shí)現(xiàn)構(gòu)造自己特定類(lèi)型下的數(shù)據(jù)結(jié)構(gòu)咸产，通過(guò)設(shè)置一些模板類(lèi)，這些模板的參數(shù)允許用戶指定容器中元素的數(shù)據(jù)類(lèi)型逸月，從而提高編程效率氧卧。

(容器部分的內(nèi)容可以對(duì)比python中的list, tuple, dict, set等數(shù)據(jù)結(jié)構(gòu)。)
容器主要由頭文件<vector>, <list>, <deque>, <set>, <map>, <stack>和<queue>組成蚜锨。

(2020.12.09 Wed)
STL定義的通用容器分為順序容器(sequence container)氛悬，關(guān)聯(lián)容器(associative container)和容器適配器则剃。

順序容器

順序容器是一種各元素間有順序關(guān)系的線性表耘柱，是線性結(jié)構(gòu)的可序群集，其中的每一個(gè)元素有固定的位置棍现，除非用刪除或插入的操作改變變量的位置调煎。順序容器具有插入速度快但查找操作相對(duì)較慢的特征。C++ STL(標(biāo)準(zhǔn)模板庫(kù))提供3中順序容器：vector己肮、list和deque士袄。vector和deque類(lèi)時(shí)以數(shù)組為基礎(chǔ)，list類(lèi)是以雙向鏈表為基礎(chǔ)谎僻。

順序容器中各種類(lèi)型的比較

vector是動(dòng)態(tài)順序容器娄柳，有連續(xù)內(nèi)存地址的數(shù)據(jù)結(jié)構(gòu)。相比于數(shù)組艘绍，vector會(huì)消耗更多的內(nèi)存以有效地動(dòng)態(tài)增長(zhǎng)赤拒。而相比于其他順序容器(deques, list)，vector能更快的索引元素(如同數(shù)組一樣)诱鞠，而且能相對(duì)高效的在尾部插入和刪除元素挎挖。在其他位置刪除和插入元素，效率沒(méi)有這些容器高航夺。

list是STL實(shí)現(xiàn)的雙向鏈表蕉朵，相比vector的連續(xù)線性空間，list復(fù)雜太多敷存，它允許快速的插入和刪除墓造，但是隨機(jī)訪問(wèn)卻比較慢堪伍。它的數(shù)據(jù)有若干個(gè)節(jié)點(diǎn)構(gòu)成锚烦，每個(gè)節(jié)點(diǎn)包括一個(gè)信息塊、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針帝雇，可以向前或向后進(jìn)行訪問(wèn)涮俄，但不能隨機(jī)訪問(wèn)。好處是每次插入或刪除會(huì)配置或者釋放一個(gè)元素空間尸闸，對(duì)空間的運(yùn)用絕對(duì)精準(zhǔn)彻亲。

deque(double ended queues雙向隊(duì)列)和vector相似，但它允許在容器頭部快速插入和刪除吮廉，如同在尾部一樣苞尝。

向量vector

使用vector的時(shí)候，需包含頭文件: <vector>宦芦，一般還要加上'using namespace std;'宙址，如果不加，調(diào)用的時(shí)候必須加std::vector<..>這樣的形式调卑，加了std::表示運(yùn)用的是std命令空間的vector容器抡砂。
向量聲明和初始化

vector<int> a;
vector<float> a(10); //初始大小為10的向量
vector<float> a(10,1);//初始大小為10注益，初始值都是1的向量
vector<int> b(a); //用向量a初始化向量b
vector<int> b(a.begin(), a.begin()+3); //將a向量中第0到第2個(gè)作為向量b的初始值
//可以用數(shù)組初始化向量
int n[] = {1,2,3,4,5};
vector<int> a(n,n+5); //n的前5個(gè)元素作為a的初值
vector<in> a(&n[1], &n[4]); //n[1]到n[4]范圍內(nèi)的元素作為向量a的初值

元素的輸入和訪問(wèn)

#include <iostream>
#include <vector>
using namespace std;
int main() 
{
    vector<int> a(10,1);
    int i;
    cout << 'initialisaiton:' << endl;
    cout << 'insert data:' << endl;
    cin >> a[2];
    cin >> a[5];
    cin >> a[8];
    cout << '賦值后遍歷:'<<endl;
    for (i = 0; i < a.size(); i++)
    { 
        cout<<a[i]<<endl; //以a[n]的方式訪問(wèn)向量的第n個(gè)元素
    }
}

基本操作

以迭代器訪問(wèn)向量

vector<int> a(10,5);
vector<int>::iterator iter;
for (iter = a.begin(); it != a.end(); iter++)
{
   cout<<*iter<<endl;
}

因?yàn)榈魇且粋€(gè)定義在vector類(lèi)中的typedef厦瓢，所以必須使用容器名vector、容器元素類(lèi)型和作用域符來(lái)使用iterator啤月。

迭代器是一個(gè)指針旷痕，用來(lái)存取容器中的數(shù)據(jù)元素，因此迭代器的操作和指針的操作相同顽冶。

二維向量

vector<vector<int>> a(3,vector<int>(4)); //相當(dāng)于數(shù)組a[3][4]欺抗，都是空
vector<vector<int>> a(3, vector<int>(4,0)); //相當(dāng)于a[3][4],都是0
for（int m = 0; m < a.size(); m++) //a.size()獲取行向量大小
{
    for (int n = 0; n < a[3].size(); n++) //a[n].size()獲取向量中具體每個(gè)向量的大小
    {
        cout<<a[m][n]<<endl;
     }
}

列表list

STL實(shí)現(xiàn)的雙向鏈表，相比vector的連續(xù)線性空間强重，list復(fù)雜太多绞呈，它允許快速的插入和刪除，但是隨機(jī)訪問(wèn)卻比較慢间景。它的數(shù)據(jù)有若干個(gè)節(jié)點(diǎn)構(gòu)成佃声，每個(gè)節(jié)點(diǎn)包括一個(gè)信息塊、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針倘要，可以向前或向后進(jìn)行訪問(wèn)圾亏，但不能隨機(jī)訪問(wèn)。好處是每次插入或刪除會(huì)配置或者釋放一個(gè)元素空間封拧，對(duì)空間的運(yùn)用絕對(duì)精準(zhǔn)志鹃。列表的定義在頭文件<list>中。
其定義方式和vector相似

list<int> lst1;
list<int> lst2(3);
list<int> lst3(3,2); //三個(gè)元素的list泽西，初始值都是2
list<int> lst4(lst2); 
list<int> lst5(lst.begin(), lst.end()); //用lst初始化lst5
lst.push_front(8); //頭部加入元素
lst.pop_front(); //頭部元素刪除
lst.push_back(xx); //尾部加入元素
lst.pop_back(); //尾部元素刪除

遍歷list

iterator begin(); //返回指向第一個(gè)元素的迭代器
iterator end();
reverse_iterator rbegin(); //返回指向第一個(gè)元素的逆向迭代器
reverse_iterator rend();
// 如下
for (list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit)
{
    cout<<**rit<<endl;
}

列表容器的操作

lst.empty(); //lst為空時(shí)返回true
lst.size(); //返回list中元素的個(gè)數(shù)
lst.max_size(); //返回lst最大能容納的元素個(gè)數(shù)
//為容器添加新內(nèi)容
lst.assign(InputIterator first, InputIterator last);
lst.assign(size_type a, const value_type& val); //給lst賦值n個(gè)值為val的元素
//
list<int> lst;
list<int> lst2;
list<int> lst3;
lst.assign(5,10); //添加5元素曹铃，值為10
lst2.assign(lst.begin(), lst.end()); //用lst為lst2賦值
int a[]={1,2,3,4};
lst3.assign(a,a+4); //將a的元素都賦值給lst3

插入元素
(2020.12.10 Thur)
list中插入元素需要成員函數(shù)insert()實(shí)現(xiàn)。分為若干版本捧杉。

iterator insert(iterator position, const value& val); 
//position是要插入這個(gè)list的迭代器陕见，val是要插入的值，比如下面這個(gè)例子
list<int> lst;
list<int>::iterator it;
it = lst.begin();
lst.inset(it, 9);

iterator insert(iterator position, size_type n, const value& val);
//插入n個(gè)值為val的元素
lst.insert(it, 2, 29); //在迭代器指針it所指的位置加入2個(gè)29

template <class InputIterator>;
void insert (iterator position, InputIterator first, InputIterator last);
//first和last是選擇的把值插入到這個(gè)list中的值所在的容器的迭代器
list<int> lst;
list<int>::iterator it;
vector<int> v(2,39);
lst.insert(it, v.begin(), v.end());

刪除元素

iterator erase(iterator position);
iterator erase(iterator first, iterator last); //刪除[first, last)中的值味抖，可以不用變量接收其返回值
list<int> lst(5,10);
list<int>::iterator it1,it2;
it1 = lst.begin();
it2 = lst.end();
it1 = lst.erase(it1);
lst.erase(it1, it2);
lst.erase(lst.begin(), lst.end()); //清空l(shuí)st

雙隊(duì)列deque

deque(double ended queue)雙向隊(duì)列评甜，和vector相似，但是它允許在容器頭部快速插入和刪除仔涩，就像在尾部一樣忍坷。
deque結(jié)合了vector和list的優(yōu)缺點(diǎn)，優(yōu)化了的對(duì)序列兩端元素進(jìn)行添加和刪除操作的基本序列容器。

它允許較為快速的隨機(jī)訪問(wèn)承匣，但不像vector那樣把所有的對(duì)象保存在一個(gè)連續(xù)的內(nèi)存塊蓖乘，而是采用多個(gè)連續(xù)的存儲(chǔ)塊，并且在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些塊及其順序的跟蹤韧骗。向deque兩端添加或刪除元素的開(kāi)銷(xiāo)很小嘉抒，不需要重新分配空間，所以向末端添加元素比vector更高效袍暴。

關(guān)聯(lián)容器

關(guān)聯(lián)容器中的元素通過(guò)關(guān)鍵字來(lái)保存和訪問(wèn)些侍，主要有映射(map)和集合(set)兩類(lèi)，支持通過(guò)鍵來(lái)高效的查找和讀取元素政模。map的元素以鍵-值對(duì)(map-value)的形式組織岗宣，鍵用作元素在map類(lèi)型下進(jìn)行索引，而值則表示所存儲(chǔ)和讀取的數(shù)據(jù)淋样。set僅包含一個(gè)鍵耗式，并有效的支持關(guān)于某個(gè)鍵是否存在的查詢。set和map類(lèi)型的對(duì)象不允許為同一個(gè)鍵添加第二個(gè)元素趁猴。如果一個(gè)鍵必須有多個(gè)實(shí)例刊咳，則需使用多重映射(multimap)或多重集合(multiset)類(lèi)型，其允許多個(gè)元素?fù)碛邢嗤逆I儡司。

(2020.12.11 Fri)

映射map

map是STL的一個(gè)關(guān)聯(lián)容器娱挨，提供一對(duì)一的數(shù)據(jù)處理能力，其元素由key和value兩個(gè)分量足成的對(duì)偶(key, value)捕犬。key唯一跷坝，給定一個(gè)key就能唯一確定一個(gè)value。map的類(lèi)型通常稱(chēng)為關(guān)聯(lián)數(shù)組碉碉，和數(shù)組很相似柴钻，但下標(biāo)是關(guān)鍵字key而非整數(shù)。map類(lèi)型定義在頭文件#include <map>中誉裆。

map是有序的且不允許重復(fù)key(關(guān)鍵字)的關(guān)聯(lián)容器顿颅。有序的實(shí)現(xiàn)時(shí)依靠關(guān)鍵字類(lèi)型中的'<'來(lái)實(shí)現(xiàn)缸濒。

#include <map>
map<key_type, value_type> tmpMap; //初始化足丢，定義一個(gè)空map
map<key_type, value_type> tmpMap{
    {key1, value1},
    {key2, value2},
    ...
};   //注意結(jié)尾有個(gè)分號(hào);
map<key_type, value_type> tmpMap(existingMap); //從已有的一個(gè)map復(fù)制過(guò)來(lái)
map<key_type, value_type> tmpMap(x, y); //x, y分別是已有map對(duì)象的迭代器范圍
map1 = map2; //直接復(fù)制

map<int, string> myMap;
myMap::value_type a; //a為pair<const int, string>類(lèi)型
myMap::key_type b; //b為int類(lèi)型
myMap::mapped_type c; //c為string類(lèi)型

pair類(lèi)型

pair標(biāo)準(zhǔn)類(lèi)型被包含在頭文件#include <utility>中，一個(gè)pair保存兩個(gè)數(shù)據(jù)成員庇配，pair是一個(gè)用來(lái)生成特定類(lèi)型的模板斩跌。當(dāng)創(chuàng)建一個(gè)pair時(shí)，用戶必須提供兩個(gè)類(lèi)型名捞慌，pair的數(shù)據(jù)成員將具有對(duì)應(yīng)的類(lèi)型耀鸦。一般來(lái)說(shuō)，一個(gè)pair類(lèi)型的對(duì)象，存儲(chǔ)的是一個(gè)鍵值對(duì)(key-value)袖订。

pair<string, string> a; //保存兩個(gè)string
pair<string, size_t> b; //保存一個(gè)string和size_t
pair<int, vector<int>> c; //
pair<string, string> author{'hello', 'world'}; //初始化一個(gè)pair氮帐，名author，兩個(gè)初值是hello world
pair<string, string> author('hello', world'); //同上

pair的數(shù)據(jù)成員是public洛姑，成員名為first和second上沐，用戶可以用普通的成員訪問(wèn)符'.'來(lái)進(jìn)行訪問(wèn)。

pair對(duì)象也可以作為函數(shù)的返回净宵。

map的使用

插入數(shù)據(jù)

#include <map>
map<int, string> m;
m.insert(pair<int, string>(1,'m_first')); //插入數(shù)據(jù)
m.insert(pair<int, string>(2,'m_second'));
map<int, string>::iterator iter;
for (iter = m.begin(); iter!= m.end(); iter++)
{ 
    cour<< iter->first << ' '<< iter->second<< endl;
}

插入value_type數(shù)據(jù)，value_type類(lèi)型代表的是這個(gè)容器中元素的類(lèi)型

map<string, string> m;
m.insert(map<string, string>::value_type('001', 'm_first')); //插入第一個(gè)value_type數(shù)據(jù)
m.insert(map<string, string>::value_type('002', 'm_second')); //插入第二個(gè)value_type數(shù)據(jù)

用key鍵為map賦值

map<string, string> m;
m['both'] = 1;
int a = m['both'];

其他指令

m.size(); //map m的數(shù)據(jù)數(shù)量
 //遍歷裹纳，正向
for (map<int, string>::iterator iter = m.begin(); iter!=m.end() ; iter++)
{
    cout<<iter->first << ' ' << iter->second<< endl;
}
 //遍歷塘娶，反向
for (map<int, string>::iterator iter = m.rbegin(); iter!=m.rend() ; iter++)
{
    cout<<iter->first << ' ' << iter->second<< endl;
}
//計(jì)數(shù)和查找
m.count(k); //m中key k的個(gè)數(shù)，0或者1
m.find(k); //找到m中的k索引的元素痊夭，并返回指向該元素的迭代器
//刪除
m.erase(k); //刪除key為k的元素刁岸，返回size_type的類(lèi)型，表示刪除的元素個(gè)數(shù)
m.erase(b, e); //刪除迭代器b和e中間的元素她我，返回void型
m.erase(p); //刪除迭代器p指向的元素虹曙，返回void型

set類(lèi)容器

set只是單純的key的集合。當(dāng)只想知道一個(gè)key是否存在時(shí)番舆，使用set容器最合適酝碳。set容器支持大多數(shù)map的操作，但不支持下標(biāo)操作恨狈，沒(méi)有定義mapped_type類(lèi)型疏哗。在set類(lèi)型中，value_type不是pair類(lèi)型禾怠，而是與key_type類(lèi)型相同返奉。set容器中存儲(chǔ)的key也是唯一的。

#include <set>
vector<int> ivec;
for (...)
{ ivec.push_back(...);}
set<int> iset(ivec.begin(), ivec.end());
cout<<iset.size()<<endl; //返回set的尺寸
iset.insert('the'); // 添加元素
iset.find('a');
iset.count('a');

容器適配器

用基本容器實(shí)現(xiàn)新的容器吗氏，用于描述更高級(jí)的數(shù)據(jù)結(jié)構(gòu)芽偏。

容器適配器有三種stack, queue和priority_queue。默認(rèn)情況下stack衍生自deque弦讽。queue也同樣來(lái)自deque污尉。

#include <stack>
#include <queue> //調(diào)用queue和priority_queue時(shí)需要引入

stack的成員函數(shù)中，s.pop()是刪除棧頂元素，s.push()是在棧頂插入元素被碗，s.top()獲得指向棧頂元素的引用某宪。

queue的成員函數(shù)中，q.push()向隊(duì)尾插入一個(gè)元素锐朴，q.pop()從隊(duì)首刪除元素缩抡，q.front()返回指向隊(duì)首元素的引用，q.back()指向隊(duì)尾元素的引用包颁。

priority_queue與queue的不同之處在于瞻想，包含最大值的元素位于隊(duì)首，且只能在隊(duì)首執(zhí)行操作娩嚼。

#include <queue>
priority_queue<int> q;
q.push(1); //插入一個(gè)元素
q.pop(); //刪除隊(duì)首的元素蘑险，即最大的元素
q.size();
q.empty();
q.top(); //隊(duì)列中最大元素的引用

容器的選擇

1. vector的特點(diǎn)
   • 指定一塊如同數(shù)組一樣的連續(xù)存儲(chǔ)，但空間可以動(dòng)態(tài)擴(kuò)展岳悟。它可以像數(shù)組一樣操作佃迄，并可以動(dòng)態(tài)操作。通常體現(xiàn)在push_back()和pop_back()
   • 隨機(jī)訪問(wèn)方便贵少，像數(shù)組一樣被訪問(wèn)
   • 節(jié)省空間呵俏，因連續(xù)存儲(chǔ)，在存儲(chǔ)數(shù)據(jù)的區(qū)域都是沒(méi)有被浪費(fèi)的滔灶，但是要明確一點(diǎn)普碎，vector大多情況下并不是滿存的，在未存儲(chǔ)的區(qū)域?qū)嶋H是浪費(fèi)
   • 在內(nèi)部進(jìn)行插入录平、刪除操作效率非常低麻车，基本上是被禁止的。vector被設(shè)計(jì)成只能在后端進(jìn)行追加和刪除操作斗这，原因是vector內(nèi)部的實(shí)現(xiàn)是按照順序表的原理
   • 只能在vector的最后進(jìn)行push和pop动猬，不能在頭進(jìn)行這個(gè)操作
   • 動(dòng)態(tài)添加的數(shù)據(jù)超過(guò)vector默認(rèn)分配的大小時(shí)，需要對(duì)內(nèi)存重新分配表箭、拷貝和釋放赁咙，這個(gè)操作消耗性能。達(dá)到最佳性能免钻，最好創(chuàng)建vector時(shí)指定空間大小
2. list的特點(diǎn)
   • 不使用連續(xù)的內(nèi)存空間彼水，可以隨意進(jìn)行動(dòng)態(tài)操作
   • 可以再內(nèi)部任何位置快速的插入和刪除，可在兩端進(jìn)行push和pop
   • 不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)
   • 比vector占用更多內(nèi)存
3. deque的特點(diǎn)
   • 隨機(jī)訪問(wèn)方便伯襟，支持[ ]操作符猿涨，性能沒(méi)有vector好
   • 可在內(nèi)部進(jìn)行插入和刪除操作，性能不及l(fā)ist
   • 可以在兩端進(jìn)行push和pop
4. vector/list/deque三者比較
   vector查詢性能最好姆怪，在末端增加數(shù)據(jù)的性能也好，除非它重新申請(qǐng)內(nèi)存段；適合高效的隨機(jī)存儲(chǔ)稽揭。
   list的插入和刪除元素的性能最好俺附，查詢性能差；適合大量的插入和刪除操作且不關(guān)心隨機(jī)存儲(chǔ)的需求溪掀。
   deque介于兩者之間事镣，比list更好查詢，比vector更好插入和刪除揪胃。如果用戶需要隨機(jī)存儲(chǔ)又關(guān)心兩端數(shù)據(jù)的插入和刪除璃哟，deque最佳。

Reference

1. 聚慕課教育研發(fā)中心 編著喊递，C++從入門(mén)到項(xiàng)目實(shí)踐(超值版)随闪，清華大學(xué)出版社
2. 劉蕾編著，21天學(xué)通C++(第五版)骚勘，電子工業(yè)出版社