C++标准模板库STL深入讲解
编程远泊 人气:0认识STL
STL的概述
STL采用泛型思想,把C中所用到的所有的数据结构,按照一定的标准,全部封装成了一个个类模板。也被称为数据容器。
STL就是用来解决容器中数据元素的操作的问题的。并且他按排标准统一封装了操作容器元素的算法,即一个个的函数模板。
为了配合统一的算法去操作不同的容器,他又按标准统一封装了不同的迭代器,即一个个不同类型的具有指针特性的类模板。
所以容器,算法,迭代器是整个STL的核心。
三者的关系如图所示:
有了统一的数据结构,即容器,有了统一的算法,每一个容器都使用各自的不同的迭代器,从而实现了对数据结构元素的标准操作。
STL标准模板库都有什么
STL的知识结构如图:
容器
- 常用的数据结构,C++重新封装成了 vector(动态数组),list(链表),deque(双向队列),set(集合) ,map(映射表)等,来实现存放数据,其中 set,map双叫关联容器 。其中的栈,单端队列,优先队列,又都是线性数据结构改造之后的具有各种特性的数据结构,又叫做容器适配器。
- 序列式容器强调值的排序,序列式容器中的每个元素均有固定的位置,除非用删除或插入的操作改变这个位置。vector容器,deque容器,List容器等。
- 关联式容器是非线性的树结构,更准确的说是二叉树结构,各元素之间没有严格的物理上的顺序关系,也就是说元素在容器中并没有保存元素入容器时的逻辑顺序 。关联式容器另一个显著特点是:在值中选择一个值作为关键字Key,这个关键字对值起到了索引的作用,方便查找。Set/mulitiset容器 Map/multimap容器,并且容器是可以嵌套使用的。
算法
algorithom头文件中的定义相关的操作的一系列的函数模板
STL收录的算法经过了数学上的效能分析与证明,且是经过商业运行考验过的,是极具复用价值 的,包括常用的排序,查找等。
算法又可为为两种,质变算法,与非质变算法。
何为质变算法:是指运算过程中会更改区间内的元素的内容。例如:拷贝,替换,删除等。
何为非质变算法:是指运算过程中不会更改区间内的元素内容,例如:查找,计数,遍历,寻找极值等。
迭代器
迭代器的设计思维-STL 的关键所在,STL 的中心思想在于将容器(container)和算法(algorithms)分开,彼此独立设计,最后再一贴胶着剂将他们撮合在一起。从技术角度来看,容器和算法的泛型化并不困难,c++的 class template 和 functiontemplate 可分别达到目标,如果设计出两这个之间的良好的胶着剂,才是大难题
提供一种方法,使之能够依序寻访某个容器所含的各个元素,而又无需暴露该容器的内部表示方式,迭代器就被发明了出来。
函数符
在STL中主要用来为泛型算法提供策略。
有四种形式:全局函数指针,成员函数指针,仿函数(函数对象),与匿名函数Lambda表达式。
空间配置器
作用:主是用来解决内存碎片化问题的,以及过多的构造无用对象的问题。
容器的空间配置器的作用是把对象的内存开辟和构造过程分开,对象析构和内存释放分离开 。那为什么要把对象的内存开辟和构造(new的两个作用)分开,对象的析构和内存释放(delete的两个作用)分开呢?
1)因为在使用容器的过程中,构造一个容器,我们只想要容器的内存空间,并不需要给我们在内存上构造一堆无用的对象出来(直接用new没有办法避免这个问题);当从容器中删除一个元素的时候,我们需要析构这个被删除对象,但是它占用的容器内存空间是不能释放的,因为容器还要使用;再比如我们需要释放一个容器的时候,需要先把容器里面有效对象元素析构一遍,而不是把容器所有元素都析构一遍(用delete无法避免这个问题),所以在操作容器的过程中,我们需要有选择性的分别去开辟内存,构造对象,析构对象,所以这就是空间配置器存在的意义。
C++ 标准STL里面提供的allocator空间配置器,默认的内存分配和释放就是依赖malloc和free实现的。SGI STL提供了两个版本的空间配置器,一级空间配置器和二级空间配置器。一级空间配置器的内存管理也是通过malloc和free实现的,但是SGI STL的二级空间配置器提供了一个内存池的实现。第二级配置器的设计思想为:
1.如果配置区块超过128 bytes,则移交给第一级配置器处理(空间配置器);
2.如果配置区块小于128 bytes,则采用内存池管理(memory pool)。每次配置一大块内存,则维护对应的自由链表(free-list),下次若再有相同大小的内存需求,就直接从 free-list 中拨出(没有就继续配置内存,具体后面讲述),如果客端释换小额区块,就有配置器回收到 free-list 中。
对于SGI STL的二级空间配置器的内存池实现机制,还是非常重要的,因为这既涉及了空间配置器,又涉及了一个内存池的实现机制,因此大家需要好好的理解它的原理,大家在手写C++空间配置器的过程中,使用过nginx的内存池作为空间配置器的内存管理方案,这又是一个新的积累。
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;//已经开辟好的空间 cout << str2.max_size() << endl;//最大容量 //string 容量对象保存字符时,如果是小字符串(小于23个字节),会在栈上开辟空间 //如果是大对象(大于23个字节),会在堆上开辟空间 //查看动态开辟空间策略(2倍扩容) // string str_test; // cout << str_test.capacity() << endl; // for(int i=0;i<1024;i++){ // cout << "string容器对象中的有效元素个数:" << str_test.size() << // ",string容器对象中的容量大小:" << str_test.capacity() << endl;//采取2倍扩容机制 // 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数组容器的区别
vector与array无乎是一样的,连续的存储结构,两者的唯一的区别在于在空间上的灵活,数组需要提前指定长度,不量确定了就不能发生改变了,比较死板,不够灵活。比如出现拷贝长度大于了给定的空间,需要再重新定义一个足够空间的大小,然后把旧空间的内容再一个个拷贝到新的空间,非常麻烦。
c++11引入array主要是用来描述一种支持迭代器的C风格数组的,所以数组怎么用,array就怎么用,他定义在栈上,且长度固定不会涉及动态内存的开辟所以没有push_back,pop_back的相关方法,但是Vector这种动态的数组在开发更为常用,他底层对象在堆上,且长度是可变的。
vector容器是动态空间,他随着元素的加入,它的内部机制会自动扩充空间以容纳新的元素。vector的运用对于内存的合理利用与运用的灵活性有很大的帮助。我们再也不必害怕空间不足而一开始就定义一个巨大的数组了。
实现分析:
空间分配策略
#include <iostream> #include <vector> using namespace std; int main() { //动态扩容的策略(没内容不先开辟空间,不同于string) vector<int> v; for(int i=0;i<100;i++){ cout << "vector容器对象中的有效元素个数:" << 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; }
泛型算法
泛型算法 = 函数模板 + 迭代器范围(注意迭代器的类型) + 函数符(策略使用)
#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 << "----------------使用泛型算法进行遍历-------------" << endl; for_each(v.begin(),v.end(),[](int val){cout << val << "-";}); cout << endl; //针对于容器中有迭代器的容器for_each算法,提供了一种变种:枚举for循环 for(int val:v){//val默认为第0个元素,一次遍历,直到结束为止 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表达式作为算法策略 sort(v.begin(),v.end(),[](int val1,int val2){return val1>val2;});//一直判断到最后 //如果val1>val2为真,就把val1排好序,可以把函数符想象成一个抽象(必须这么理解,因为具体排序要看sort实现了),不是算法的具体实现,算法知道意思,就是降序了 for(int k:v){ cout << k << " "; } cout << endl; cout << "----------------------3--------------------" << endl; //使用函数对象 sort(v.begin(),v.end(),greater<int>());//这是调用库函数中的函数对象 for(int k:v){ cout << k << " "; } cout << endl; cout << "----------------------4--------------------" << endl; //定义一个函数指针,函数符来实现 sort(v.begin(),v.end(),&my_greate<int>);//这个就是全局函数指针,函数符实现 for(int k:v){ cout << k << " "; } cout << endl; //定义一个成员函数指针,函数符来实现 //因为成员函数指针依赖于对象的调用,所以不可以有直接做为策略使用,需要绑定器进行对象绑定才可以 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; //时间复杂度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(绑定第一个参数)&&bind2nd(绑定第二个参数)&&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对容器中的值没有要求,时间复杂度O(n),顺序遍历一遍,和二分查找不一样,时间复杂度不同 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按条件查找,需要把一个2这个值按序插入到序列中 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; //实现一个自定的空间配置器 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.构造对象 void constructor(T* p,const T& obj){ //定位new new (p) T(obj); } //3.析构对象 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; } //拷贝构造 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; } //等号运算符重载 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倍扩容 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: //与标准库中的泛型算法匹配类型 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; } //迭代器功能:++运算,!=运算 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; } // !=运算符重载: 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; }
容器适配置
容器适配器是没有迭代器的,不能实现泛型算法
使用deque
容器实现一个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; }
实现一个单端队列
#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; }
优先队列
#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);//快排,但系统中采取的是大顶堆,原因快排,递归过多 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特性是:所有元素都会根据元素的键值自动被排序。(set 与 map都会按照键值来自动排序,只不过set的键与值是一体的相同的)Set的元素不像map那样,可以同时拥有实值与键值,set的元素即是键值又是实值。(你也可以理解为只有一个值,键与值相同)Set不允许两个元素有相同的键值。(即然是自动排序,set与map是不允许有相同的键的存在。这一点与map是共同的。),而multiset是可以存相同键值的元素。(这是set与multiset的唯一区别。)。
所以set容器的迭代器是一个常双向迭代器,只支持什么:++,–,==,!=的操作。
我们可以通过set的迭代器改变set元素的值吗?不行,因为set元素值就是其键值,关系到set元素排序规则,如果任意改变set元素值,会严重破坏set组织结构。换句话说,set的迭代器是一个只读迭代器。
set容器拥有与list某些相同的性质,当对容器中的元素进行插入操作或者删除操作的时候,操作之前所有迭代器,在操作完成之后依
multiset的底层实现是红黑树,红黑树是平衡二叉树的一种。二叉树的相关知识点可以百度一下。
#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;//调用库中的<预算符重载函数 // 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 << "学号:" << 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;//调用库中的<预算符重载函数 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 << "王五子入学成功!" << endl; // }else{ // cout << " 王五子入学失败!" << "\n"; // } for(const Stu& stu:s1){ stu.showInfo(); } return 0; }
map容器
对组pair构建方式:
#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容器的特性是:所有元素都会根据元素的键的值自动排序。Map所有的元素都是统一的pair对组,同时拥有键值Key实值Value,pair的第一元素被视为键值,第二个元素被视为实值,map不允许两个元素有相同的键。
我们可以通过map迭代器改变map的键值吗?答案是不行,因为map的键值关系到map的元素的排列布局,Map中的键是不可修改的,但是键对应的值是可以修改的。
所以Map的迭代器是一个双向迭代器,只支持++ == !=操作。
Map是可以随时插入或删除键值对的。
Map与multimap的唯一区别是multimap中的键是可以重复的。
Map的底层实现机制是由二叉树中的红黑树进行实现的。
#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中是没有【】中括号运算符的:
map中的[]注意事项:
map中的[]运算符具有两个作用:
1.就是可以在map容器直接插入一个键值对。
2.当map容器有同名的key时,使用[]也可修饰key对应的value的值。
3.注意:在multimap中是没有[]中括号运算符的。
4.中括号运算符如果map没有这个键时,将会自动插入这个键值对。
观察者设计模型
引言
用来解决两个不相关对象之间的一对一或者一对多的通信模型。
什么是观察者设计模式
观察者模式是一种对象行为模式。它定义对象间的一种一对多的依赖关系, 当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。在观察者模式中,主体是通知的发布者,它发出通知时并不需要知道谁是它的观察者,可以有任意数目的观察者订阅并接受通知。观察者模式不仅被广泛应用于软件界面元素之间的交互,在业务对象之间的交互、权限管理等方面也有广泛的应用。
解决的问题
定义了对象间的一种一对多的组合关系,以便一个对象的状态发生时,所有依赖于它的对象都得到通知并自动刷新。
观察者和被观察者之间存在“观察”的逻辑关系,当被观察者发生变化时,观察者就会观察到这样的变化,并作出相应的响应。
编程思路
设定两者类,一个为观察者类,一个为被观察者类
观察者类中,定义一个对某个事件感兴趣的处理函数,一般也叫做槽函数
被观察者类中,定义一个数据结构,用来保存观察者对某一个事件id(信号)感兴趣,使用数据结构建立信号与对象之间的映射关系
被观察者类中,定义两个方法函数:
一个方法为:添加观察者与其感兴趣的事件id(信号)加入到容器中
另一个方法为:信号函数:通知事件函数执行逻辑:首先遍历容器中,有没有感兴趣的事件ID,如果有,则代表一系列的观察者,对这个事件感兴趣,那么再次遍历观察者列表,让每一个观察者执行相应的槽函数
#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信号,执行信号1对应槽函数逻辑" << endl; break; case 2: cout << "接收到2信号,执行信号2对应槽函数逻辑" << endl; break; case 3: cout << "接收到3信号,执行信号3对应槽函数逻辑" << endl; break; case 4: cout << "接收到4信号,执行信号4对应槽函数逻辑" << 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 << "接受到未知信号,没有信号对应的槽函数逻辑" << 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; }
加载全部内容