本文將對(duì)C++語(yǔ)言中的標(biāo)準(zhǔn)模板庫(kù)STL容器進(jìn)行簡(jiǎn)單介紹，重點(diǎn)在于如何使用。

容器類

STL中的容器包括以下類別：

• vector: 動(dòng)態(tài)數(shù)組，底層基于數(shù)組來(lái)實(shí)現(xiàn)，在容量不足的時(shí)候能夠自動(dòng)進(jìn)行擴(kuò)容。
• list: 鏈表
• stack: 先進(jìn)后出的棧
• set: 基于紅黑樹實(shí)現(xiàn)的集合，插入或者查找的時(shí)間復(fù)雜度在$O(nlogn)$
• unordered_set:基于哈希表實(shí)現(xiàn)的集合，插入或者查找的時(shí)間復(fù)雜度基本上在$O(1)$
• map: 基于紅黑樹實(shí)現(xiàn)，插入或者查找的時(shí)間復(fù)雜度在$O(nlogn)$，性能相對(duì)穩(wěn)定，且因?yàn)橛行蛐钥梢灾С址秶檎?/li>
• unordered_map: 基于哈希表實(shí)現(xiàn)，插入或者查找的時(shí)間復(fù)雜度基本上在$O(1)$，性能相對(duì)不穩(wěn)定
• queue：新進(jìn)先出的單向隊(duì)列
• deque: 雙端隊(duì)列
• priority_queue: 底層基于大頂堆或者小頂堆來(lái)實(shí)現(xiàn)，優(yōu)先級(jí)隊(duì)列，能夠以$O(logn)$的時(shí)間復(fù)雜度取出隊(duì)列中所有的元素的最小值
• string: 字符串

下面以代碼的方式給出各種容器的使用方法，包括如何使用迭代器進(jìn)行遍歷，如何使用算法進(jìn)行排序，如下：

/*多年刷題經(jīng)驗(yàn)總結(jié)的stl常用的接口
*/
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<queue>  // 包括priority_queue
#include<deque>
#include<string>
#include<algorithm>
//  g++  -Wno-all  -o demo   stl.cpp
class Demo {
public:int A;Demo(){}Demo(int A) {this -> A = A;}
};struct Demo1
{bool operator()(const int &lhs, const int &rhs) const{ // 后面const修飾表示該函數(shù)為常成員函數(shù)，不會(huì)修改成員變量return lhs > rhs;}
};bool compare(const int &l1, const int &l2)
{return l1 > l2;
}void use_vector() {std::vector<int> v1;   // 空的vectorstd::vector<int> v2(3);  // 含有三個(gè)默認(rèn)值的vectorstd::vector<int> v3(3, -1); // 三個(gè)值為-1的vectorstd::vector<std::vector<int>> v4 = {{1, 2}, {3, 4}};  // 二維數(shù)組// 獲取元素?cái)?shù)量, 所有容器通用, 調(diào)用的還有empty, 以及可以迭代操作的容器會(huì)有begin和end兩個(gè)獲取迭代器的通用函數(shù)int size = v3.size();  std::cout << "v3.size() = " << size << std::endl;v3[1] = 2;std::cout << "v3[1] = " << v3[1] << std:: endl;  // 通過(guò)[]直接讀寫對(duì)應(yīng)位置的元素v3.push_back(1);  // 在某位添加元素v3.pop_back();   // 刪除末尾的元素for (auto item: v3) {std::cout << item << std::endl;}// 排序, 倒排序std::sort(v3.begin(), v3.end(), compare);for (auto item: v3) {std::cout << item << std::endl;}
}void use_list() {std::list<int> l1;// 提供的api可以完美實(shí)現(xiàn)隊(duì)列和雙端隊(duì)列l1.push_back(0);   // 尾部插入l1.push_back(1);l1.push_front(2);  // 頭部插入l1.push_front(3);// 分別訪問(wèn)頭部和尾部的元素std::cout << l1.front() << " " << l1.back() << std::endl;l1.pop_back();   // 尾部刪除l1.pop_front();  // 頭部刪除，無(wú)返回值std::cout << l1.front() << " " << l1.back() << std::endl;
}void use_stack() {std::stack<int> s1;s1.push(-1);s1.push(-2);std::cout << s1.top() << std::endl;s1.pop();  // 無(wú)返回值std::cout << s1.top() << std::endl;
}void use_set()
{std::set<int> s1{1, 2};std::unordered_set<int> s2{3, 4};// set 和unordered_set 的查找和插入,刪除操作是一樣的if (s1.find(1) != s1.end()){ // 通過(guò)這種方式判斷元素是否存在std::cout << "1 int s1" << std::endl;}s1.erase(1);if (s1.find(1) != s1.end()){std::cout << "1 int s1" << std::endl;}if (s2.find(1) != s2.end()){std::cout << "1 not int s2" << std::endl;}s2.insert(1);if (s2.find(1) != s2.end()){std::cout << "1 not int s2" << std::endl;}// 此外，基于有序，set還能提供以下兩個(gè)函數(shù)auto it1 = s1.lower_bound(2); // 小于等于的元素對(duì)應(yīng)的迭代器auto it2 = s1.upper_bound(1); // 大于元素對(duì)應(yīng)的迭代器std::cout << *it1 << " " << *it2 << std::endl;
}void use_map()
{std::map<int, int> m1;std::unordered_map<int, int> m2;// 以下為兩種類型的map都有的操作,直接通過(guò)[]讀寫元素m1[1] = -1;m2[0] = 1;m1.erase(1);auto it = m2.find(0);std::cout << it->second << std::endl;// 如何遍歷for (auto it = m2.begin(); it != m2.end(); it++){std::cout << it->first << " " << it->second << std::endl;}
}void use_queue() {// 單向隊(duì)列std::queue<int> q1;q1.push(-1);q1.push(-2);std::cout << q1.front() << std::endl;std::cout << q1.back() << std::endl;q1.pop();  // 無(wú)返回值std::deque<int> q2;q2.push_back(0);   // 尾部插入q2.push_back(1);q2.push_front(2);  // 頭部插入q2.push_front(3);// 分別訪問(wèn)頭部和尾部的元素std::cout << q2.front() << " " << q2.back() << std::endl;q2.pop_back();   // 尾部刪除q2.pop_front();  // 頭部刪除，無(wú)返回值std::cout << q2.front() << " " << q2.back() << std::endl;// 重點(diǎn)關(guān)注優(yōu)先級(jí)隊(duì)列的創(chuàng)建，分別傳入類型，底層容器（可選，默認(rèn)vector），排序方式（可選，默認(rèn)大頂堆)std::priority_queue<int, std::vector<int>, Demo1> q3;q3.push(37);q3.push(14);q3.push(559);q3.push(14);std::cout << q3.top() << std::endl;  // 打印最小數(shù)q3.pop();q3.pop();std::cout << q3.top() << std::endl; // 37// 介紹emplacestd::queue<Demo> q4;// emplace 原地構(gòu)造對(duì)象，相比于push操作，push會(huì)先構(gòu)造一個(gè)對(duì)象，然后調(diào)用拷貝構(gòu)造函數(shù)或者移動(dòng)構(gòu)造函數(shù)在容器的對(duì)應(yīng)位置構(gòu)造一個(gè)，而emplace直接在容器的對(duì)應(yīng)位置構(gòu)造，效率更高q4.emplace(-1);
}void use_string() {char *str = "abcd";// 構(gòu)造方法std::string s1 = std::string(4, 'c');  // "cccc"std::string s2 = std::string(str);  // 兩種構(gòu)造方法// 通過(guò)[]直接讀寫某個(gè)位置的字符s1[0] = 'b';std::cout << s1[0] << std::endl;std::string s3 = s1.append(s2);  // 拼接字符串std::cout << s3 << std::endl;int pos1 = s2.find("b", 1);  // 從字符串的1號(hào)位置往右查找第一個(gè)子串int pos2 = s1.rfind("c", 2); // 從字符串的2號(hào)位置往左查找第一個(gè)子串int ret = s1.compare(s2);  // 比較大小，大于返回1， 小于返回-1， 相等返回0std::string s4 = s1.substr(1, 2); // 截取從1號(hào)位置開始的后面兩個(gè)字符作為子字符串std::cout << pos1 << " " << pos2 << " " << ret << " " << s4 << std::endl;
}int main() {std::cout << "test use vector" << std::endl;use_vector();std::cout << "test use list" << std::endl;use_list();std::cout << "test use stack" << std::endl;use_stack();std::cout << "test use set" << std::endl;use_set();std::cout << "test use map" << std::endl;use_map();std::cout << "test use queue" << std::endl;use_queue();std::cout << "test use string" << std::endl;use_string();return 0;
}