上传了网站标志 功能链接,专业影视广告制作公司,怎样做网站的签约设计师,凡科互动登录1. 关联式容器 在初阶阶段#xff0c;我们已经接触过STL中的部分容器#xff0c;比如#xff1a;vector、list、deque、 forward_list(C11)等#xff0c;这些容器统称为序列式容器#xff0c;因为其底层为线性序列的数据结构#xff0c;里面 存储的是元素本身。那什么是关…1. 关联式容器 在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、 forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面 存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是结构的 键值对 在数据检索时比序列式容器效率更高。
2. 键值对 pair 用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代 表键值value表示与key对应的信息。 比如现在要建立一个英汉互译的字典那该字典中必然 有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应 该单词在词典中就可以找到与其对应的中文含义。 key为单词value为翻译 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)
{}
};
3.map set 两者都使用红黑树作为底层数据结构来存储元素。map是一种键值对容器其中每个键都是唯一的并且与一个值相关联。set则是一个元素集合其中的每个元素也是唯一的但它不存储与元素相关联的值。 4.set K模型 set使用介绍
set是标准模板库STL中的一种关联容器它存储的元素是唯一的并且按照特定的顺序默认是升序自动排序。
https://cplusplus.com/reference/set/set/?kwset
注意 1. 与map/multimap不同map/multimap中存储的是真正的键值对key,valueset中只放 value但在底层实际存放的是由value,value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。!!!!!!!!!! 4. 使用set的迭代器遍历set中的元素可以得到有序序列(可以理解为二叉搜索树的中序遍历) 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为log2n 7. set中的元素不允许修改 !!!!!!!!!! 1. set的模板参数列表 T: set中存放元素的类型实际在底层存储的键值对。 Compareset中元素默认按照小于来比较 Allocset中元素空间的管理方式使用STL提供的空间配置器管理 2. set的构造 3. set的迭代器 4. set的容量 5. set修改操作 #include set
void TestSet()
{// 用数组array中的元素构造setint array[] { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };setint s(array, arraysizeof(array)/sizeof(array[0]));cout s.size() endl;// 正向打印set中的元素从打印结果中可以看出set可去重for (auto e : s)cout e ;cout endl;// 使用迭代器逆向打印set中的元素for (auto it s.rbegin(); it ! s.rend(); it)cout *it ;cout endl;// set中值为3的元素出现了几次cout s.count(3) endl;
}
5.multiset 它允许存储具有相同值的元素并且这些元素会根据特定的排序准则自动排序。与 set 容器不同multiset 允许重复的元素值。 multiset的操作大致是一样的唯一的额区别就是multiset允许有重复的元素。针对set以下接口大致是留给multiset https://cplusplus.com/reference/set/multiset/?kwmultiset 6. mapKV模型 https://cplusplus.com/reference/map/map/?kwmap 1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元 素。 2. 在map中键值key通常用于排序和唯一地标识元素而值value中存储与此键值key关联 的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类 型value_type绑定在一起为其取别名称为pair: typedef pair value_type; 3. 在内部map中的元素总是按照键值key进行比较排序的。 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。 5. map支持下标访问符即在[]中放入key就可以找到与key对应的value。 6. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 1. map的模板参数说明 1.key: 键值对中key的类型 2.T 键值对中value的类型 3.Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比 较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户 自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) 4.Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的 空间配置器 2. map的构造 3. map的迭代器 4. map的容量与元素访问 1.着重讨论operator[] 问题当key不在map中时通过operator获取对应value时会发生什么问题 当key不存在时operator[]用默认 value与key构造键值对然后插入返回该默认value !!! pairiterator, bool ret insert(key, V());
return ret.first-second;//这里返回的是value5. map中元素的修改 #include string
#include map
void TestMap()
{mapstring, string m;// c98 插入m.insert(pairstring, string(peach, 桃子));// c11 插入m.insert(make_pair(banan, 香蕉));// 借用operator[]向map中插入元素/*operator[]的原理是用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中如果key已经存在插入失败insert函数返回该key所在位置的迭代器如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回*/// 将apple, 插入map中插入成功返回value的引用将“苹果”赋值给该引
用结果m[apple] 苹果;cout m.size() endl;// 用迭代器去遍历map中的元素可以得到一个按照key排序的序列for (auto e : m)cout e.first --- e.second endl;cout endl;// map中的键值对key一定是唯一的如果key存在将插入失败auto ret m.insert(make_pair(peach, 桃色));if (ret.second)cout peach, 桃色不在map中, 已经插入 endl;elsecout 键值为peach的元素已经存在 ret.first-first --- ret.first-second 插入失败 endl;// 删除key为apple的元素m.erase(apple);if (1 m.count(apple))cout apple还在 endl;elsecout apple被吃了 endl;
} 1. map中的的元素是键值对 2. map中的key是唯一的并且不能修改 3. 默认按照小于的方式对key进行比较 4. map中的元素如果用迭代器去遍历可以得到一个有序的序列 5. map的底层为平衡搜索树(红黑树)查找效率比较高O(log_2 N) 6. 支持[]操作符operator[]中实际进行插入查找。 7. multimap
https://cplusplus.com/reference/map/multimap/?kwmultimap 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是可以 重复的。 所以multimap中没有重载operator[]操作 8.实际应用
1.前k个高频单词
. - 力扣LeetCode class Solution {
public:struct compare{bool operator()(const pairstring,int V1,const pairstring,int V2){return (V1.second V2.second) || (V1.second V2.second V1.first V2.first);//如果一样就按first排序}};//vectorstring topKFrequent(vectorstring words, int k) {mapstring,int CountMap;for(auto e : words){CountMap[e];//这里并没有有序因为map的默认构造是根据key的大小进行排序插入的但本题的要求是先按value降序排序若相同再按key升序排序}vectorpairstring,int v(CountMap.begin(),CountMap.end()); //需要存到vector内才能调用sort函数因为迭代器类型不同sort(v.begin(),v.end(),compare());//这里传的是compare对象不是模板参数sort支持仿函数//如果不写compare直接调用会出问题一是迭代器类型不匹配vectorstring vs;for(size_t i0; ik;i){vs.push_back(v[i].first);}return vs;}
}; 仿函数往期连接priority移情别恋c ദ്ദി˶̀֊́ ) ——8.stackqueuepriority_queue(模拟实现-CSDN博客
2.两个数组的交集
. - 力扣LeetCode class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setintarr(nums1.begin(),nums1.end());setintbrr(nums2.begin(),nums2.end());vectorint str;int num0;auto it1arr.begin();auto it2brr.begin();while(it1!arr.end()it2!brr.end()){if(*it1!*it2){if(*it1*it2)it1;elseit2;}else{str.push_back(*it1);it1;it2;}}return str;}
}; map和set对比
综上所述map和set很相似很多接口都一样区别如下
