STL

1 STL的誕生
? 長久以來，軟件界一直希望建立一種可重復利用的東西；
? C++的面向對象和泛型編程思想，目的是復用性的提升；
? 大多情況下，數(shù)據(jù)結構和算法都未能有一套標準，導致被迫從事大量重復工作；
? 為了建立數(shù)據(jù)結構和算法的一套標準，誕生了STL。
C++面向對象的三大特性：封裝、繼承、多態(tài)。
2 STL基本概念
? STL（standard template library，標準模板庫）
? STL從廣義上分為：容器（container）、算法（algorithm）、迭代器（iterator）
? 容器和算法之間通過迭代器進行無縫連接
? STL幾乎所有的代碼都采用了模板類或模板類函數(shù)。
3 STL六大組件：容器、算法、迭代器、仿函數(shù)、適配器（配接器），空間配置器。
? 容器；各種數(shù)據(jù)結構，如vector、list、deque、set、map等，用來存放數(shù)據(jù)。
? 算法：各種常用的算法，如sort、find、copy、for_each等
? 迭代器：扮演了容器與算法之間的膠合劑
? 仿函數(shù)：行為類似函數(shù)，可作為算法的某種策略
? 適配器：一種用來修飾容器或仿函數(shù)或迭代器接口的東西
? 空間適配器：負責空間的配置與管理。
4 容器分為序列式容器和關聯(lián)式容器兩種。
序列式容器：強調值的排序，序列式容器中的每個元素均有固定的位置。
關聯(lián)式容器：二叉樹結構，各元素之間沒有嚴格的物理上的順序關系
5 算法分為質變算法和非質變算法。
質變算法：是指運算過程中會更改區(qū)間內的元素的內容，例如拷貝，替換，刪除等等
非質變算法：是指運算過程中不會更改區(qū)間內的元素的內容，例如查找、計數(shù)、遍歷、尋找極值等等。
6 迭代器：提供一種方法，使之能夠依序尋訪某個容器所含的各個元素，而又無需暴露該
容器的內部表示方式，每個容器都有自己專屬迭代器； 迭代器使用非常類似于指針，初學階段我們可以先理解迭代器為指針。

迭代器

常用的容器迭代器種類為雙向迭代器和隨機訪問迭代器。

Vector 容器

算法：for_each 迭代器：vector<int>::iterator
1 使用vector容器時，需要包含頭文件include<vector>
2 創(chuàng)建一個容器vector<int>v;
3 使用尾插法插入數(shù)據(jù)，v.push_back（數(shù)據(jù)）；
4 通過迭代器訪問容器中的數(shù)據(jù)
Vector<int>::iterator itBegin = v.begin(); // v.begin() 起始迭代器 指向容器中第一個元素
Vector<int>::iterator itEnd = v.end(); // 結束迭代器 指向容器的最后一個元素的下一個位置。
遍歷方式一

遍歷方式二

5 vector容器存放自定義數(shù)據(jù)類型(Person)

6 容器嵌套容器（類似二維數(shù)組）

1 創(chuàng)建容器
? vector<T> v; //采用模板實現(xiàn)類實現(xiàn)，默認構造函數(shù)
? vector(v.begin(), v.end()); //將v[begin(), end())區(qū)間中的元素拷貝給本身。
? vector(n, elem); //構造函數(shù)將n個elem拷貝給本身。
? vector(const vector &vec); //拷貝構造函數(shù)
2 賦值操作
? vector &operator=(const vector &vec); //重載等號操作符
? assign(beg, end); //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
? assign(n, elem); //將n個elem拷貝賦值給本身。
3 容量和大小
? empty(); //判斷容器是否為空
? capacity(); //容器的容量
? size(); //返回容器中元素的個數(shù)
? resize(int num); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
? resize(int num, elem); //重新指定容器的長度為num，若容器變長，則以elem填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
4 插入和刪除
? push_back(ele); //尾部插入元素ele
? pop_back(); //刪除最后一個元素
? insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
? insert(const_iterator pos, int count, ele); //迭代器指向位置pos插入count個元素ele
? erase(const_iterator pos); // 刪除迭代器指向的元素
? erase(const_iterator start , const_iterator end); //刪除迭代器從start到end之間的元素
? clear(); // 刪除容器中所有元素
5 數(shù)據(jù)存取
? at(int idx); //返回索引idx所指的數(shù)據(jù)
? operator[]; //返回索引idx所指的數(shù)據(jù)
? front(); //返回容器中的第一個數(shù)據(jù)元素
? back(); // 返回容器中最后一個數(shù)據(jù)元素
6 互換容器
? swap(vec); //將vec與本身的元素互換
7 預留空間
? reserve(int len); //容器預留len個元素長度，預留位置不初始化，元素不可訪問

String容器

1 構造方式
? String（）； // 創(chuàng)建一個空的字符串，例如：string str；
String（const char s）； //使用字符串s初始化
? String（const string &str）； // 使用一個string對象初始化另一個string對象
? String（int n, char c）; //使用n個符c初始化。
2 賦值操作方式
? String & operator=(const char * s); // char類型字符串賦值給當前的字符串
? String & operator=(const string &s); //把字符串s賦給當前的字符串
? String & operator=(char c); // 字符賦值給當前的字符串
? String & assign(const char * s); //把字符串s賦給當前的字符串
? String & assign(const char *s, int n); //把字符串s的前n個字符賦給當前的
字符串
? String & assign(const string &s); // 把字符串s賦給當前字符串
? String & assign(int n, char c); // 用n個字符c賦給當前字符串
3 字符串拼接
? String & operator+=(const char * str); //重載+=操作符
? String & operator+=(const char c); //重載+=操作符
? String & operator+=(const string& str); //重載+=操作符
? String & append(const char *s); //把字符串s連接到當前字符串的尾部
? String & append(const char *s, int n); //把字符串s的前n個字符連接到當前字符
串的尾部
? String & append(const string &s); //同operator+=(const string & str)
? String & append(const string &s, int pos, int n); //把字符串s中從pos開始的n個
字符連接到字符的結尾
4 查找和替換
查找：查找指定字符串是否存在
? int find(const string &str, int pos=0)const; // 查找str第一次出現(xiàn)的位置，從pos=0開始查找。
? int find(const char *s, int pos=0)const; //查找s第一次出現(xiàn)位置，從pos開始查找。
? int find(const char *s, int pos, int n)const; //從pos位置查找s的前n個字符第一次位置。
? int find(const char c, int pos=0)const; //查找字符c第一次出現(xiàn)位置
? int rfind(const string &str, int pos=npos)const; //查找str最后一次位置，從pos開始查找。
? int rfind(const *s, int pos=npos)const; //查找s最后一次出現(xiàn)位置，從pos開始查找。
? int rfind(const char *s, int pos, int n)const; //從pos查找s的前n個字符的最后一次位置。
? int rfind(const char c, int pos=0)const; //查找字符c最后一次出現(xiàn)位置。
替換：在指定的位置替換字符串
? string& replace(int pos, int n, const string &str); //替換從pos開始n個字符為字符串str。
? string &replace(int pos, int n, const char *s); // 替換從pos開始的n個字符為字符串s
總結：
1 find查找是從左往右，rfind是從右往左；
2 find找到字符串后返回查找的第一個字符位置，找不到返回-1；
3 replace在替換時，要指定從哪個位置起，多少個字符，替換成什么樣的字符串。
5 字符串比較
1 比較方式：按字符的ASCII碼進行對比（=返回 0，>返回1，<返回-1）
? int compare(const string &s)const; //與字符串s比較
? int compare(const char *s)const; //與字符串s比較
6 字符串存取方式
? char &operator[](int n); //通過[]方式取字符
? char &at(int n); //通過at方法獲取字符
7 插入和刪除
? string &insert(int pos, const char *s); //插入字符串
? string &insert(int pos, const string &str); //插入字符串
? string &insert(int pos, int n, char c); //在指定位置插入n個字符c
? string &erase(int pos, int n=npos); //刪除從pos開始的n個字符
8 子串（從字符串中獲取想要的子串）
? string substr(int pos=0, int n=npos)const; //返回由pos開始的n個字符組成的字符串。

deque容器

功能：雙端數(shù)組，可以對頭端進行插入刪除操作
deque與vector區(qū)別
? vector對于頭部的插入刪除效率低，數(shù)據(jù)量大，效率越低；
? deque相對而言，對頭部的插入刪除速度會比vector快；
? vector訪問元素時的速度會比deque快，這和兩者內部實現(xiàn)有關。

deque內部工作原理：
? deque內部有個中控器，維護每段緩沖區(qū)中的內容，緩沖區(qū)中存放真實數(shù)據(jù)
? 中控器維護的是每個緩沖區(qū)的地址，使得使用deque時像一片連續(xù)的內存空間

deque容器的迭代器也是支持隨機訪問的
1 構造函數(shù)
? deque<T> deqT; //默認構造形式
? deque(beg, end); //構造函數(shù)將[beg, end）區(qū)間中的元素拷貝給本身
? deque(n, elem); //構造函數(shù)將n個elem拷貝給本身
? deque(const deque &deq); //拷貝構造函數(shù)
注意deque容器的迭代器要加const，在遍歷的時候。
2 賦值操作
? deque &operator =(const deque &deq); //重載等號操作符
? assign(beg, end); //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
? assign(n, elem); //將n個elem拷貝賦值給本身
3 大小操作
? deque.empty(); //判斷容器是否為空
? deque.size(); //返回容器中元素的個數(shù)
? deque.resize(num); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
? duque.resize(num, elem); //重新指定容器的長度為num，若容器變長，則以elem值填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
4 插入和刪除
? push_back(elem); //尾插
? push_front(elem); //頭插
? pop_back(); //刪除最后一個元素
? pop_front(); //刪除第一個元素

? insert(pos, elem); //在pos位置插入一個elem元素的拷貝，返回新數(shù)據(jù)的位置
? insert(pos, n, elem); //在pos位置插入n個elem數(shù)據(jù)，無返回值
? insert(pos, beg, end); //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值
? clear(); //清空容器中所有數(shù)據(jù)
? erase(beg, end); //刪除[beg, end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置
? erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置
5 數(shù)據(jù)存取
? at(int idx); //返回索引idx所指的數(shù)據(jù)
? operator[]; //同上
? front(); // 返回容器中第一個數(shù)據(jù)元素
? back(); // 返回容器中最后一個數(shù)據(jù)元素
6 排序
? sort(iterator beg, iterator end) //對beg和end區(qū)間內元素進行排序，加頭文件algorithm

stack容器

stack是一種先進后出(FILO)的數(shù)據(jù)結構，它只有一個出口

棧中只有頂端的元素可以被外界使用，因此不允許有遍歷行為
棧中進入數(shù)據(jù)稱為——入棧push
棧中彈出數(shù)據(jù)稱為——出棧pop
1 構造函數(shù)
? stack<T> stk; //stack采用模板類實現(xiàn)，stack對象的默認構造形式
? stack(const stack &stk); //拷貝構造函數(shù)
2 賦值操作
? stack& operator=(const stack &stk); //重載等號操作符
3 數(shù)據(jù)存取
? push(elem); //向棧頂添加元素
? pop(); //從棧頂移除第一個元素
? top(); //返回棧頂元素
4 大小操作
? empty(); // 判斷堆棧是否為空
? size(); //返回棧的大小

queue 容器

queue是一種先進先出（FIFO）的數(shù)據(jù)結構，它有兩個出口

隊列容器允許從一端新增元素，從另一端移除元素
隊列中只有隊頭和隊尾才可以被外界使用，因此隊列不允許有遍歷行為
隊列中進數(shù)據(jù)稱為——入隊 push
隊列中出數(shù)據(jù)稱為——出隊 pop
1 構造函數(shù)
? queue<T> que; //queue采用模板類實現(xiàn)，queue對象的默認構造形式
? queue(const queue &que); // 拷貝構造函數(shù)
2 賦值操作
? queue& operator= (const queue & que); //重載等號操作符
3 數(shù)據(jù)存取
? push(elem); //往隊尾添加元素
? pop(); //從隊頭移除第一個元素
? back(); //返回最后一個元素
? front(); //返回第一個元素
4 大小操作
? empty(); //判斷堆棧是否為空
? size(); // 返回棧的大小
list容器
功能：將數(shù)據(jù)進行鏈式存儲
鏈表（list）是一種物理存儲單元上非連續(xù)的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實現(xiàn)的。
鏈表的組成：由一系列結點組成。
結點的組成：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結點地址的指針域。
STL中的鏈表是一個雙向循壞鏈表：

由于鏈表的存儲方式并不是連續(xù)的內存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器。
List的優(yōu)點：
? 采用動態(tài)存儲分配，不會造成內存浪費和溢出
? 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素。
List的缺點：
? 鏈表靈活，但是空間(指針域)和時間(遍歷)額外耗費較大
注：list有一個重要的性質，插入操作和刪除操作都不會造成原有l(wèi)ist迭代器的失效，這在vector是不成立的。
總結：STL中l(wèi)ist和vector是兩個最常用的容器，各有優(yōu)缺點。
1 構造函數(shù)
? list<T> lst; //list采用模板類實現(xiàn)，對象的默認構造形式
? list(beg, end); //構造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身
? list(n, elem); //構造函數(shù)將n個elem拷貝給本身
? list(const list &lst); //拷貝構造函數(shù)
2 賦值和交換
? assign(beg, end); //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
? assign(n, elem); //將n個elem拷貝賦值給本身
? list& operator=(const list &lst); //重載等號操作符
? swap(lst); // 將lst與本身的元素互換。
3 大小操作
? size(); //返回容器中元素的個數(shù)
? empty(); //判斷容器是否為空
? resize(num); //重新指定容器的長度為num，若容器變長，則以默認值填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
? resize(num, elem); //重新指定容器的長度為num，若容器變長，則以elem值填充新位置，若容器變短，則末尾超出容器長度的元素被刪除。
4 插入和刪除
? push_back(elem); //在容器尾部加入一個元素
? pop_back(); //刪除容器中最后一個元素
? push_front(elem); //在容器開頭插入一個元素
? pop_front(); //從容器開頭移除第一個元素
? insert(pos, elem); //在pos位置插elem元素的拷貝，返回新數(shù)據(jù)的位置
? insert(pos, n, elem); //在pos位置插入n個elem數(shù)據(jù)，無返回值。
? insert(pos, beg, end); //在pos位置插入[beg, end)區(qū)間的數(shù)據(jù)，無返回值
? clear(); //移除容器的所有數(shù)據(jù)
? erase(beg, end); //刪除[beg, end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置
? erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置
? remove(elem); //刪除容器中所有與elem值匹配的元素。
5 數(shù)據(jù)存取
? front(); //返回第一個元素
? back(); //返回最后一個元素
6 反轉和排序
? reverse(); // 反轉鏈表
? sort(); // 鏈表排序

set/multiset容器

簡介：所有元素都會在插入時自動被排序
本質：set/multiset屬于關聯(lián)式容器，底層結構用二叉樹實現(xiàn)。
set和multiset區(qū)別：
? set不允許容器中有重復的元素
? multiset允許容器中有重復的元素
1 構造和賦值
? set<T> st; //默認構造函數(shù)
? set(const set &st); //拷貝構造函數(shù)

? set &operator=(const set &st); //重載等號操作符
2 大小和交換
? size(); //返回容器中元素的數(shù)目
? empty(); //判斷容器是否為空
? swap(st); //交換兩個集合容器
3 插入和刪除
? insert(elem); //在容器中插入元素
? clear(); //清除所有元素
? erase(pos); //刪除pos迭代器所指的元素，返回下一個元素的迭代器
? erase(beg, end); //刪除區(qū)間[beg, end)的所有元素，返回下一個元素的迭代器
? erase(beg, end); //刪除區(qū)間[beg, end)的所有元素，返回下一個元素的迭代器
? erase(elem); //刪除容器中值為elem的元素
4 查找和統(tǒng)計
? find(key); //查找key是否存在，若存在，返回該鍵的元素的迭代器；若不存在，返回set.end();
? count(key); //統(tǒng)計key的元素個數(shù)

pair對組創(chuàng)建(兩種方式)

? pair<type, type> p (value1, value2);
? pari<type, type> p = make_pair(value1, value2);
set與unordered_set的區(qū)別
a c++ std中set與unordered_set區(qū)別和map與unordered_map區(qū)別類似：
? set基于紅黑樹實現(xiàn)，紅黑樹具有自動排序的功能，因此map內部所有的數(shù)據(jù)，在任何時候，都是有序的。
? unordered_set基于哈希表，數(shù)據(jù)插入和查找的時間復雜度很低，幾乎是常數(shù)時間，而代價是消耗比較多的內存，無自動排序功能。底層實現(xiàn)上，使用一個下標范圍比較大的數(shù)組來存儲元素，形成很多的桶，利用hash函數(shù)對key進行映射到不同區(qū)域進行保存。
b set使用時設置：
? 我們需要有序數(shù)據(jù)（不同的元素）
? 我們必須打印/訪問數(shù)據(jù)（按排序順序）
? 我們需要元素的前身/后繼者
c 在以下情況下使用unordered_set:
? 我們需要保留一組不同的元素，不需要排序。
? 我們需要單個元素訪問，即沒有遍歷。

map/multimap容器

簡介：map中所有元素都是pair；
pair中第一個元素為key(鍵值)，起到索引作用，第二個元素為values(實值)
所有元素都會根據(jù)元素的鍵值自動排序
本質：map/multimap屬于關聯(lián)式容器，底層結構是用二叉樹實現(xiàn)
優(yōu)點：可以根據(jù)key值快速找到value值
Map和multimap區(qū)別： map不允許容器中有重復的key值元素
Multimap允許容器中有重復key值元素。
1 構造和賦值
? map<T1, T2> mp; //map默認構造函數(shù)
? map(const map &mp); //拷貝構造函數(shù)

? map & operator=(const map & mp); //重載等號操作符
2 大小和交換
? size(); //返回容器中所有元素的數(shù)目
? empty(); //判斷容器是否為空
? swap(st); //交換兩個集合容器
3 插入和刪除
? insert(elem); //在容器中插入元素
? clear(); //清除所有元素
? erase(pos); //刪除pos迭代器所指的元素，返回下一個元素的迭代器
? erase(beg, end); //刪除區(qū)間[beg, end)的所有元素，返回下一個元素的迭代器
? erase(key); //刪除容器中值為key的元素
4 查找和統(tǒng)計
? find(key); //查找key是否存在，若存在，返回該鍵的元素的迭代器；若不存在，返回set.end();
? count(key); // 統(tǒng)計key的元素的個數(shù)