做头条信息流要网站吗,泌阳县住房建设局网站,市场营销四大基本内容,合肥营销型网站标准模板库STL的组成
主要由六大基本组件组成#xff1a;容器、迭代器、算法、适配器、函数对象(仿函数)以及空间配置器。
容器#xff1a;就是用来存数据的#xff0c;也称为数据结构。 本文要详述的是容器主要如下#xff1a; 序列式容器#xff1a;vector、list 关联…标准模板库STL的组成
主要由六大基本组件组成容器、迭代器、算法、适配器、函数对象(仿函数)以及空间配置器。
容器就是用来存数据的也称为数据结构。 本文要详述的是容器主要如下 序列式容器vector、list 关联式容器set、map 无序关联式容器unordered_set、unordered_map 迭代器行为类似于指针具有指针的功能我们使用迭代器来连接容器与算法。
算法就是用来操作数据的。
适配器因为STL中的算法的实现不是针对于具体容器的所以可能有些算法并不适合用于具体的容器需要使用适配器进行适配或者转接。 包含容器的适配器、迭代器的适配器、算法的适配器。 函数对象(仿函数)函数对象就是通过重载小括号运算符对象的在STL中用来做定制化操作的。
空间配置器用来进行空间的申请与释放的。
容器
序列式容器
序列式容器总共有下面五种 这里只讲vector、deque与list。
原因很简单array是静态数组forward_list是单向链表而vector是动态数组、list是双向(循环)链表谁又还会去用静态数组和单向链表呢而deque是双端队列是比较常用的数据结构所以自然也是需要学习的。
序列式容器的模板参数类型
template
class T,
class Allocator std::allocatorTclass vector;template
class T,
class Allocator std::allocatorTclass deque;template
class T,
class Allocator std::allocatorTclass list;可以看见第一个参数T是我们所要存放入模板的参数Allocator是空间配置器其具有一个默认参数为std::allocatorT因此我们使用序列式容器的时候不需要传入空间配置器而只需要传入我们要存放的数据。
序列式容器常用的初始化与遍历方式示例
#include cstddef
#include iostream
#include list
#include vector
#include dequeusing namespace std;void test(){//序列式容器的初始化与遍历操作都基本一样主要有下面几种形式//以vector为例deque操作与vector是一样的就不再赘述//list与vector只有一处不同就是list无法使用下标进行遍历这一点要格外注意//常用的初始化方法//1、无参初始化vectorint number;//2、指定容器大小初始化//2.1、指定初始化的内容//第一个参数表示容器要初始化的大小第二个参数表示要初始化的值//即下面的number是初始化了 10 个 4即传count个valuevectorint number(10,4);//2.2、不指定初始化的内容则容器默认内容存储为0//即下面的number是初始化了10个0元素vectorint number(10);//3、使用迭代器范围进行初始化(范围是左闭右开)int arr[10] {1,2,4,3,6,3,8,9,10,5};vectorint number(arr,arr10);//4、使用初始化列表的形式进行初始化vectorint number {1,2,3,4,5,6,7,8,9,10};//常用的遍历方法//1、使用for循环for(size_t idx0;idx!number.size();idx){cout number[idx] ;}cout endl;//2、使用迭代器vectorint::iterator it;for(itnumber.begin();it!number.end();it){cout *it ;}cout endl;//3、使用加强的for循环for(auto elem : number){cout elem ;}cout endl;
}int main(){test();return 0;
}
对于上面代码中的迭代器遍历方式下面有个图示可能看了会有助于理解begin()与end()的工作机制 这是一个比较简单和基本的概念begin和end其实就是两个指针begin指向容器的首部而end指向容器尾部的下一个为空的元素而迭代器iterator也是一个指针因此可以通过这三个指针的组合来完成容器遍历就和学习链表时遍历链表的操作一样只不过STL这里进行了封装而已不再赘述。
另外注意list无法使用下标访问元素切记。
序列式容器常用的头尾位置插入与删除方式示例
#include iostream
#include vector
#include deque
#include listusing namespace std;//模板打印函数
template typename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}//从尾部插入与删除三者是一样的
void test(){//序列式容器从尾部插入与删除操作是一样的主要有下面两个方式//push_back()和pop_back()//这里依然只以vector为例deque与list和vector是一样的就不再赘述vectorint number {1,3,5,7,9,10};display(number);//在vector尾部进行插入number.push_back(100);number.push_back(200);display(number);//在vector尾部进行删除number.pop_back();display(number);}//从头部插入和删除只有list和deque是一样的vector没有这种方式
//为什么呢
//因为插入与删除第一个元素的这种操作对于vector而言其都会进行一个
//将后面的元素进行挪动的操作(跟数组一样)时间复杂度过高(o(N))所以不予实现
void test1(){//因为list和deque的方式一样这里依然是只以list为例//两个方法: push_front()和pop_front()listint number {1,2,3,4,5};//从头部插入number.push_front(20);number.push_front(50);display(number);//从头部删除number.pop_front();display(number);
}int main(){test();return 0;
}
对于插入删除操作只需要注意vector的特殊性vector不提供头部删除与插入的操作原因是复杂度过高。
序列式容器常用的中间位置插入与删除方式示例
#include iostream
#include list
#include vectorusing namespace std;templatetypename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}//对于中间位置插入三个序列式容器都是可以做到的
//但是注意时间复杂度的问题list毫无疑问是最快的因为是双向链表
//这里只以list为例进行示例insert方法三个序列式容器都是一样的操作
void test(){//list的中间插入操作示例//常用方法如下listint number {1,2,34,3,8,56,89};auto cit number.begin();cit;cit;//1、指定位置进行插入number.insert(cit,300);display(number);//2、指定位置插入count个value元素//下面这句代码的意思是在cit的位置出开始插入3个值为200的元素number.insert(cit,3,200);display(number);//3、指定位置按其它容器的迭代器范围进行元素插入vectorint num {2,3,4,5};number.insert(cit,num.begin(),num.end());display(number);//删除操作//使用erase()函数传入参数为迭代器for(auto it number.begin(); it!number.end();it){if(2 *it){//erase函数要注意迭代器失效的问题嗷//具体参见本文下文迭代器失效问题it number.erase(it);}}display(number);
} int main(){test();return 0;
}
序列式容器常用的一些其它操作
注意这里只是提了一些比较常见的操作还有更多的操作随用随查即可嗷。
#include iostream
#include list
#include vectorusing namespace std;templatetypename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}//这里要注意对于deque而言其没有capacity()函数
//但其具有shrink_to_fit函数
//对于list来说其没有capacity()函数也没有shrink_to_fit()函数
void test(){//容器元素的清空vectorint number {1,2,34,3,8,56,89};cout number.size number.size() endl;cout number.capacity number.capacity() endl;display(number);//使用clear函数可以清空元素但要注意其容量不会被重置//清除前是多大清除后依然是多大number.clear();cout number.size number.size() endl;cout number.capacity number.capacity() endl;display(number);//如果想要将容量也一并清除//即缩减掉所有未使用的内存的话可以使用shrink_to_fit()函数number.shrink_to_fit();cout number.size number.size() endl;cout number.capacity number.capacity() endl;display(number);
} int main(){test();return 0;
}
vector底层原理
通过阅读vector的底层源码我们不难发现vector的继承体系如下 vector保护继承自_Vector_base_Vector_base公有继承自_Vector_alloc_base在最上层的基类_Vector_alloc_base中有三个指针类型的数据成员_Tp* _M_start_Tp* _M_finish和_Tp* _M_end_of_storage;
三个指针的作用图示如下
还是比较好理解的吧_M_start指向头部_M_finish指向实际存储元素的下一个空元素而_M_end_of_storage则是控制整个vector容量的指针永远指向vector容量最大位置的末端地址。
我们所使用的vector的各种函数其实都是由这三个指针实现的如 经典面试题: vector中的at函数与下标访问运算符函数有什么区别
这里有一个经典的面试题在vector提供的函数中有下面两个作用相同的函数
也就是at函数和operator[]函数二者的作用都是随机获取vector中的值那么二者的区别是什么呢 通过上面两幅图的源码显示我们可以看到at函数在返回结果之前先调用了一个_M_range_check(__n)的函数我们来看一下该函数的源码 不难发现其做了一个越界检查如果超出了vector的最大长度则会抛出异常。 因此二者的区别是at函数可以进行范围的检查比operator[]函数更加安全。 vector的push_back函数探究 源码如上可以看见其逻辑还是比较简单的如果vector没满那么就往里面存内容如果满了的话就进行扩容即可扩容操作在_M_insert_aux()函数中 上面只是源码的一部分从划红线位置可以看出vector底层扩容时确实是按照两倍的标准进行的。
迭代器失效问题的典型vector迭代器失效
由前文可知vector在遇到空间大小不够时会自动进行扩容操作其步骤就算不看源码我们也能猜出一二大致如下 1、检查容量当向 std::vector 添加元素时它首先检查当前容量是否足够。如果当前容量不足以容纳新元素则进行下一步。 2、计算新容量std::vector 不会仅仅为了添加一个新元素而重新分配内存。相反它会预估在未来添加更多元素时需要的容量。3、默认情况下每次扩容时新容量是旧容量的2倍这个比例可以在创建 std::vector 时通过第二个参数进行定制。 4、分配新内存使用计算出的新容量std::vector 会分配一块新的内存区域。 5、复制元素std::vector 会将旧数组中的所有元素复制到新数组中。 6、添加新元素在新数组的末尾添加新元素。 7、释放旧内存旧数组的内存被释放。 8、更新 std::vector 的大小std::vector 的大小size 成员增加一个以反映新添加的元素。 同时我们知道vector容器的迭代器就是指针类型那么vector在扩容时其内存地址发生该变是不是意味着原来的迭代器指针就会失效呢
来看下面的代码示例; 运行结果如下 不难看出因为我们是迭代器指针cit本来指向的是元素34一开始vector的大小和容量都为7因为初始化时总共七个元素在32位置插入300之后我们可以看到number的capacity容量值发生了扩容并且清晰的是2倍扩容此时就意味着vector容器的内存地址发生了改变因为内存是被重新分配了的那么原先旧版number容器的迭代器自然也就失效了此时再使用该迭代器去继续迭代崭新的容器元素必然出现错误这也就是为什么上述运行结果出现乱码且出现了core dumped的原因。
解决办法很简单使用insert方法返回的新容器的迭代器即可 运行结果如下 此时不再发生迭代器失效问题除了上述方法之外还可以对cit迭代器重新赋值也是可以的
cit number.begin();同理vector在删除元素时也会发生迭代器失效的情况其原因是在我们删除如中间某一个元素的时候vector底层实现不允许其中间具有空值(因为vector是连续存储的)所以在缺少元素时vector会进行一个元素移动的操作这同样会引发迭代器失效而出现意料之外的情况解决办法相同测试用例如下程序目的为删除number容器中所有的 6 运行结果如下 上图中第一次运行为异常情况(即迭代器失效的情况)第二次运行为解决了迭代器失效问题的运行结果分析就不再赘述自己画图分析一目了然。
另外除了vector容器需要考虑迭代器失效以外其它序列式容器如list和deque一样需要考虑在插入删除操作时迭代器失效的情况很常见一种最佳实践是每次进行插入删除操作时都按时更新新的迭代器从而避免迭代器失效的情况。
vector动态扩容的底层原理
对于insert函数插入元素时其扩容方式为设size() tcapacity() n插入的元素个数为m则有如下关系式 1、m n - t此时不需要扩容 2、n - t m t 此时是 2 * t 进行扩容操作 3、n - t mt m n此时是 t m 进行扩容操作 4、n - t mm n此时是 t m 进行扩容操作。 因为push_back每次插入的元素的个数是一个所以按照两倍的扩容方式是没有问题的。 而insert每次插入的元素个数是不确定的所以扩容方式也是不固定的因此insert扩容会麻烦一些。
deque底层原理
通过分析源码我们可以得出deque的继承体系如下 顶层基类_Deque_alloc_base有两个数据成员_M_map和_M_map_size
deque的迭代器详解
派生类_Deque_base类有两个数据成员_M_start和_M_finish也就是一个指向队头一个指向队尾值得注意的点是这两个数据成员的类型为iterator迭代器之前我们说过iterator都可以抽象的理解为指向容器存储位置的指针但这并不意味着所有容器的迭代器的实现都是通过指针实现的上文的vector的迭代器是指针实现的而deque容器的迭代器则是一个类(_Deque_iterator_Tp,_Tp,_Tp* iterator)被typedef后实现的在该类内部实现了iterator的类指针操作。
_Deque_iterator类的源码实现部分如下 可以看出该类内部实现了iterator的各个函数重载如运算符、-运算符等等让deque的迭代器抽象成了一个类似指针的东西。 因此之前说迭代器是一种指针这只是广义上的说法我们并不能断定说容器的iterator就是一个指针这样的说法是错误的。 比如deque容器的迭代器实现就是通过一个类typedef之后重定义而成的。 _M_map中控器
deque作为双端队列直觉上给人的感觉似乎就是一个两端开口存储连续的数据结构如下 但实际上其底层实现并非如此直观deque使用了_M_map中控器的数据结构 从上图可以看到中控器的每个位置都指向了一小块内存片段在每一小块内部数据是连续存放的小块与小块之间是并不连续的。 所以千万注意deque逻辑上是连续的但实际物理存储上是分散的非连续的嗷 这个中控器就是基类_Deque_alloc_base的主要内容然后派生类_Deque_base公有继承自基类_Deque_alloc_base拿到这个中控器其有两个数据成员_M_start和_M_finish来操作该中控器对于这两个数据成员其类型都为迭代器类型从前文可以知道每个迭代器类型都具有四个指针_M_cur、_M_first、_M_last、_M_node
_M_start的原理分析 _M_start会指向中控器的第一个内存片段然后其内部的四个指针会做如下操作 _M_first会指向该片段的第一个可以存放元素的位置可能为空 _M_cur会指向该内存片段中的真正存储的第一个元素也就是整个deque的第一个元素 _M_last会指向该片段的最后一个元素的下一个空元素的位置 _M_node表示一个节点。 _M_finish的原理分析 同理_M_finish会指向中控器的最后一个内存片段其余指针效果同前。
总结 deque是由多个小内存片段组成的每个小片段内部是连续的但是片段与片段之间不是连续的每个小片段靠中控器数组进行管理当元素过多之后会重新申请新的片段如果片段过多之后可能会扩大中控器数组的大小。 list容器的一些特殊操作
#include functional
#include iostream
#include list
#include vectorusing namespace std;templatetypename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}//自定义的排序方式
struct Com{bool operator()(const int lhs,const int rhs) const{return lhs rhs;}
};void test(){//list的一些特殊操作这些是vector和deque所不具有的listint number {1,3,4,6,7,98,8,3,3,8};display(number);cout 链表的逆置 endl;number.reverse();display(number);cout 链表的排序 endl;//默认从小到大排序可以传入比较参数来重新定义排序//number.sort();//number.sort(greater());//从大到小进行排序//也可以自定义,写成普通类或者模板类的形式都是可以的number.sort(Com());display(number);cout 链表的去重,注意只是去重连续重复的值 endl;number.unique();display(number);cout 链表的合并 endl;//如果两个链表本身是有序的那么合并之后也依然会有序listint lst1 {1,3,7,9,4};listint lst2 {8,30,70,90,40};lst1.sort();lst2.sort();lst1.merge(lst2);display(lst1);display(lst2);//lst2为空相当于将lst2的内容move到了lst1中cout 链表的splice()的使用 endl;listint lst3 {1,4,7,9,3};listint lst4 {5,8,10,20,2};auto cit lst3.begin();cout *cit *cit endl;//将整个lst4存进lst3中的cit位置//lst3.splice(cit,lst4); 此时lst4也为空了嗷相当于move//将lst4中的it所指向的位置的元素存进lst3中的cit位置处//注意这个操作也可以自己对自己使用如lst3.splice(cit,lst3,it);//效果相当于移动自己所存储的元素到其它位置auto it lst4.end();--it;cout *it *it endl;lst3.splice(cit,lst4,it);display(lst3);display(lst4);//lst4中的it所指向的值就没有了但其它元素还在} int main(){test();return 0;
}
关联式容器
set 与 multiset
首先第一点要注意的就是set 和 multiset 都位于同一个头文件 set中
set 的模板参数类型
templateclass Key,class Compare std::lessKey,class Allocator std::allocatorKeyclass set;可以看到有三个值key值不用多说是我们要传入的数据而Compare类型参数是我们用来定义排序的比较方式默认是从小到大升序若想从大到小可以使用 std::greater 另外我们也可以自定义这个比较类然后传入即可。第三个值是空间配置器这个在后面会进行详述。
set 的基本CRUD操作
#include iostream
#include ostream
#include set
#include vectorusing namespace std;//打印函数
templatetypename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}void test(){//set 的初始化//set的特点//1、key值是唯一的不能重复//2、默认情况下会按照key值进行升序排列//3、底层使用的数据结构是红黑树setint number {1,3,5,2,3,5,7,9,4,5};display(number);//set 的查找操作//常用的是count和findsize_t cnt1 number.count(3);size_t cnt2 number.count(10);cout cnt1 cnt1 cnt2 cnt2 endl;auto it number.find(5);if(it ! number.end()){cout *it *it endl;}else{cout 查找失败 endl;}//set的插入操作//auto it2 number.insert(8); 使用auto可以简化我们的代码形式//但set 的insert 操作返回的是 一个 pair 类型的值pairsetint::iterator,bool ret number.insert(8);if(ret.second){cout 该元素插入成功 *ret.first endl;}else{cout 插入失败 endl;}//插入迭代器范围的方式进行插入vectorint vec {10,3,6,20,50};number.insert(vec.begin(),vec.end());display(number);//插入大括号表达式进行插入也是可以的number.insert({1,0,100,200});display(number);//set 的删除number.erase(10);display(number);//set 的下标访问 //cout number[10] number[0] endl; error,set不支持下标访问嗷//set的修改操作auto it3 number.begin();cout *it3 *it3 endl;//*it3 200; error set是不支持修改的
}class Comparation;//自定义类型point
class Point{friend Comparation;public:Point(int ix 0, int iy 0):_ix(ix),_iy(iy){cout Point() endl;}//重写小于运算符函数friend bool operator(const Point lhs,const Point rhs);~Point(){cout ~Point() endl;}friend ostream operator(ostream os,const Point rhs);private:int _ix;int _iy;
};ostream operator(ostream os,const Point rhs){os ( rhs._ix , rhs._iy ) endl;return os;
}bool operator(const Point lhs,const Point rhs){//定义小于比较的逻辑随便定义set会根据这个逻辑来进行排序if(lhs._ix rhs._ix){return true;}else{return false;}
}//比较器的类重载函数调用运算符即可
struct Comparation{bool operator()(const Point lhs,const Point rhs){if(lhs._ix rhs._ix){return true;}else{return false;}}
};//set存储自定义类型的情况
void test2(){setPoint number {Point(1,2),Point(1,-2),Point(-1,-2),Point(4,5)};display(number);//此时进行打印会报错因为set容器是会自动进行排序的//而我们的Point类里面并没有实现对应的比较函数//实现了之后输出才是正确的//另一种方式是手写一个比较类然后在其内部重载函数调用运算符即可//然后把该类当成set模板参数列表的第二个比较器参数传入setPoint,Comparation number2 {Point(1,2),Point(1,-2),Point(-1,-2),Point(4,5)};display(number2);
}int main(){test2();return 0;
}
对于set 的使用要注意当存储的元素类型为自定义类型的情况。
重载大于符号或者小于符号等价实现 std::less 或者 std::greater。
multiset 的CRUD操作
#include iostream
#include ostream
#include set
#include vectorusing namespace std;//打印函数
templatetypename Container
void display(Container con){for(auto elem : con){cout elem ;}cout endl;
}void test(){//multiset 的初始化//multiset的特点//1、key值是不唯一的可以重复//2、默认情况下会按照key值进行升序排列//3、底层使用的数据结构是红黑树multisetint number {1,3,5,2,3,5,7,9,4,5};display(number);//multiset 的查找操作//常用的是count和find//count会计数传入参数在multiset容器中出现的次数size_t cnt1 number.count(3);size_t cnt2 number.count(10);cout cnt1 cnt1 cnt2 cnt2 endl;auto it number.find(5);if(it ! number.end()){cout *it *it endl;}else{cout 查找失败 endl;}//测试multiset的xxx_bound()函数//lower_bound()会返回第一个大于等于所给定的key值的迭代器//upper_bound()会返回第一个大于所给定的key值的迭代器auto itt1 number.lower_bound(5);cout *itt1 *itt1 endl;auto itt2 number.upper_bound(5);cout *itt2 *itt2 endl;//测试multiset的euqal_range()函数//该函数返回的是pair类型的两个迭代器指针用来表示一个范围//该范围内就全是所给定的key的值auto ret2 number.equal_range(5);while(ret2.first ! ret2.second){cout *ret2.first ;ret2.first;}cout endl;//multiset的插入操作//auto it2 number.insert(8); 使用auto可以简化我们的代码形式//但multiset 的insert 操作返回的是 一个 iterator 类型的值//使用multiset时只管插入即可肯定是成功的不需要考虑返回值number.insert(8);display(number);//插入迭代器范围的方式进行插入vectorint vec {10,3,6,6,20,50};number.insert(vec.begin(),vec.end());display(number);//插入大括号表达式进行插入也是可以的number.insert({1,0,100,200});display(number);//multiset 的删除number.erase(10);display(number);//multiset 的下标访问 //cout number[10] number[0] endl; error,multiset不支持下标访问嗷//multiset的修改操作auto it3 number.begin();cout *it3 *it3 endl;//*it3 200; error multiset是不支持修改的
}class Comparation;//自定义类型point
class Point{friend Comparation;public:Point(int ix 0, int iy 0):_ix(ix),_iy(iy){cout Point() endl;}//重写小于运算符函数friend bool operator(const Point lhs,const Point rhs);~Point(){cout ~Point() endl;}friend ostream operator(ostream os,const Point rhs);private:int _ix;int _iy;
};ostream operator(ostream os,const Point rhs){os ( rhs._ix , rhs._iy ) endl;return os;
}bool operator(const Point lhs,const Point rhs){//定义小于比较的逻辑随便定义multiset会根据这个逻辑来进行排序if(lhs._ix rhs._ix){return true;}else{return false;}
}//比较器的类重载函数调用运算符即可
struct Comparation{bool operator()(const Point lhs,const Point rhs){if(lhs._ix rhs._ix){return true;}else{return false;}}
};//multiset存储自定义类型的情况
void test2(){multisetPoint number {Point(1,2),Point(1,-2),Point(-1,-2),Point(4,5)};display(number);//此时进行打印会报错因为multiset容器是会自动进行排序的//而我们的Point类里面并没有实现对应的比较函数//实现了之后输出才是正确的//另一种方式是手写一个比较类然后在其内部重载函数调用运算符即可//然后把该类当成multiset模板参数列表的第二个比较器参数传入multisetPoint,Comparation number2 {Point(1,2),Point(1,-2),Point(-1,-2),Point(4,5)};display(number2);
}int main(){test2();return 0;
}multiset注意一下count、upper_bound和lower_bound、insert以及equal_range等函数与set的区别对比学习即可。
map的基本CRUD操作
#include iostream
#include ostream
#include map
#include string
#include vectorusing namespace std;//打印函数
templatetypename Container
void display(Container con){for(auto elem : con){cout elem.first , elem.second endl;}cout endl;
}void test(){//map的初始化//map的特征// 1、存放的元素是一个pair类型key与value值key是唯一的不能重复// 但是value值重复与否是没有关系的// 2、默认情况下会按照key值进行升序排列// 3、底层实现是红黑树mapint,string number {{3,武汉},{5,上海},pairint,string(4,北京),pairint,string(5,天津),//也可以使用make_pair函数其返回类型是一个pairmake_pair(2,南京)};display(number);cout endl map的下标访问 endl;//使用下标访问当该下标key存在时访问就相当于查找对应key下标的value值cout number[2] number[2] endl;//若不存在则就相当于插入一个新的value值对应的key为下标cout number[1] number[1] endl;display(number);//同时如果对已经存在的key进行赋值的话就相当于修改操作number[1] 东京;display(number);
} class Point{
public:Point(int ix0,int iy0):_ix(ix),_iy(iy){cout Point() endl;}~Point(){cout ~Point() endl;}friend ostream operator(ostream os,const Point rhs);
private:int _ix;int _iy;
};ostream operator(ostream os,const Point rhs){os ( rhs._ix , rhs._iy ) endl;return os;
}//map的自定义类型存储时的特殊情况
void test2(){//注意并非每次出现自定义类型时都要去重写比较运算符//因为map是根据key来排序的如果key键为内置类型那么库是帮我们写好了比较运算符的//此时排序行为和我们的自定义类型都没有关系就不用在自定义类型中重写比较运算符//比如下面这种情况就不需要重写mapstring,Point number {{wuhan,Point()},pairstring,Point(nanjing,Point(1,2)),make_pair(dongjing,Point(2,3))};//map的查找操作//其count函数与find函数与之前序列式容器中的count与find效果一样//不再赘述size_t cnt1 number.count(wuhan);size_t cnt2 number.count(wuhan2);cout cnt1 cnt1 endl;cout cnt2 cnt2 endl;//map的插入操作//1、pairmapstring,Point::iterator,bool ret number.insert(pairstring,Point(hubei,Point(1,2)));//2、auto ret number.insert((make_pair(hubei2,Point(2,3))));auto ret number.insert({hubei2,Point(2,3)});if(ret.second){//因为first里面存的是指针数据所以要用-去引用其存储的pair类型数据cout 插入成功 ret.first-first ret.first-second endl;}else{cout 插入失败,该元素存在map中 endl;}display(number);//map的删除操作//对于map而言使用erase可以删除元素//erase两种重载形式传入迭代器删除 和 传入key值删除//因为更常用的是下标访问运算符的方式所以这里不再赘述erase函数的使用//cout的下标访问//如果下标运算符传入的key值存在则可以打印出其对应的valuecout number[\dongjing\] number[dongjing] endl;//如果下标运算符中传入的key值不存在那么对于自定义类型而言就直接调用无参构造cout number[\1\] number[1] endl;//如果下标运算符中传入的key值存在且赋予其新值那么就是修改number[1] Point(2,4);
}int main(){test();return 0;
}
multimap的CRUD操作
#include functional
#include iostream
#include ostream
#include map
#include string
#include vectorusing namespace std;//打印函数
templatetypename Container
void display(Container con){for(auto elem : con){cout elem.first , elem.second endl;}cout endl;
}void test(){//multimap的初始化//multimap的特征// 1、存放的元素是一个pair类型key与value值key是不唯一的可以重复// 但是value值重复与否是没有关系的// 2、默认情况下会按照key值进行升序排列// 3、底层实现是红黑树//multimapint,string number {//如果想实现降序排列那么需要将第三个模板参数传入multimapint,string,greaterint number {{3,武汉},{5,上海},pairint,string(4,北京),pairint,string(5,天津),//也可以使用make_pair函数其返回类型是一个pairmake_pair(2,南京)};display(number);
#if 0multimap不支持下标访问原因显而易见key值重复会产生二义性cout endl multimap的下标访问 endl;//使用下标访问当该下标key存在时访问就相当于查找对应key下标的value值cout number[2] number[2] endl;//若不存在则就相当于插入一个新的value值对应的key为下标cout number[1] number[1] endl;display(number);//同时如果对已经存在的key进行赋值的话就相当于修改操作number[1] 东京;display(number);
#endif
} class Point{
public:Point(int ix0,int iy0):_ix(ix),_iy(iy){cout Point() endl;}~Point(){cout ~Point() endl;}friend ostream operator(ostream os,const Point rhs);
private:int _ix;int _iy;
};ostream operator(ostream os,const Point rhs){os ( rhs._ix , rhs._iy ) endl;return os;
}//multimap的自定义类型存储时的特殊情况
void test2(){//注意并非每次出现自定义类型时都要去重写比较运算符//因为multimap是根据key来排序的如果key键为内置类型那么库是帮我们写好了比较运算符的//此时排序行为和我们的自定义类型都没有关系就不用在自定义类型中重写比较运算符//比如下面这种情况就不需要重写multimapstring,Point number {{wuhan,Point()},pairstring,Point(nanjing,Point(1,2)),make_pair(dongjing,Point(2,3))};//multimap的查找操作//其count函数与find函数与之前序列式容器中的count与find效果一样//不再赘述size_t cnt1 number.count(wuhan);size_t cnt2 number.count(wuhan2);cout cnt1 cnt1 endl;cout cnt2 cnt2 endl;//multimap的插入操作//1、number.insert(pairstring,Point(hubei,Point(1,2)));//2、auto ret number.insert((make_pair(hubei2,Point(2,3))));number.insert({hubei2,Point(2,3)});
#if 0因为multimap的insert方法返回的并非是pair类型的值所以无法使用下面注释的这一段内容来打印if(ret.second){//因为first里面存的是指针数据所以要用-去引用其存储的pair类型数据cout 插入成功 ret.first-first ret.first-second endl;}else{cout 插入失败,该元素存在multimap中 endl;}
#endifdisplay(number);//multimap的删除操作//对于multimap而言使用erase可以删除元素//erase两种重载形式传入迭代器删除 和 传入key值删除//因为更常用的是下标访问运算符的方式所以这里不再赘述erase函数的使用
#if 0因为multimap的insert方法返回的并非是pair类型的值所以无法使用下面注释的这一段内容来打印//cout的下标访问//如果下标运算符传入的key值存在则可以打印出其对应的valuecout number[\dongjing\] number[dongjing] endl;//如果下标运算符中传入的key值不存在那么对于自定义类型而言就直接调用无参构造cout number[\1\] number[1] endl;//如果下标运算符中传入的key值存在且赋予其新值那么就是修改number[1] Point(2,4);
#endif
}int main(){test();return 0;
}
无序关联式容器
无序关联式容器的底层实现使用的是哈希表关于哈希表有几个概念需要了解哈希函数、哈希冲突、 解决哈希冲突的方法、装载因子(装填因子、负载因子)
1、哈希函数
是一种根据关键码key去寻找值的数据映射的结构即根据key值找到key对应的存储位置。
2、哈希函数的类型
1、直接定址法 H(key) a * key b 2、平方取中法 key^2 1234^2 1522756 ------227 3、数字分析法H(key) key % 10000 4、除留取余法H(key) key mod p (p m, m为表长)
3、哈希冲突
就是对于不一样的key值可能得到相同的地址,即:H(key1) H(key2)。
4、解决哈希冲突的方法
1、开放定址法 2、链地址法 (推荐使用这种这也是STL中使用的方法) 3、再散列法 4、建立公共溢出区
5、装载因子
装载因子 a (实际装载数据的长度n)/(表长m) a越大哈希表填满时所容纳的元素越多空闲位置越少好处是提高了空间利用率但是增加了哈希碰 撞的风险降低了哈希表的性能所以平均查找长度也就越长但是a越小虽然冲突发生的概率急剧下 降但是因为很多都没有存数据空间的浪费比较大经过测试装载因子的大小在[0.5~0.75]之间比 较合理特别是0.75。
6、哈希表的设计思想
用空间换时间注意数组本身就是一个完美的哈希所有元素都有存储位置没有冲突空间利用率也 达到极致。
7、四种无序关联式容器
(unordered_set、unordered_multiset、unordered_map、unordered_multimap)底层实现使用哈 希表。针对于自定义类型需要自己定义std::hash函数与std::equal_to函数四种容器的类模板如下
//unordered_set与unordered_multiset位于#include unordered_set中
template class Key,class Hash std::hashKey,class KeyEqual std::equal_toKey,class Allocator std::allocatorKeyclass unordered_set;template class Key,class Hash std::hashKey,class KeyEqual std::equal_toKey,class Allocator std::allocatorKeyclass unordered_multiset;//unordered_map与unordered_multimap位于#include unordered_map中
template class Key,class T,class Hash std::hashKey,class KeyEqual std::equal_toKey,class Allocator std::allocator std::pairconst Key, T class unordered_map;template class Key,class T,class Hash std::hashKey,class KeyEqual std::equal_toKey,class Allocator std::allocator std::pairconst Key, T class unordered_multimap;针对内置类型初始化、遍历、查找、插入、删除、修改、下标访问这些与关联式容器类似无序关联 式容器中元素没有顺序底层采用的是哈希表。特别是对于自定义类型而言没有针对key值对应的哈 希函数以及比较函数所以需要自己写。
无序关联式容器unordered_set的示例
#include iostream
#include ostream
#include unordered_setusing namespace std;templatetypename Container
void display(const Container con){for(auto elem : con){cout elem ;}cout endl;
}void test(){//unordered_set 的特征//1、key值是唯一不能重复//2、key值是没有顺序的//3、底层使用的是哈希//因为容器的基本使用都是差不多的所以这里不再赘述和set基本一致//只有下面测试函数test2中的哈希和比较函数的一点不同其它基本一致unordered_setint number {1,3,5,7,9,6,4,2,3,1,3};display(number);
}//自定义数据类型
class Point{
public:Point(int ix 0,int iy 0):_ix(ix),_iy(iy){cout Point() endl;}~Point(){cout ~Point() endl;}friend ostream operator(ostream os,const Point rhs);friend class HashPoint;friend bool operator(const Point lhs,const Point rhs);
private:int _ix;int _iy;
};ostream operator(ostream os,const Point rhs){os ( rhs._ix , rhs._iy ) endl;return os;
}//哈希函数的实现函数对象的形式
struct HashPoint{size_t operator()(const Point rhs)const {cout HashPoint endl;return (rhs._ix 1)^(rhs._iy 2);}
};//标准命名空间std中的类模板hash的全特化版本std::hash
namespace std{ //这是标准命名空间的扩展//哈希函数的特化全特化的形式templatestruct hashPoint{size_t operator()(const Point rhs) const{//此处参考上面的哈希函数return true;}};
};// end of namespace//比较函数的实现:std::equal_to
bool operator(const Point lhs,const Point rhs){cout operator endl;return (lhs._ix rhs._ix lhs._iy rhs._iy);
}void test2(){//对于unordered_set容器在使用自定义数据类型时需要//传入第二个模板参数hash函数//然后还有第三个模板参数equal_to只不过这个模板参数是自定义类型中的运算符函数//这个函数需要被实现以定义某种比较两个自定义类型对象是否相等//若不实现的话则哈希函数无法判断是否发生哈希冲突即相同对象存储到了同一块位置unordered_setPoint,HashPoint number {Point(1,2),Point(1,2), Point(1,-2),Point(3,2),Point(-1,4)};display(number);
}int main(){test();return 0;
}
unordered_multiset的示例
其与unordered_set的使用没有什么区别只要记住下述的一点特性即可 1、key值是不唯一的可以重复 2、key值是没有顺序的 3、底层使用的是哈希结构
unordered_map的示例
和 map 基本没有区别就是其不会根据key值进行排序而已然后底层实现是哈希不是红黑树基本使用是一样的。
unordered_multimap的示例
就记几个特性就行基本都差不多。
