营销网站定制公司,男科医院网站模板,网站建设类织梦模板,抖音推广引流关联式概念
STL中的部分容器#xff0c;比如#xff1a;vector、list、deque、forward_list(C11)等#xff0c;这 些容器统称为序列式容器#xff0c;因为其底层为线性序列的数据结构#xff0c;里面存储的是元素本身。关联式容器也是用来存储数据的#xff0c;与序列式…关联式概念
STL中的部分容器比如vector、list、deque、forward_list(C11)等这 些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。
二叉搜索平衡结构
关于key有序的序列时间复杂度O(logN)
mapkey,value 要求:key一定不能重复set:key 要求:key一定不可以重复multimap:key,value key是可以重复的multiset:keykey可以重复
键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值 value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应 的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与 其对应的中文含义
SGI—STL中键值对的底层实现 template class T1, class T2 struct pair { typedef T1 first_type; typedef T2 second_type;T1 first; T2 second;
pair() : first(T1()) , second(T2()) {}
pair(const T1 a, const T2 b): first(a), second(b) {}}; map
map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值 key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起 为其取别名称为pair: typedef pair value_type;在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行 直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 map::insert() 通过insert插入数据有两种方式
pair类型类型(数据,数据)make_pair(数据数据)
还可以通过下标运算符[] 对于map来说如果我们提供的key不存在的情况下他就会插入这个数据 因为它的下标运算符的底层是这样实现的
(*((this-insert(make_pair(k,mapped_type()))).first)).second 如果key已经存在了他就不会插入
void TestMap()
{mapstring, stringm;m.insert(pairstring,string(宋江,及时雨));m.insert(pairstring, string(李逵, 黑旋风));//pairiterator,bool//iterator:代表map中的一个key-value的键值对//bool:insert插入是否成功auto ret m.insert(make_pair(孙二娘,母夜叉));if (ret.second){cout (*ret.first).first --- ret.first-second endl;}ret m.insert(make_pair(李逵, 铁牛));//key 已经存在不会插入cout (*ret.first).first --- ret.first-second endl;cout m.size() endl;cout m[李逵] endl; //把value返回来//用户提供key----[]返回key所对应的valuem[李逵] 铁牛; //修改valuecout m[李逵] endl;m[林冲] 豹子头;cout m.size() endl;
}下标运算符为什么要用insert? 因为如果key不存在的话返回值就不好返回了因为如果key存在返回存在的如果key不存在插入key和一个默认的value
void TestMap2()
{int array[] { 3, 1, 9, 4, 0, 7, 6, 2, 5 };mapint, intm;for (auto e : array){m.insert(make_pair(e, e));}//测试按照迭代器方式进行遍历能否得到一个关于key有序的序列auto it m.begin();while (it ! m.end()){cout it-first ---- it-second endl;it;}cout endl;for (auto e : m){cout e.first ---- e.second endl;}cout endl;
}key是有序的但是value就不一定 其余的功能演示参考:map的其他功能演示
set
set相关接口的演示
set容器没有下标预算符. set:key,key一定是唯一的 set 最主要的功能是去重并排序
测试set
int main()
{int array[] { 3, 1, 3, 4, 5, 6, 7, 8, 9, 0, 9, 4, 0, 7, 6, 2, 5, 8 };setints;for (auto e : array)s.insert(e);cout s.size() endl;for (auto e : s)cout e ;cout endl;system(pause);return 0;
}multimap
multimap基本操作
注意事项
multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较multimap中没有重载operator[]操作使用时与map包含的头文件相同
#include #include
void TestMultimap1()
{multimapstring, string m; m.insert(make_pair(李逵, 黑旋风)); m.insert(make_pair(林冲, 豹子头)); m.insert(make_pair(鲁达, 花和尚));// 尝试插入key相同的元素 m.insert(make_pair(李逵, 铁牛)); cout m.size() endl;for (auto e : m)
cout e.first , e.second endl;// key为李逵的元素有多少个 cout m.count(李逵) endl; return 0;
}void TestMultimap2() { multimapint, int m;for (int i 0; i 10; i) m.insert(pairint, int(i, i));for (auto e : m) cout e.first --- e.second endl; cout endl;// 返回m中大于等于5的第一个元素 auto it m.lower_bound(5); cout it-first --- it-second endl;// 返回m中大于5的元素 it m.upper_bound(5); cout it-first --- it-second endl;}multiset
multiset的基本操作
multiset:只存储keykey可以重复关于key有序
测试
int main()
{int array[] { 3, 1, 3, 4, 5, 6, 7, 8, 9, 0, 9, 4, 0, 7, 6, 2, 5, 8 };multisetints;for (auto e : array)s.insert(e);cout s.size() endl;for (auto e : s)cout e ;cout endl;system(pause);return 0;
}底层结构及其模拟实现
底层原理及其模拟实现
