手机网站被做跳转,不用js做网站,一个合格的网站设计,广东建设网官网目录
一、关联式容器
二、键值对
三、树形结构的关联式容器 3.1 set 3.1.1 set介绍
3.1.2 set的使用 1. set的模板参数列表 2. set的构造 3. set的迭代器(类型是双向迭代器) 4. set的容量 5.set修改操作 6、operator
7. set的使用举例
3.2 map
3.2.1map介绍
3.2.2map的…
目录
一、关联式容器
二、键值对
三、树形结构的关联式容器 3.1 set 3.1.1 set介绍
3.1.2 set的使用 1. set的模板参数列表 2. set的构造 3. set的迭代器(类型是双向迭代器) 4. set的容量 5.set修改操作 6、operator
7. set的使用举例
3.2 map
3.2.1map介绍
3.2.2map的使用
1.map的模板参数说明
2. map的构造
编辑
3. map的迭代器类其他容器 4. map的容量与元素访问
5. map中元素的修改
6、operator编辑 3.3 multiset
3.3.1 multiset的介绍
3.4 multimap
3.4.1 multimap的介绍
3.4.2 multimap的使用
3.5 在OJ中的使用 一、关联式容器 一般我们之前所学习的vector、list、daque、forword_list(C11)等容器都是序列式容器因为底层是线性序列的数据结构里面存储的是元素本身。 关联式容器也是存储型容器但是与序列式容器不同的是关联式容器一般存储的是键值对——key,value,在数据检索时比序列式容器雄效率更高。 二、键值对 一种类或者结构体用来表述具有一一对应关系的两个值一般存在两个成员变量key和valuekey表示键值用与检索比较排序value表示key对应的数据或信息。 例如建立一个汉英对应的字典每一个英文单词都有对应的中文含义将英文单词作为key值value作为对应的中文含义英文单词与中文含义是一一对应的关系在此字典中即可以通过英文找到其中文含义。 SGI-STL中关于键值对的定义 templateclass 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(T1()),second(T2()){}
}三、树形结构的关联式容器 根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构和哈希结构。树型结构的关联式容器主要有四种mapsetmultimapmultiset。这四种容器的特点是都使用了平衡搜索二叉树红黑树作为其底层结果容器中的元素是一个有序的序列key值排序。下面依次介绍每一个容器。 3.1 set 3.1.1 set介绍 set文档 翻译 1、set是按照一定次序存储元素 2、在set中value与key相同即是唯一的key不可修改但是可以插入或者删除 3、在内部set中的元素总是按照其内部比较对象类型比较所指示的特定严格弱排序准则进行排序 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的 注意 1. 与map/multimap不同map/multimap中存储的是真正的键值对set中只放 value但在底层实际存放的是由构成的键值对value,value。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历set中的元素可以得到有序序列 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为$log_2 n$ 7. set中的元素不允许修改(为什么?) 8. set中的底层使用二叉搜索树(红黑树)来实现。 3.1.2 set的使用 1. set的模板参数列表 T: set中存放元素的类型实际在底层存储的键值对。 Compareset中元素默认按照小于来比较升序 Allocset中元素空间的管理方式使用STL提供的空间配置器管理 2. set的构造 按参数列表分类默认构造、按迭代器范围构造、拷贝构造 3. set的迭代器(类型是双向迭代器) 4. set的容量 5.set修改操作 声明 重点在set中插入元素x实际插入的是x,x构成的键值对如果插入成功返回该元素在set中的位置true如果插入失败说明x在set中已经存在返回x在set中的位置false value_type是类模板中的第一个参数的别名 声明 1删除位置上的元素 3删除迭代器范围的元素 2删除值为val的元素并返回哥数 声明 交换两个set中的元素 声明 清空元素 6、operator find传递key返回指向位置的迭代器count:传递key返回个数set中仅有一哥元素lower_bound传递key返回在set序列中的第一个元素位置的迭代器upper_bound:传递key返回在set序列中的最后一个元素的下一个位置的迭代器 上述两函数实现左闭右开区级满足函数区间需求。equal_range:转递key返回该元素区间边界的迭代器组成的一个键值对第一个是lower_bound,第二个是upper_bound. 7. set的使用举例 #includeset
#includeiostream
#includeset
using std::cout;
using std::endl;
using std::set;
void test()
{int array[] { 1,1,1,1,1,3,1,23,3,3,2,13,2,23,3,23,3,1,2,1,1,2,1,2,567,5,7,6,5 };setint s(array, array sizeof(array) / sizeof(array[0]));cout s.size() endl;for (int e : s){cout e ;}cout endl;//逆向打印for (setint::reverse_iterator it s.rbegin(); it ! s.rend(); it){cout *it ;}cout endl;//统计次数cout s.count(3) endl;
}int main()
{test();return 0;
} 3.2 map 3.2.1map介绍 map文档 翻译 1、map是关联容器它按照特定的次序按照key来比较存储由键值key和值value组合而成的元素 2、在map中键值key通常用于排序和唯一的标识元素用于find查找value中存储与key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定到一起其为pair类实例化取别名。 typedef pairconst key,T value_type; 3、在内部map中的元素是按照键值key来比较排序 4、map中通过键值访问单一元素通常比unorder_map容器慢但map允许对元素进行直接迭代也就是说可以遍历访问得到一个有序序列。 5、map支持下标访问符即在[]中放入key可以直接找到与key对应都的value 6、map通常底层实现为平衡二叉树即红黑树 3.2.2map的使用 1.map的模板参数说明 key对应键值类型 T对应value类型 compare比较器的类型缺省按找小于比较升序序列一般情况下内置类型元素该参数不需要传递如果无法比较时自定义类型需要用户自己显示传递比较规则一般情况下按照函数指针或者仿函数来传递 Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的 空间配置器 2. map的构造 空参数列表构造迭代器范围构造、拷贝构造 3. map的迭代器类其他容器 4. map的容量与元素访问 empty:无参空返回true否则返回falsesize无参返回元素个数operator[]:参数是键值key返回value的引用 注意如果键值key在map中不存在则插入一个新的键值对元素键值为keyvalue的值为对应类型的默认构造。 at():同operator[] 5. map中元素的修改 insert参数为键值对pair类型返回一个键值对键值对first为插入位置类型iteratorsecond为bool类型表示插入是否成功。erase①参数为元素位置返回void②参数为迭代器范围删除范围中的元素swap交换两个map中的元素this*与参数交换参数为map类型返回voidclear清空map 6、operator find找键值key的位置参数为键值key返回位置迭代器count参数为key返回键值key的个数为1或0lower_bound:参数为key返回第一个key的位置迭代器upper_bound:参数为key返回最后一个key的下一个位置迭代器equal_bound:参数为key返回键值对类型为pairmapkey,value::iterator,mapkey,value::iterator,first为第一个key的位置迭代器second是最后一个key的下一个位置迭代器 【总结】 1. map中的的元素是键值对 2. map中的key是唯一的并且不能修改 3. 默认按照小于的方式对key进行比较 4. map中的元素如果用迭代器去遍历可以得到一个有序的序列 5. map的底层为平衡搜索树(红黑树)查找效率比较高$O(log_2 N)$ 6. 支持[]操作符operator[]中实际进行插入查找 3.3 multiset
3.3.1 multiset的介绍 [翻译] 1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的。与set的区别 2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是组成 的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。 3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则 进行排序。 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭 代器遍历时会得到一个有序序列。 5. multiset底层结构为二叉搜索树(红黑树) 注意 1. multiset中再底层中存储的是的键值对 2. mtltiset的插入接口中只需要插入即可 3. 与set的区别是multiset中的元素可以重复set是中value是唯一的 4. 使用迭代器对multiset中的元素进行遍历可以得到有序的序列 5. multiset中的元素不能修改 6. 在multiset中找某个元素时间复杂度为$O(log_2 N)$ 7. multiset的作用可以对元素进行排序 总结注意与set的区别insert返回为迭代器不是键值对pairiterator,bool,仅iterator 3.4 multimap
3.4.1 multimap的介绍
翻译 1. Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对其中多个键值对之间的key是可以重复的。
2. 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内 容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起 value_type是组合key和value的键值对: typedef pair value_type;
3. 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对 key进行排序的。
4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代 器直接遍历multimap中的元素可以得到关于key有序的序列。
5. multimap在底层用二叉搜索树(红黑树)来实现。
注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的
3.4.2 multimap的使用
multimap中的接口可以参考map功能都是类似的。
注意 1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较
3. multimap中没有重载operator[]操作(同学们可思考下为什么?)。无法返value.
4. 使用时与map包含的头文件相同
3.5 在OJ中的使用
692. 前K个高频单词 - 力扣LeetCode
349. 两个数组的交集 - 力扣LeetCode
