1.Stack 棧容器
棧同數(shù)據(jù)結(jié)構(gòu)的定義和特性一樣，自己去查狐赡，這里介紹棧的API
特別說(shuō)明：stack沒(méi)有遍歷行為Ｗ拆摹！
構(gòu)造函數(shù)
stack<T> stkT;//stack采用模板類實(shí)現(xiàn)，stack對(duì)象的默認(rèn)構(gòu)造函數(shù)
stack(const stack &stk);//拷貝構(gòu)造函數(shù)
stack賦值操作
stack & operator=(const stack &stk);//重載等號(hào)操作符
數(shù)據(jù)存取操作
void push(const TYPE & elem);//向棧頂添加一個(gè)元素
void pop();//從棧頂移除一個(gè)元素
TYPE & top();//返回棧頂元素
大小操作
bool empty();//判斷堆棧是否為空
int size();//返回堆棧的大小
2.Queue 隊(duì)列
2.1queue概念
queue是一種先進(jìn)先出(first in first out,FIFO)的數(shù)據(jù)類型鸟雏，它有兩個(gè)口享郊，數(shù)據(jù)元素只能從一個(gè)口進(jìn)，從另一個(gè)口出孝鹊。隊(duì)列只允許從隊(duì)尾加入元素炊琉，隊(duì)頭刪除元素，必須符合先進(jìn)先出原則又活，queue和stack一樣不具有遍歷行為苔咪！
1.png
特點(diǎn)
- 必須從一個(gè)口數(shù)據(jù)元素入隊(duì)，另一個(gè)口數(shù)據(jù)元素出隊(duì)
- 不能隨機(jī)存取柳骄，不支持遍歷
2.2queue常用API
構(gòu)造函數(shù)
queue<T> queT;//queue采用模板類實(shí)現(xiàn)团赏，queue對(duì)象的默認(rèn)構(gòu)造形式
queue(const queue &que);//拷貝構(gòu)造函數(shù)
queue存取、插入和刪除操作
void push(const TYPE &elem);//往隊(duì)尾添加元素
void pop();//從隊(duì)頭移除第一個(gè)元素
TYPE & back();//返回最后一個(gè)元素
TYPE & front();//返回第一個(gè)元素
queue賦值操作
queue& operator=(const queue &que);
queue大小操作
bool empty();//判斷隊(duì)列是否為空
int size();//返回隊(duì)列大小
3.list容器（雙向鏈表）
3.1list特性
鏈表是一種物理存儲(chǔ)單元上非連續(xù)耐薯、非順序的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)舔清，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針次序?qū)崿F(xiàn)的。鏈表由一系列的結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成可柿，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成鸠踪。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域丙者，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域
2.png
特性總結(jié)
- 采用動(dòng)態(tài)存儲(chǔ)分配复斥，不會(huì)造成內(nèi)存浪費(fèi)和溢出
- 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可械媒，不需要移動(dòng)大量元素
- 鏈表靈活目锭，但是空間和時(shí)間額外消耗較大
3.2 list常用API
list初始化
list<T> list;//默認(rèn)構(gòu)造函數(shù)
list(iterator beg,iterator end);//構(gòu)造函數(shù)將[beg,end)區(qū)間中的元素拷貝給本身
list(int n,TYPE & elem);//構(gòu)造函數(shù)將n個(gè)elem拷貝給自身
list(const list &lst);//拷貝構(gòu)造函數(shù)
list數(shù)據(jù)元素插入和刪除操作
void push_back(const TYPE &elem);//在容器尾部加入一個(gè)元素
void pop_back();//在容器尾部刪除一個(gè)元素
push_front(const TYPE &elem);//在容器頭部加入一個(gè)元素
pop_front(const TYPE &elem);//在容器開(kāi)頭移除一個(gè)元素
iterator insert(iterator pos,const TYPE & elem);//在pos位置插e(cuò)lem元素的拷貝，返回新數(shù)據(jù)的位置
void insert(iterator pos,int n,const TYPE &elem);//在pos位置插入n個(gè)elem元素
void insert(iterator pos,iterator beg,iterator end);//在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)
void clear();//移除容器的所有數(shù)據(jù)
iterator erase(iterator beg,iterator end);//刪除[beg,end)區(qū)間的數(shù)據(jù)纷捞，返回下一個(gè)數(shù)據(jù)的位置
iterator erase(iterator pos);//刪除pos位置的數(shù)據(jù)痢虹，返回下一個(gè)數(shù)據(jù)的位置
void remove(const &TYPE elem);//刪除容器中所有與elem值匹配的元素
大小操作
int size();//返回容器中的元素個(gè)數(shù)
bool empty();//判斷容器是否為空
void resize(int num);//重新制定容器長(zhǎng)度為num,若邊長(zhǎng)，則以默認(rèn)值填充新位置
//若變短主儡，則末尾超出容器長(zhǎng)度的元素被刪除
void resize(int num,const TYPE & elem);//重新制定容器長(zhǎng)度為num,若邊長(zhǎng)奖唯，則以elem填充新位置
//若變短，則末尾超出容器長(zhǎng)度的元素被刪除
list賦值操作
void assign(iterator beg,iterator end);//將[beg,end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身
void assign(int num,const TYPE &elem);//將n個(gè)elem拷貝給自身
list & operator=(const list &lst);//重載=號(hào)操作符
void swap(lst);//將lst與本身的元素互換
注意：assign和assign并不是疊加關(guān)系糜值，而是重新構(gòu)造的關(guān)系
list數(shù)據(jù)的存取
TYPE front();//返回第一個(gè)元素
TYPE back();//返回最后一個(gè)元素
list反轉(zhuǎn)排列排序
void reverse();//反轉(zhuǎn)鏈表 1,3,5 變 5,3,1
void sort();//List排序丰捷，默認(rèn)從小到大
鏈表和數(shù)組有什么區(qū)別
- 數(shù)組必須實(shí)現(xiàn)定義固定的長(zhǎng)度（元素個(gè)數(shù)），不能適應(yīng)數(shù)據(jù)動(dòng)態(tài)增減的情況寂汇。當(dāng)數(shù)據(jù)增加時(shí)病往，可能超出原先定義的元素的個(gè)數(shù)；當(dāng)數(shù)據(jù)減少時(shí)骄瓣，造成內(nèi)存浪費(fèi)
- 鏈表動(dòng)態(tài)地進(jìn)行存儲(chǔ)分配停巷，可以適應(yīng)數(shù)據(jù)動(dòng)態(tài)地增減的情況，且可以方便地插入、刪除
4. Set集合
4.1 set/multiset特性
set/multiset的特性是所有元素會(huì)根據(jù)元素的值自動(dòng)進(jìn)行排序畔勤。set是以RB-tree(紅黑樹,平衡二叉樹的一種)為底層機(jī)制蕾各，其查找效率非常好。set容器中不允許重復(fù)元素庆揪，multiset允許重復(fù)元素
1.png
問(wèn)：我們可以通過(guò)set的迭代器改變?cè)氐闹祮幔?/p>
答：不行示损，因?yàn)閟et集合是根據(jù)元素值進(jìn)行排序的，關(guān)系到set的排序規(guī)則嚷硫，如果任意改變set的元素值检访，會(huì)嚴(yán)重破會(huì)set組織。只能先刪掉仔掸，再插入脆贵，就是二叉排序樹的關(guān)系嘛！起暮！
set構(gòu)造函數(shù)
set<T> st;//默認(rèn)構(gòu)造函數(shù)
multiset<T> mst;//multiset默認(rèn)構(gòu)造函數(shù)
set(const set &st);//拷貝構(gòu)造函數(shù)
set賦值操作
set & operator=(const set &st);
void swap(st);//交換兩個(gè)集合器
set大小操作
int size();//返回容器中元素的數(shù)目
bool empty();//判斷容器是否為空
set插入和刪除操作
void insert(const TYPE & elem);//在容器中插入元素
void clear();//清楚所有元素
iterator erase(iterator pos);//刪除pos爹地器所指的元素卖氨，返回下一個(gè)元素的迭代器
iterator erase(iterator beg,iterator end);//刪除區(qū)間[beg,end)的所有元素，返回下一個(gè)元素的迭代器
int erase(const TYPE &elem);//刪除容器中值為elem的元素
void test(){
set<int> myset;//默認(rèn)從小到大排序
myset.insert(4);
myset.insert(2);
myset.insert(1);
myset.insert(5);
myset.insert(2);
printSet(myset);
//刪除
myset.erase(myset.begin());//刪除第一個(gè)元素
myset.erase(2);//根據(jù)元素值刪除
printSet(myset);
myset.erase(myset.beigin(),myset.end());//myset.clear();
cout<<"size:"<<myset.size();
}
2.png
multiset操作同理類似
#include <set>
int main(int argc, char const *argv[])
{
multiset<int> muset;
muset.insert(10);
muset.insert(20);
muset.insert(5);
muset.insert(35);
muset.insert(5);
for (multiset<int>::iterator it = muset.begin(); it != muset.end();it++)
{
cout<<*it<<" "<<endl;
}
return 0;
}
3.jpg
set查找操作
iterator find(const TYPE &key);//在當(dāng)前集合中查找等于key值的元素负懦，并返回指向該元素的迭代器筒捺；如果沒(méi)有找到，返回指向集合最后一個(gè)元素的迭代器纸厉。
iterator lower_bound(const TYPE &keyElem);//返回第一個(gè)>=keyElem元素的迭代器
iterator upper_bound(const TYPE &keyElem);//返回第一個(gè)>keyElem元素的迭代器
pairii equal_bound(const TYPE &keyElem);//返回容器中key與keyElem相等的上下限的兩個(gè)迭代器
class Teacher
{
public:
Teacher(int id,int age){
this->id = id;
this->age = age;
}
private:
int id;
int age;
}
class compare
{
public:
bool operator()(Teacher t1,Teacher t2){
return t1.id>t2.id;
}
}
void test(){
Teacher t1(1,2),t2(3,4),t3(5,6);
set<Teacher,compare> myset;
myset.insert(t1);
myset.insert(t2);
myset.insert(t3);
set<Teacher,compare>::iterator pos = myset.find(Teacher(3,10));
if (pos == myset.end())//竟然能查找到系吭，因?yàn)樗歉鶕?jù)id排序的
//所以查找也是根據(jù)id查找的,id = 3和t2重復(fù)！
//所以能查到
{
cout<<"沒(méi)有查找到!"<<endl;
}
else{
cout<<"查找到:"<<pos->id<<":"<<pos->age<<endl;
}
}
----------------------------------------------------
void test2(){
set<int> myset;
myset.insert(10);
myset.insert(5);
myset.insert(1);
myset.insert(8);
set<int>::iterator pos = myset.lower_bound(5);//查找第一個(gè)>=5的迭代器
if (pos ==myset.end())
{
cout<<"沒(méi)有找到"<<endl;
}
else{
cout<<"找到:"<<*pos<<endl;
}
pos = myset.upper_bound(5);//返回第一個(gè)>keyElem元素的迭代器
if (pos ==myset.end())
{
cout<<"沒(méi)有找到"<<endl;
}
else{
cout<<"找到:"<<*pos<<endl;
}
pair<set<int>::iterator,set<int>iterator> pos2 = myset.equal_range(5);
if (pos2.first == myset.end())
{
cout<<"沒(méi)有找到"<<endl;
}
else{
cout<<"找到:"<<*(pos2.first)<<endl;
}
if (pos2.second == myset.end())
{
cout<<"沒(méi)有找到"<<endl;
}
else{
cout<<"找到:"<<*(pos2.first)<<endl;
}
}
問(wèn)題：我們發(fā)現(xiàn)打印出來(lái)set集合中的元素都是從小到大的升序排序颗品，那么我們?nèi)绾沃贫ㄅ判驗(yàn)榻敌蚰乜铣撸窟@個(gè)問(wèn)題呢？我們需要了解函數(shù)對(duì)象的概念躯枢。
#include <functional>//預(yù)定義函數(shù)對(duì)象
set<int,greater<int>> myset;//從大到小
set<int,less<int>> myset;//從小到大
template<class T>
class compare{
public:
bool operator()(T v1,T v2) const{
return v1>v2;
}
};
//函數(shù)對(duì)象
compare mycom;
mycom<int>(1,2);//函數(shù)對(duì)象 仿函數(shù)
set<int,compare<int>> myset;
