容器
容器，就是用來存放東西的盒子。
常用的數(shù)據(jù)結(jié)構(gòu)包括：數(shù)組array, 鏈表list， 樹tree， 棧stack， 隊(duì)列queue， 散列表hash table, 集合set、映射表map 等等。容器便是容納這些數(shù)據(jù)結(jié)構(gòu)的。這些數(shù)據(jù)結(jié)構(gòu)分為序列式與關(guān)聯(lián)式兩種，容器也分為序列式容器和關(guān)聯(lián)式容器。
STL 標(biāo)準(zhǔn)模板庫，核心包括容器、算法、迭代器。
序列式容器/順序容器
元素排列次序與元素?zé)o關(guān)，由元素添加到容器的順序決定
容器說明
vector:支持快速隨機(jī)訪問
list:支持快速插入、刪除
deque:雙端隊(duì)列允許兩端都可以進(jìn)行入隊(duì)和出隊(duì)操作的隊(duì)列
stack:后進(jìn)先出LIFO(Last In First Out)堆棧
queue:先進(jìn)先出FIFO(First Input First Output)隊(duì)列
priority_queueL:有優(yōu)先級管理的queue
向量(vector)
連續(xù)存儲的元素
列表 (list)
由節(jié)點(diǎn)組成的雙向鏈表，每個結(jié)點(diǎn)包含著一個元素
雙端隊(duì)列(deque)
連續(xù)存儲的指向不同元素的指針?biāo)M成的數(shù)組
以上三種容器操作基本一樣
基本操作:
#include <vector>
using namespace std;
vector<int> vec_1;
//1個元素
vector<int> vec_2(1);
//6個值為 1 的元素
vector<int> vec_3(6,1);
//使用容器初始化
vector<int> vec_4(vec_3);
//通過下標(biāo)操作元素
int i = vec_3[1];
int j = vec_3.at(1);
//首尾元素
vec_3.front()
vec_3.back()
//插入元素
//vector不支持 push_front list,deque可以
vec_1.push_back(1);
//刪除元素 vector不支持 pop_front
vec_1.pop_back();
//釋放
//可以單個清除，也可以清除一段區(qū)間里的元素
vec_3.erase(vec_3.begin(),vec_3.end())
//清理容器 即erase所有
vec_3.clear();
//容量大小
vec_3.capacity();
//在容器中，其內(nèi)存占用的空間是只增不減的，
//clear釋放元素，卻不能減小vector占用的內(nèi)存
//所以可以對vector 收縮到合適的大小
vector< int >().swap(vec_3);
//在vec是全局變量時候
//建立臨時vector temp對象，swap調(diào)用之后對象vec占用的空間就等于默認(rèn)構(gòu)造的對象的大小
//temp就具有vec的大小，而temp隨即就會被析構(gòu)，從而其占用的空間也被釋放。
迭代器
//獲得指向首元素的迭代器 模板類，不是指針，當(dāng)做指針來使用
vector<int>::iterator it = vec.begin();
//遍歷元素
for (; it < vec.end(); it++)
{
cout << *it << endl;
}
//begin和end 分別獲得 指向容器第一個元素和最后一個元素下一個位置的迭代器
//rbegin和rend 分別獲得 指向容器最后一個元素和第一個元素前一個位置的迭代器
//注意循環(huán)中操作元素對迭代器的影響
vector<int>::iterator it = vec.begin();
for (; it < vec.end(); )
{
//刪除值為2的元素
if (*it == 2) {
vec.erase(it);
}
else {
it++;
}
}
棧(stack)
后進(jìn)先出的值的排列
stack<int> s;
//入棧
s.push(1);
s.push(2);
//彈棧
s.pop();
//棧頂
cout << s.top() << endl;
隊(duì)列(queue)
先進(jìn)先出的值的排列
queue<int> q;
q.push(1);
q.push(2);
//移除最后一個
q.pop();
//獲得第一個
q.front();
//最后一個元素
cout << q.back() << endl;
優(yōu)先隊(duì)列(priority_queue )
元素的次序是由所存儲的數(shù)據(jù)的某個值排列的一種隊(duì)列
//最大的在隊(duì)首
priority_queue<int>;
//在vector之上實(shí)現(xiàn)的
priority_queue<int, vector<int>, less<int> >;
//vector 承載底層數(shù)據(jù)結(jié)構(gòu)堆的容器
//less 表示數(shù)字大的優(yōu)先級高，而 greater 表示數(shù)字小的優(yōu)先級高
//less 讓優(yōu)先隊(duì)列總是把最大的元素放在隊(duì)首
//greater 讓優(yōu)先隊(duì)列總是把最小的元素放在隊(duì)首
//less和greater都是一個模板結(jié)構(gòu)體 也可以自定義
class Student {
public:
int grade;
Student(int grade):grade(grade) {
}
};
struct cmp {
bool operator ()(Student* s1, Student* s2) {
// > 從小到大
// < 從大到小
return s1->grade > s2->grade;
}
bool operator ()(Student s1, Student s2) {
return s1.grade > s2.grade;
}
};
priority_queue<Student*, vector<Student*>, cmp > q1;
q1.push(new Student(2));
q1.push(new Student(1));
q1.push(new Student(3));
cout << q1.top()->grade << endl;
關(guān)聯(lián)式容器
關(guān)聯(lián)容器和大部分順序容器操作一致
關(guān)聯(lián)容器中的元素是按關(guān)鍵字來保存和訪問的 支持高效的關(guān)鍵字查找與訪問
集合(set)
由節(jié)點(diǎn)組成的紅黑樹，每個節(jié)點(diǎn)都包含著一個元素,元素不可重復(fù)
set<string> a;
set<string> a1={"fengxin","666"};
a.insert("fengxin"); // 插入一個元素
a.erase("123"); //刪除
鍵值對(map)
由{鍵，值}對組成的集合
map<int, string> m;
map<int, string> m1 = { { 1,"Lance" },{ 2,"David" } };
//插入元素
m1.insert({ 3,"Jett" });
//pair=鍵值對
pair<int, string> p(4, "dongnao");
m1.insert(p);
//insetrt 返回 map<int, string>::iterator : bool 鍵值對
//如果 插入已經(jīng)存在的 key，則會插入失敗
//multimap：允許重復(fù)key
//使用m1[3] = "xx" 能夠覆蓋
//通過【key】操作元素
m1[5] = "yihan";
cout << m1[5].c_str() << endl;
//通過key查找元素
map<int, string>::iterator it = m1.find(3);
cout << (*it).second.c_str()<< endl;
// 刪除
m1.erase(5);
//遍歷
for (it = m1.begin(); it != m1.end(); it++)
{
pair<int, string> item = *it;
cout << item.first << ":" << item.second.c_str() << endl;
}
//其他map================================
unordered_map c++11取代hash_map（哈希表實(shí)現(xiàn)，無序）
哈希表實(shí)現(xiàn)查找速度會比RB樹實(shí)現(xiàn)快,但rb整體更節(jié)省內(nèi)存
需要無序容器，高頻快速查找刪除，數(shù)據(jù)量較大用unordered_map；
需要有序容器，查找刪除頻率穩(wěn)定，在意內(nèi)存時用map。
