C++標(biāo)準(zhǔn)模板庫STL深入講解
認(rèn)識STL
STL的概述
STL采用泛型思想，把C中所用到的所有的數(shù)據(jù)結(jié)構(gòu)，按照一定的標(biāo)準(zhǔn)，全部封裝成了一個(gè)個(gè)類模板。也被稱為數(shù)據(jù)容器。
STL就是用來解決容器中數(shù)據(jù)元素的操作的問題的。并且他按排標(biāo)準(zhǔn)統(tǒng)一封裝了操作容器元素的算法，即一個(gè)個(gè)的函數(shù)模板。
為了配合統(tǒng)一的算法去操作不同的容器，他又按標(biāo)準(zhǔn)統(tǒng)一封裝了不同的迭代器，即一個(gè)個(gè)不同類型的具有指針特性的類模板。
所以容器，算法，迭代器是整個(gè)STL的核心。
三者的關(guān)系如圖所示：
有了統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)，即容器，有了統(tǒng)一的算法，每一個(gè)容器都使用各自的不同的迭代器，從而實(shí)現(xiàn)了對數(shù)據(jù)結(jié)構(gòu)元素的標(biāo)準(zhǔn)操作。
STL標(biāo)準(zhǔn)模板庫都有什么
STL的知識結(jié)構(gòu)如圖：
容器
- 常用的數(shù)據(jù)結(jié)構(gòu)，C++重新封裝成了 vector（動態(tài)數(shù)組），list(鏈表)，deque（雙向隊(duì)列），set(集合) ，map(映射表)等，來實(shí)現(xiàn)存放數(shù)據(jù)，其中 set,map雙叫關(guān)聯(lián)容器 。其中的棧，單端隊(duì)列，優(yōu)先隊(duì)列，又都是線性數(shù)據(jù)結(jié)構(gòu)改造之后的具有各種特性的數(shù)據(jù)結(jié)構(gòu)，又叫做容器適配器。
- 序列式容器強(qiáng)調(diào)值的排序，序列式容器中的每個(gè)元素均有固定的位置，除非用刪除或插入的操作改變這個(gè)位置。vector容器，deque容器，List容器等。
- 關(guān)聯(lián)式容器是非線性的樹結(jié)構(gòu)，更準(zhǔn)確的說是二叉樹結(jié)構(gòu)，各元素之間沒有嚴(yán)格的物理上的順序關(guān)系，也就是說元素在容器中并沒有保存元素入容器時(shí)的邏輯順序 。關(guān)聯(lián)式容器另一個(gè)顯著特點(diǎn)是：在值中選擇一個(gè)值作為關(guān)鍵字Key,這個(gè)關(guān)鍵字對值起到了索引的作用，方便查找。Set/mulitiset容器 Map/multimap容器，并且容器是可以嵌套使用的。
算法
algorithom頭文件中的定義相關(guān)的操作的一系列的函數(shù)模板
STL收錄的算法經(jīng)過了數(shù)學(xué)上的效能分析與證明，且是經(jīng)過商業(yè)運(yùn)行考驗(yàn)過的，是極具復(fù)用價(jià)值 的，包括常用的排序，查找等。
? 算法又可為為兩種，質(zhì)變算法，與非質(zhì)變算法。
? 何為質(zhì)變算法：是指運(yùn)算過程中會更改區(qū)間內(nèi)的元素的內(nèi)容。例如：拷貝，替換，刪除等。
? 何為非質(zhì)變算法：是指運(yùn)算過程中不會更改區(qū)間內(nèi)的元素內(nèi)容，例如：查找，計(jì)數(shù)，遍歷，尋找極值等。
迭代器
迭代器的設(shè)計(jì)思維-STL 的關(guān)鍵所在，STL 的中心思想在于將容器(container)和算法(algorithms)分開，彼此獨(dú)立設(shè)計(jì)，最后再一貼膠著劑將他們撮合在一起。從技術(shù)角度來看，容器和算法的泛型化并不困難，c++的 class template 和 functiontemplate 可分別達(dá)到目標(biāo)，如果設(shè)計(jì)出兩這個(gè)之間的良好的膠著劑，才是大難題
提供一種方法，使之能夠依序?qū)ぴL某個(gè)容器所含的各個(gè)元素，而又無需暴露該容器的內(nèi)部表示方式,迭代器就被發(fā)明了出來。
函數(shù)符
在STL中主要用來為泛型算法提供策略。
有四種形式：全局函數(shù)指針，成員函數(shù)指針，仿函數(shù)（函數(shù)對象），與匿名函數(shù)Lambda表達(dá)式。
空間配置器
作用：主是用來解決內(nèi)存碎片化問題的，以及過多的構(gòu)造無用對象的問題。
容器的空間配置器的作用是把對象的內(nèi)存開辟和構(gòu)造過程分開，對象析構(gòu)和內(nèi)存釋放分離開 。那為什么要把對象的內(nèi)存開辟和構(gòu)造（new的兩個(gè)作用）分開，對象的析構(gòu)和內(nèi)存釋放（delete的兩個(gè)作用）分開呢？
1）因?yàn)樵谑褂萌萜鞯倪^程中，構(gòu)造一個(gè)容器，我們只想要容器的內(nèi)存空間，并不需要給我們在內(nèi)存上構(gòu)造一堆無用的對象出來（直接用new沒有辦法避免這個(gè)問題）；當(dāng)從容器中刪除一個(gè)元素的時(shí)候，我們需要析構(gòu)這個(gè)被刪除對象，但是它占用的容器內(nèi)存空間是不能釋放的，因?yàn)槿萜鬟€要使用；再比如我們需要釋放一個(gè)容器的時(shí)候，需要先把容器里面有效對象元素析構(gòu)一遍，而不是把容器所有元素都析構(gòu)一遍（用delete無法避免這個(gè)問題），所以在操作容器的過程中，我們需要有選擇性的分別去開辟內(nèi)存，構(gòu)造對象，析構(gòu)對象，所以這就是空間配置器存在的意義。
C++ 標(biāo)準(zhǔn)STL里面提供的allocator空間配置器，默認(rèn)的內(nèi)存分配和釋放就是依賴malloc和free實(shí)現(xiàn)的。SGI STL提供了兩個(gè)版本的空間配置器，一級空間配置器和二級空間配置器。一級空間配置器的內(nèi)存管理也是通過malloc和free實(shí)現(xiàn)的，但是SGI STL的二級空間配置器提供了一個(gè)內(nèi)存池的實(shí)現(xiàn)。第二級配置器的設(shè)計(jì)思想為：
1.如果配置區(qū)塊超過128 bytes，則移交給第一級配置器處理（空間配置器）；
2.如果配置區(qū)塊小于128 bytes，則采用內(nèi)存池管理（memory pool）。每次配置一大塊內(nèi)存，則維護(hù)對應(yīng)的自由鏈表（free-list），下次若再有相同大小的內(nèi)存需求，就直接從 free-list 中撥出（沒有就繼續(xù)配置內(nèi)存，具體后面講述），如果客端釋換小額區(qū)塊，就有配置器回收到 free-list 中。
對于SGI STL的二級空間配置器的內(nèi)存池實(shí)現(xiàn)機(jī)制，還是非常重要的，因?yàn)檫@既涉及了空間配置器，又涉及了一個(gè)內(nèi)存池的實(shí)現(xiàn)機(jī)制，因此大家需要好好的理解它的原理，大家在手寫C++空間配置器的過程中，使用過nginx的內(nèi)存池作為空間配置器的內(nèi)存管理方案，這又是一個(gè)新的積累。
string字符容器庫
字符串容器API接口：
#include <iostream>
using namespace std;
int main()
{
string str(15,'g');
string str10;
str10.assign(10,'k');
cout << str << endl;
string str1(str,5);
cout << str1 << endl;
string str2("yaoliang",8);
cout << str2 << endl;
const char* s1=str2.data();
const char* s=str2.c_str();
cout << s << endl;
//獲取迭代器
string::iterator it;
for(it=str2.begin();it!=str2.end();it++){
cout << *it << " ";
}
cout << endl;
//獲取反向迭代器
string::reverse_iterator it1;
for(it1=str2.rbegin();it1!=str2.rend();it1++){
cout << *it1 << " ";
}
cout << endl;
cout << str2.size() << endl;
cout << str2.length() << endl;
cout << str2.capacity() << endl;//已經(jīng)開辟好的空間
cout << str2.max_size() << endl;//最大容量
//string 容量對象保存字符時(shí)，如果是小字符串（小于23個(gè)字節(jié)）,會在棧上開辟空間
//如果是大對象(大于23個(gè)字節(jié)),會在堆上開辟空間
//查看動態(tài)開辟空間策略（2倍擴(kuò)容）
// string str_test;
// cout << str_test.capacity() << endl;
// for(int i=0;i<1024;i++){
// cout << "string容器對象中的有效元素個(gè)數(shù):" << str_test.size() <<
// "，string容器對象中的容量大小:" << str_test.capacity() << endl;//采取2倍擴(kuò)容機(jī)制
// str_test.push_back('a');
// }
cout << str1.insert(0,3,'A') << endl;
cout << str1 << endl;
cout << str1.insert(0,"hello") << endl;
cout << str1.erase(0,6) << endl;
cout << str2.find("liang") << endl;
cout << str2.substr(3,5) << endl;
cout << str2.replace(3,5,"ming");
return 0;
}
vector容器
vector容器于array數(shù)組容器的區(qū)別
vector與array無乎是一樣的，連續(xù)的存儲結(jié)構(gòu)，兩者的唯一的區(qū)別在于在空間上的靈活，數(shù)組需要提前指定長度，不量確定了就不能發(fā)生改變了，比較死板，不夠靈活。比如出現(xiàn)拷貝長度大于了給定的空間，需要再重新定義一個(gè)足夠空間的大小，然后把舊空間的內(nèi)容再一個(gè)個(gè)拷貝到新的空間，非常麻煩。
c++11引入array主要是用來描述一種支持迭代器的C風(fēng)格數(shù)組的，所以數(shù)組怎么用，array就怎么用，他定義在棧上，且長度固定不會涉及動態(tài)內(nèi)存的開辟所以沒有push_back,pop_back的相關(guān)方法，但是Vector這種動態(tài)的數(shù)組在開發(fā)更為常用，他底層對象在堆上，且長度是可變的。
vector容器是動態(tài)空間，他隨著元素的加入，它的內(nèi)部機(jī)制會自動擴(kuò)充空間以容納新的元素。vector的運(yùn)用對于內(nèi)存的合理利用與運(yùn)用的靈活性有很大的幫助。我們再也不必害怕空間不足而一開始就定義一個(gè)巨大的數(shù)組了。
實(shí)現(xiàn)分析：
空間分配策略
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//動態(tài)擴(kuò)容的策略（沒內(nèi)容不先開辟空間，不同于string）
vector<int> v;
for(int i=0;i<100;i++){
cout << "vector容器對象中的有效元素個(gè)數(shù):" << v.size() << "vector容器容量的大小:" << v.capacity() << endl;
v.push_back(i);
}
return 0;
}
迭代器非法化問題及解決
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
cout << endl;
//insert后,迭代器非法化的問題
for(vector<int>::iterator it=v.begin();it!=v.end();it++){
if(0==*it%2){
it=v.insert(it,888);//返回值為迭代器類型
it++;//更新迭代器
}
}
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
cout << endl;
//erase迭代器非法化的問題
for(auto it=v.begin();it!=v.end();){
if(0==*it%2){
it=v.erase(it);//返回值為容器類型
}else{
it++;
}
}
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
cout << endl;
return 0;
}
泛型算法
泛型算法 = 函數(shù)模板 + 迭代器范圍（注意迭代器的類型） + 函數(shù)符（策略使用）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int i=0;i<v.size();i++){
cout << v[i] << " ";
}
cout << endl;
cout << "----------------使用泛型算法進(jìn)行遍歷-------------" << endl;
for_each(v.begin(),v.end(),[](int val){cout << val << "-";});
cout << endl;
//針對于容器中有迭代器的容器for_each算法，提供了一種變種：枚舉for循環(huán)
for(int val:v){//val默認(rèn)為第0個(gè)元素，一次遍歷，直到結(jié)束為止
cout << val << "-" ;
}
cout << endl;
return 0;
}sort：
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
template <class T>
T my_greate(T t1,T t2){
return t1>t2;
}
template <class T>
class my_Greate{
public:
bool get_my_Greate(T t1,T t2){
return t1>t2;
}
};
int main()
{
vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
cout << "---------------------1---------------------" << endl;
//sort,ASC//升序
sort(v.begin(),v.end());
for(int k:v){
cout << k << " ";
}
cout << endl;
cout << "----------------------2--------------------" << endl;
//sort,DESC,使用lambda表達(dá)式作為算法策略
sort(v.begin(),v.end(),[](int val1,int val2){return val1>val2;});//一直判斷到最后
//如果val1>val2為真，就把val1排好序，可以把函數(shù)符想象成一個(gè)抽象（必須這么理解，因?yàn)榫唧w排序要看sort實(shí)現(xiàn)了），不是算法的具體實(shí)現(xiàn)，算法知道意思，就是降序了
for(int k:v){
cout << k << " ";
}
cout << endl;
cout << "----------------------3--------------------" << endl;
//使用函數(shù)對象
sort(v.begin(),v.end(),greater<int>());//這是調(diào)用庫函數(shù)中的函數(shù)對象
for(int k:v){
cout << k << " ";
}
cout << endl;
cout << "----------------------4--------------------" << endl;
//定義一個(gè)函數(shù)指針，函數(shù)符來實(shí)現(xiàn)
sort(v.begin(),v.end(),&my_greate<int>);//這個(gè)就是全局函數(shù)指針，函數(shù)符實(shí)現(xiàn)
for(int k:v){
cout << k << " ";
}
cout << endl;
//定義一個(gè)成員函數(shù)指針，函數(shù)符來實(shí)現(xiàn)
//因?yàn)槌蓡T函數(shù)指針依賴于對象的調(diào)用，所以不可以有直接做為策略使用，需要綁定器進(jìn)行對象綁定才可以
cout << "----------------------5--------------------" << endl;
my_Greate<int> m;
using namespace placeholders;
sort(v.begin(),v.end(),bind(&my_Greate<int>::get_my_Greate,&m,_1,_2));
for(int k:v){
cout << k << " ";
}
cout << endl;
return 0;
}binary_find:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
//sort,ASC
sort(v.begin(),v.end());
for(int k:v){
cout << k << " ";
}
cout << endl;
//時(shí)間復(fù)雜度O（logn）
bool ok=binary_search(v.begin(),v.end(),70);
if(ok)
cout << "find succeed!" << endl;
else
cout << "find failure!" << endl;
return 0;
}find&&find_if&&bind1st(綁定第一個(gè)參數(shù))&&bind2nd(綁定第二個(gè)參數(shù))&&bind(新式綁定器):
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
//find對容器中的值沒有要求,時(shí)間復(fù)雜度O(n),順序遍歷一遍，和二分查找不一樣，時(shí)間復(fù)雜度不同
auto it=find(v.begin(),v.end(),70);
if(it!=v.end()){
cout << "find succeed!index:" << it-v.begin() << endl;
}else{
cout << "find failure!" << endl;
}
//find_if按條件查找,需要把一個(gè)2這個(gè)值按序插入到序列中
it=find_if(v.begin(),v.end(),[](int val){return val < 2;});
if(it!=v.end()){
it=v.insert(it,2);
it++;
cout << "find succeed!" << endl;
}else{
cout << "find failure!" << endl;
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
//老式綁定器bind1st,bind2nd
it=find_if(v.begin(),v.end(),bind1st(greater<int>(),2));
if(it!=v.end()){
it=v.insert(it,2);
it++;
cout << "find succeed!" << endl;
}else{
cout << "find failure!" << endl;
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
//新式綁定器:bind
using namespace placeholders;
it=find_if(v.begin(),v.end(),bind(greater<int>(),2,_1));
if(it!=v.end()){
it=v.insert(it,2);
it++;
cout << "find succeed!" << endl;
}else{
cout << "find failure!" << endl;
}
for(int val:v){
cout << val << " " ;
}
cout << endl;
return 0;
}迭代器與空間配置器
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//實(shí)現(xiàn)一個(gè)自定的空間配置器
template <class T>
struct Allocate{
//1.開辟空間
T* allocate(size_t size){
T* temp=(T*)malloc(sizeof (T)*size);
if(nullptr==temp){
throw bad_alloc();
}
return temp;
}
//2.構(gòu)造對象
void constructor(T* p,const T& obj){
//定位new
new (p) T(obj);
}
//3.析構(gòu)對象
void destructor(T* p){
p->~T();
}
//4.釋放空間
void destroy(T* p){
free(p);
}
};
template <class T,class Allocat=Allocate<T>>
class Vector{
private:
T* _frist;
T* _last;
T* _end;
Allocat _allcater;
public:
Vector(int size=10){
// this->_frist=new T[size];
this->_frist=_allcater.allocate(size);
this->_last=_frist;
this->_end=this->_frist+size;
}
~Vector(){
if(nullptr!=this->_frist){
// delete [] this->_frist;
for(T* p=_frist;p!=_last;p++){
_allcater.destructor(p);
}
}
_allcater.destroy(_frist);
this->_end=this->_last=this->_frist=nullptr;
}
//拷貝構(gòu)造
Vector(const Vector& other){
int size=other._end-other._frist;
// this->_frist=new T[size];
this->_frist=_allcater.allocate(size);
int len=other._end-other._frist;
memmove(this->_frist,other._frist,sizeof (T)*len);
this->_last=this->_frist+len;
this->_end=this->_frist+size;
}
//等號運(yùn)算符重載
Vector& operator=(const Vector& other){
if(this==&other){
return *this;
}
int size=other._end-other._frist;
int len=other._last-other._frist;
if(nullptr!=this->_frist){
// delete [] this->_frist;
// this->_frist=new T[size];
for(T* p=_frist;p!=_last;p++){
_allcater.destructor(p);
}
_allcater.destroy(_frist);
this->_frist=_allcater.allcate(size);
}else{
// this->_frist=new T[size];
this->_frist=_allcater.allcate(size);
}
memmove(this->_frist,other._frist,sizeof (T)*len);
this->_last=this->_frist+ len;
this->_end=this->_frist+size;
return *this;
}
bool full(){
return this->_last==this->_end;
}
bool empty(){
return this->_last==this->_frist;
}
//2倍擴(kuò)容
void expand(){
int size=this->_end-this->_frist;
// T* temp=new T[size* 2];
T* temp=_allcater.allocate(size*2);
memmove(temp,this->_frist,sizeof (T)*size);
// delete [] this->_frist;
for(T* p=_frist;p!=_last;p++){
_allcater.destructor(p);
}
_allcater.destroy(_frist);
this->_frist=temp;
this->_last=this->_frist+size;
this->_end=this->_frist+size*2;
}
void push_back(const T& val){
if(this->full()){
this->expand();
}
// *_last++=val;
_allcater.constructor(this->_last,val);
_last++;
}
void pop_back(){
if(this->empty()){
return;
}
// _last--;
_last--;
_allcater.destructor(_last);
}
int size(){
return this->_last-this->_frist;
}
int capacity(){
return this->_end-this->_frist;
}
T& operator[](int index){
if(index<0||index>=this->size()){
throw out_of_range("越界！");
}
return this->_frist[index];
}
class iterator{
public:
//與標(biāo)準(zhǔn)庫中的泛型算法匹配類型
using difference_type=int;
using value_type= T ;
using pointer=T*;
using reference=T&;
using iterator_category=random_access_iterator_tag;
private:
T* ptr;
public:
iterator(T* ptr=nullptr){
this->ptr=ptr;
}
//迭代器功能：++運(yùn)算，！=運(yùn)算
iterator& operator++(){
++this->ptr;
return *this;
}
iterator& operator++(int){
this->ptr++;
return *this;
}
iterator& operator--(){
--this->ptr;
return *this;
}
iterator& operator--(int){
this->ptr--;
return *this;
}
// !=運(yùn)算符重載：
bool operator!=(const iterator& other){
return this->ptr!=other.ptr;
}
bool operator==(const iterator& other){
return this->ptr==other.ptr;
}
T& operator*(){
return *ptr;
}
T* operator->(){
return ptr;
}
iterator& operator+=(int n){
this->ptr+=n;
return *this;
}
iterator& operator-=(int n){
this->ptr-=n;
return *this;
}
iterator operator+(int n){
T* temp=this->ptr+n;
return iterator(temp);
}
iterator operator-(int n){
T* temp=this->ptr-n;
return iterator(temp);
}
int operator-(const iterator& other){
return this->ptr-other.ptr;
}
bool operator>(const iterator& other){
return this->ptr - other.ptr > 0;
}
bool operator<(const iterator& other){
return this->ptr - other.ptr < 0;
}
bool operator>=(const iterator& other){
return !(*this < other);
}
bool operator<=(const iterator& other){
return !(*this > other);
}
T* get(){
return ptr;
}
};
iterator begin(){
return iterator(this->_frist);
}
iterator end(){
return iterator(this->_end);
}
};
class A{
public:
A(){
cout << "A structure" << endl;
}
~A(){
cout << "A destruct" << endl;
}
A(const A&other){
cout << "A copy" << endl;
}
};
int main()
{
Vector<int> v;
for(int i=0;i<20;i++){
v.push_back(rand()%100+1);
}
for(int i=0;i<v.size();i++){
cout << v[i] << " " ;
}
cout << endl;
Vector<A> v1;
Vector<int> v2;
for(int i=0;i<20;i++){
v2.push_back(rand()%100+1);
}
for(int k:v2){
cout << k << " " ;
}
cout << endl;
return 0;
}deque容器
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
deque<int> dq;
for(int i=0;i<20;i++){
dq.push_front(rand()%100+1);
}
for(auto it=dq.begin();it!=dq.end();it++){
cout << *it << " ";
}
cout << endl;
sort(dq.begin(),dq.end());
for(int k:dq){
cout << k << " ";
}
cout << endl;
for(int i=0;i<20;i++){
cout << dq.back() << " ";
dq.pop_back();
}
cout << endl;
for(int i=0;i<20;i++){
cout << dq.front() << " ";
dq.pop_front();
}
cout << endl;
return 0;
}容器適配置
容器適配器是沒有迭代器的，不能實(shí)現(xiàn)泛型算法
使用deque容器實(shí)現(xiàn)一個(gè)stack
#include <iostream>
#include <deque>
using namespace std;
template <class T,class Container=deque<T>>
class Stack{
private:
Container container;
public:
void push(const T& val){
container.push_back(val);
}
void pop(){
container.pop_back();
}
T& top(){
return container.back();
}
bool empty(){
return container.empty();
}
};
int main()
{
Stack<int> s;
for(int i=0;i<10;i++){
s.push(i);
cout << i << " ";
}
cout << endl;
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}實(shí)現(xiàn)一個(gè)單端隊(duì)列
#include <iostream>
#include <deque>
using namespace std;
template <class T,class Container=deque<T>>
class SimpleQ{
private:
Container container;
public:
void push(const T& val){
container.push_back(val);
}
void pop(){
container.pop_front();
}
T& top(){
return container.front();
}
bool empty(){
return container.empty();
}
};
int main()
{
SimpleQ<int> q;
for(int i=0;i<10;i++){
q.push(i);
cout << i << " ";
}
cout << endl;
while (!q.empty()) {
cout << q.top() << " ";
q.pop();
}
cout << endl;
return 0;
}優(yōu)先隊(duì)列
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T,class Container=vector<T>,class Compair=less<T>>
class Priority_queue{
private:
Container container;
Compair compair;
public:
Priority_queue(){
make_heap(container.begin(),container.end(),compair);
}
void push(const T& val){
container.push_back(val);
// sort(container.begin(),container.end(),compair);//快排,但系統(tǒng)中采取的是大頂堆，原因快排，遞歸過多
push_heap(container.begin(),container.end(),compair);
}
void pop(){
pop_heap(container.begin(),container.end(),compair);
container.pop_back();
}
T& top(){
return container.front();
// return container.back();
}
bool empty(){
return container.empty();
}
};
int main()
{
Priority_queue<int> pq;
for(int i=0;i<20;i++){
pq.push(rand()%100+1);
}
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}list容器
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> l;
for(int i=0;i<20;i++){
l.push_back(rand()%100+1);
}
for(int k:l){
cout << k << " ";
}
cout << endl;
l.sort();
for_each(l.begin(),l.end(),[](int val){cout << val << " ";});
cout << endl;
l.sort([](int val1,int val2){return val1>val2;});
for_each(l.begin(),l.end(),[](int val){cout << val << " ";});
cout << endl;
return 0;
}set容器
Set特性是：所有元素都會根據(jù)元素的鍵值自動被排序。（set 與 map都會按照鍵值來自動排序，只不過set的鍵與值是一體的相同的）Set的元素不像map那樣，可以同時(shí)擁有實(shí)值與鍵值，set的元素即是鍵值又是實(shí)值。（你也可以理解為只有一個(gè)值，鍵與值相同）Set不允許兩個(gè)元素有相同的鍵值。（即然是自動排序，set與map是不允許有相同的鍵的存在。這一點(diǎn)與map是共同的。），而multiset是可以存相同鍵值的元素。（這是set與multiset的唯一區(qū)別。）。
所以set容器的迭代器是一個(gè)常雙向迭代器，只支持什么：++，–，==，!=的操作。
我們可以通過set的迭代器改變set元素的值嗎？不行，因?yàn)閟et元素值就是其鍵值，關(guān)系到set元素排序規(guī)則，如果任意改變set元素值，會嚴(yán)重破壞set組織結(jié)構(gòu)。換句話說，set的迭代器是一個(gè)只讀迭代器。
set容器擁有與list某些相同的性質(zhì)，當(dāng)對容器中的元素進(jìn)行插入操作或者刪除操作的時(shí)候，操作之前所有迭代器，在操作完成之后依
multiset的底層實(shí)現(xiàn)是紅黑樹，紅黑樹是平衡二叉樹的一種。二叉樹的相關(guān)知識點(diǎn)可以百度一下。
#include <iostream>
#include <set>
using namespace std;
class Stu{
private:
string name;
int age;
public:
Stu(string name,int age){
this->age=age;
this->name=name;
}
// bool operator<(const Stu& other)const{
// return this->age<other.age;
// }
void showInfo()const{
cout << "姓名：" << name << "，年齡：" << age << endl;
}
int getAge(){
return this->age;
}
};
template <class T>
class Myless{
public:
bool operator()(T t1,T t2)const{
return t1.getAge()<t2.getAge();
}
};
int main()
{
set<int> s;
for(int i=0;i<20;i++){
s.insert(rand()%100+1);
}
for(int k:s){
cout << k << " ";
}
cout << endl;
cout << "*********************自定義類型放入set****************" << endl;
Stu stu1("yaoliang",19);
Stu stu2("minmin",18);
Stu stu3("sun",17);
// set<Stu> s1;//調(diào)用庫中的<預(yù)算符重載函數(shù)
// s1.insert(stu1);
// s1.insert(stu2);
// s1.insert(stu3);
// for(const Stu& stu:s1){
// stu.showInfo();
// }
set<Stu,Myless<Stu>> s1;//自定義比較策略
s1.insert(stu1);
s1.insert(stu2);
s1.insert(stu3);
for(const Stu& stu:s1){
stu.showInfo();
}
return 0;
}multiset與set
#include <iostream>
#include <set>
using namespace std;
class Stu{
private:
string name;
int age;
int id;
public:
Stu(string name,int age,int id){
this->age=age;
this->name=name;
this->id=id;
}
bool operator<(const Stu& other)const{
return this->id<other.id;
}
void showInfo()const{
cout << "學(xué)號：" << id << "，姓名：" << name << "，年齡：" << age << endl;
}
int getAge(){
return this->id;
}
};
int main()
{
Stu stu1("王大錘",19,1);
Stu stu2("李二狗",18,2);
Stu stu3("張三豐",17,3);
Stu stu4("王五子",17,5);
Stu stu5("劉四思",20,3);
// set<Stu> s1;//調(diào)用庫中的<預(yù)算符重載函數(shù)
multiset<Stu> s1;
s1.insert(stu1);
s1.insert(stu2);
s1.insert(stu3);
s1.insert(stu5);
s1.insert(stu4);
// pair<set<Stu>::iterator,bool> p;
// p=s1.insert(stu4);
// if(p.second){
// cout << "王五子入學(xué)成功！" << endl;
// }else{
// cout << " 王五子入學(xué)失敗！" << "\n";
// }
for(const Stu& stu:s1){
stu.showInfo();
}
return 0;
}map容器
對組pair構(gòu)建方式：
#include <iostream>
#include <map>
using namespace std;
int main()
{
pair<string,int> p1("zhangsan",1001);
cout << p1.first << "," << p1.second << endl;
pair<string,int> p2={"lisi",1002};
cout << p2.first << "," << p2.second << endl;
pair<string,int> p3;
p3.first="maliu";
p3.second=1003;
cout << p3.first << "," << p3.second << endl;
pair<string,int> p4=make_pair("wangwu",1004);
cout << p4.first << "," << p4.second << endl;
pair<string,int> p5=map<string,int>::value_type("tianqi",1005);
return 0;
}Map容器的特性是：所有元素都會根據(jù)元素的鍵的值自動排序。Map所有的元素都是統(tǒng)一的pair對組，同時(shí)擁有鍵值Key實(shí)值Value，pair的第一元素被視為鍵值，第二個(gè)元素被視為實(shí)值，map不允許兩個(gè)元素有相同的鍵。
我們可以通過map迭代器改變map的鍵值嗎？答案是不行，因?yàn)閙ap的鍵值關(guān)系到map的元素的排列布局，Map中的鍵是不可修改的，但是鍵對應(yīng)的值是可以修改的。
所以Map的迭代器是一個(gè)雙向迭代器，只支持++ == ！=操作。
Map是可以隨時(shí)插入或刪除鍵值對的。
Map與multimap的唯一區(qū)別是multimap中的鍵是可以重復(fù)的。
Map的底層實(shí)現(xiàn)機(jī)制是由二叉樹中的紅黑樹進(jìn)行實(shí)現(xiàn)的。
#include <iostream>
#include <map>
using namespace std;
int main()
{
pair<string,int> p1("zhangsan",1001);
pair<string,int> p2={"lisi",1002};
pair<string,int> p3;
p3.first="maliu";
p3.second=1003;
pair<string,int> p4=make_pair("wangwu",1004);
pair<string,int> p5=map<string,int>::value_type("tianqi",1005);
map<string,int> m1;
m1.insert(p1);
m1.insert(p2);
m1.insert(p3);
m1.insert(p4);
m1.insert(p5);
for(pair<string,int> p:m1){
cout << p.first << p.second << endl;
}
cout <<m1.at("zhangsan") << endl;
// cout <<m1.at("********") << endl;
cout << m1["zhangsan"] << endl;
cout << "------------------map[] not exist throw-------------" << endl;
cout << m1["**********"] << endl;//副作用，會保存不存在的值
for(pair<string,int> p:m1){
cout << p.first << p.second << endl;
}
cout << "-----------------find-------------" << endl;
auto it=m1.find("lisi");
if(it!=m1.end()){
cout << it->first << "," << it->second << endl;
}else{
cout << "no find!!!" << endl;
}
return 0;
}注意:multimap中是沒有【】中括號運(yùn)算符的：
map中的[]注意事項(xiàng)：
map中的[]運(yùn)算符具有兩個(gè)作用：
? 1.就是可以在map容器直接插入一個(gè)鍵值對。
? 2.當(dāng)map容器有同名的key時(shí)，使用[]也可修飾key對應(yīng)的value的值。
? 3.注意：在multimap中是沒有[]中括號運(yùn)算符的。
? 4.中括號運(yùn)算符如果map沒有這個(gè)鍵時(shí)，將會自動插入這個(gè)鍵值對。
觀察者設(shè)計(jì)模型
引言
用來解決兩個(gè)不相關(guān)對象之間的一對一或者一對多的通信模型。
什么是觀察者設(shè)計(jì)模式
觀察者模式是一種對象行為模式。它定義對象間的一種一對多的依賴關(guān)系， 當(dāng)一個(gè)對象的狀態(tài)發(fā)生改變時(shí)，所有依賴于它的對象都得到通知并被自動更新。在觀察者模式中，主體是通知的發(fā)布者，它發(fā)出通知時(shí)并不需要知道誰是它的觀察者，可以有任意數(shù)目的觀察者訂閱并接受通知。觀察者模式不僅被廣泛應(yīng)用于軟件界面元素之間的交互，在業(yè)務(wù)對象之間的交互、權(quán)限管理等方面也有廣泛的應(yīng)用。
解決的問題
定義了對象間的一種一對多的組合關(guān)系，以便一個(gè)對象的狀態(tài)發(fā)生時(shí)，所有依賴于它的對象都得到通知并自動刷新。
觀察者和被觀察者之間存在“觀察”的邏輯關(guān)系，當(dāng)被觀察者發(fā)生變化時(shí)，觀察者就會觀察到這樣的變化，并作出相應(yīng)的響應(yīng)。
編程思路
設(shè)定兩者類，一個(gè)為觀察者類，一個(gè)為被觀察者類
觀察者類中，定義一個(gè)對某個(gè)事件感興趣的處理函數(shù)，一般也叫做槽函數(shù)
被觀察者類中，定義一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來保存觀察者對某一個(gè)事件id（信號）感興趣，使用數(shù)據(jù)結(jié)構(gòu)建立信號與對象之間的映射關(guān)系
被觀察者類中，定義兩個(gè)方法函數(shù)：
一個(gè)方法為：添加觀察者與其感興趣的事件id（信號）加入到容器中
另一個(gè)方法為：信號函數(shù)：通知事件函數(shù)執(zhí)行邏輯：首先遍歷容器中，有沒有感興趣的事件ID，如果有，則代表一系列的觀察者，對這個(gè)事件感興趣，那么再次遍歷觀察者列表，讓每一個(gè)觀察者執(zhí)行相應(yīng)的槽函數(shù)
#include <iostream>
#include <map>
#include <list>
using namespace std;
class RecvBase
{
public:
RecvBase(){
cout << "--------------RecvBase structure------------------" << endl;
}
virtual void slotFunctions(int msgid)=0;
virtual~RecvBase()
{
cout << "--------------RecvBase destruct------------" << endl;
}
};
class Recv:public RecvBase
{
public:
void slotFunctions(int msgid)override
{
switch(msgid)
{
case 1:
cout << "接收到1信號，執(zhí)行信號1對應(yīng)槽函數(shù)邏輯" << endl;
break;
case 2:
cout << "接收到2信號，執(zhí)行信號2對應(yīng)槽函數(shù)邏輯" << endl;
break;
case 3:
cout << "接收到3信號，執(zhí)行信號3對應(yīng)槽函數(shù)邏輯" << endl;
break;
case 4:
cout << "接收到4信號，執(zhí)行信號4對應(yīng)槽函數(shù)邏輯" << endl;
break;
}
}
Recv()
{
cout << "--------------structure--------------" << endl;
}
~Recv()override
{
cout << "--------------destruct------------" << endl;
}
};
class Sender
{
public:
map<int,list<RecvBase*>> recvMap;
void addRecvToMap(int msgid,RecvBase* recv)
{
this->recvMap[msgid].push_back(recv);
}
void signals(int msgid)
{
auto it=recvMap.find(msgid);
if(it!=recvMap.end())
{
for(RecvBase* p:it->second)
p->slotFunctions(msgid);
}else
{
cout << "接受到未知信號，沒有信號對應(yīng)的槽函數(shù)邏輯" << endl;
}
}
};
int main(){
Sender sender;
RecvBase* r1=new Recv();
RecvBase* r2=new Recv();
RecvBase* r3=new Recv();
RecvBase* r4=new Recv();
sender.addRecvToMap(1,r1);
sender.addRecvToMap(2,r2);
sender.addRecvToMap(3,r3);
sender.addRecvToMap(4,r4);
int msgid;
while(true)
{
cin >> msgid;
if(-1==msgid)break;
sender.signals(msgid);
}
delete r1;
delete r2;
delete r3;
delete r4;
return 0;
}到此這篇關(guān)于C++標(biāo)準(zhǔn)模板庫STL深入講解的文章就介紹到這了,更多相關(guān)C++標(biāo)準(zhǔn)模板庫內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Qt實(shí)現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細(xì)介紹了Qt是如何實(shí)現(xiàn)編輯數(shù)據(jù)庫數(shù)據(jù)的，文中的示例代碼簡潔易懂，對我們深入了解QT有一定的幫助，感興趣的小伙伴可以了解一下2023-02-02
C語言實(shí)現(xiàn)掃雷小游戲(擴(kuò)展版可選擇游戲難度)
游戲目標(biāo)是找出所有沒有地雷的方格，完成游戲；要是按了有地雷的方格，游戲失??；玩家可標(biāo)記雷的位置,游戲以完成時(shí)間來評高低,并且用戶可以選擇游戲難度2019-10-10
在C/C++中有一個(gè)基礎(chǔ)且重要的知識，什么是聲明？什么是定義？他們的區(qū)別是什么？本文將帶你理清其中的區(qū)別2022-07-07
本文詳細(xì)講解了C語言實(shí)現(xiàn)掃雷并附完整代碼，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-11-11
這篇文章主要介紹了C語言寫一個(gè)散列表,散列表，就是下標(biāo)可以為字母的數(shù)組。更多內(nèi)容和小編一起學(xué)習(xí)下面內(nèi)容吧2022-01-01
這篇文章主要介紹了C/C++中虛基類的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細(xì)介紹了C++哈希應(yīng)用中的位圖、哈希切分與布隆過濾器，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，需要的可以參考一下2023-04-04
整數(shù)拆分，指把一個(gè)整數(shù)分解成若干個(gè)整數(shù)的和。本文重點(diǎn)給大家介紹C++ 整數(shù)拆分方法詳解，非常不錯(cuò)，感興趣的朋友一起學(xué)習(xí)吧2016-08-08
本文將詳細(xì)介紹for循環(huán)的用法并提供相關(guān)的可編譯運(yùn)行的C代碼示例，代碼簡單易懂，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，感興趣的朋友一起看看吧2023-06-06
C++實(shí)現(xiàn)編碼轉(zhuǎn)換的示例代碼
這篇文章主要介紹了C++實(shí)現(xiàn)編碼轉(zhuǎn)換的示例代碼，幫助大家快捷的實(shí)現(xiàn)編碼轉(zhuǎn)換，感興趣的朋友可以了解下2020-08-08