金融网站制作,网站做cdn,wordpress 移动支付宝,百度用户服务中心官网set、map、multiset、multimap的介绍及使用 一、关联式容器二、键值对键值对概念定义 三、setset的介绍set的使用set的模板参数列表set的构造set的迭代器set的容量emptysize set的修改操作insertfind erasecountlower_bound 和 upper_bound Multiset的用法 四、mapm… set、map、multiset、multimap的介绍及使用 一、关联式容器二、键值对键值对概念定义 三、setset的介绍set的使用set的模板参数列表set的构造set的迭代器set的容量emptysize set的修改操作insertfind erasecountlower_bound 和 upper_bound Multiset的用法 四、mapmap的介绍map的用法map的模板参数 map迭代器map的构造map的常见修改操作inserterasefindcount map的容量与元素访问 -- operator[]利用map统计出现次数用直接插入法用[]法 multimapmultimap介绍multimap的使用 五、题目前k个高频词题目描述解题思路解题代码 两个数组的交集题目描述解题思路解题代码差集思想 一、关联式容器
初期我们接触了listvectordeque等容器这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 二、键值对
键值对概念
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。
定义
SGI-STL中关于键值对pair的定义
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(a),second(b){}
};三、set
set的介绍
set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。 1.与map/multimap不同map/multimap中存储的是真正的键值对key,valueset中只放value但在底层实际存放的是由value, value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历set中的元素可以得到有序序列 5. set中的元素默认按照小于来比较 6. set中查找某个元素时间复杂度为 l o g 2 n log_2 n log2n 7. set中的元素不允许修改(为什么?) 8. set中的底层使用二叉搜索树(红黑树)来实现。 总结set的本质就是key模型。
set的使用
set支持的操作为增删查不能修改
set的模板参数列表 Tset中存放元素的类型实际在底层存储的是value, value的键值对 Compare仿函数set容器中默认使用库函数中的less函数来比较我们如果想实现More函数我们可以自己进行写一个More函数以实现不同的功能。 Allocset中元素空间的管理方式使用STL提供的空间配置器。
set的构造 void testset1()
{setint set1;int num[10] { 1,2,4,3,5,7,6,8,9,10 };// 区间构造setint set2(num, num sizeof(num) / sizeof(num[0]));// 拷贝构造setint set3(set2);// 拷贝构造代价太大// for循环打印set2for (auto e : set2){cout e ;}cout endl;// for循环打印set3for (auto e : set3){cout e ;}cout endl;
}set的迭代器 如图所示 void testset2()
{setint set1 { 1,2,1,4,5,3,7,6,5,8,9 };setint::iterator it set1.begin();// 去重排序while (it ! set1.end()){cout *it ;it;}cout endl;// 范围forfor (auto e : set1){cout e ;}cout endl;
}我们如果想要将这个排序变成降序该咋办呢很简单用一个Greater仿函数即可
void testset3()
{int a[10] { 1,3,1,2,4,5,7,6,5,8 };// 这个greater仿函数是set库函数中的函数// 就是进行降序的函数setint, greaterint set1(a, a sizeof(a) / sizeof(a[0]));// for循环for (auto e : set1){cout e ;}cout endl;
}set的容量
empty size set的修改操作
insert 这里我们直接用cplusplus网站上的插入介绍和代码解析 void testset4()
{std::setint myset;std::setint::iterator it;std::pairstd::setint::iterator, bool ret;// for循环并单个插入for (int i 1; i 5; i)myset.insert(i * 10);// 单个插入ret myset.insert(20);if (ret.second false) it ret.first;// 插入迭代器所代表的值myset.insert(it, 25);myset.insert(it, 24);myset.insert(it, 26);// 插入一段区间int myints[] { 5,10,15 };myset.insert(myints, myints 3);std::cout myset contains:;for (it myset.begin(); it ! myset.end(); it)std::cout *it;std::cout \n;
}find erase void testset5()
{std::setint myset;std::setint::iterator it;for (int i 1; i 10; i) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90it myset.begin();it; // 第二个位置// 删除第二个位置myset.erase(it);// 删除一个数myset.erase(40);// 删除一个迭代器区间it myset.find(60);myset.erase(it, myset.end());std::cout myset contains:;for (it myset.begin(); it ! myset.end(); it)std::cout *it;std::cout \n;
}上面是erase我们下面介绍一下find
void testset6()
{std::setint myset;std::setint::iterator it;for (int i 1; i 5; i) myset.insert(i * 10); // 10 20 30 40 50it myset.find(20);myset.erase(it); // 删除20这个迭代器的值myset.erase(myset.find(40)); // 删除40这个迭代器的值std::cout myset contains:;for (it myset.begin(); it ! myset.end(); it)std::cout *it;std::cout \n;
}看似没什么问题有一个问题那我们假如说删除了一个并不存在的数值或者是迭代器呢 所以我们在写完find以后需要判断一下是否是真的找到了找到了才能删除找不到就不删除即可。 // 删除一个不存在的迭代器setint::iterator pos myset.find(70);if (pos ! myset.end()){myset.erase(pos);}count lower_bound 和 upper_bound void testset9()
{setint myset;setint::iterator itup, itlow;for (int i 1; i 10; i){myset.insert(i * 10);}itlow myset.lower_bound(35);itup myset.upper_bound(60);cout [ *itlow , *itup ] endl;myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;
}Multiset的用法
multiset的用法和set基本是一致的唯一一个区别是multiset允许键值对冗余即使用multiset可以让数字重复。
void testset10()
{// multisetint a[10] {1,3,2,4,1,2,5,6,7,10};multisetint set1(a, a sizeof(a) / sizeof(a[0]));for (auto e : set1){cout e ;}cout endl;
}还有一个find和erase呢 find是返回中序中的第一个在有多个重复值的情况下。
erase是将所有的想删除的值全部删掉。
四、map
map的介绍
map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair: typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
map的用法
map的模板参数 key: 键值对中key的类型 T 键值对中value的类型 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器
map迭代器 void testmap1()
{mapstring, string map1;map1.insert(make_pair(banana, 香蕉));map1.insert(make_pair(apple, 苹果));map1.insert(make_pair(orange, 橙子));mapstring, string::iterator it map1.begin();while (it ! map1.end()){cout it-first it-second endl;it;}
}map的构造 void testmap2()
{mapint, int map1; // 空的构造int a[] { 1,2,3,4,5,6,7,8,88,9,10 };for (auto e : a){map1.insert(make_pair(e, e));}mapint, int map2(map1.begin(), map1.end()); // 迭代器区间构造mapint, int map3(map2); // 拷贝构造for (auto e : map3){cout e.first - e.second endl;}
}map的常见修改操作
insert void testmap3()
{std::mapchar, int mymap;// 匿名对象mymap.insert(std::pairchar, int(a, 100));mymap.insert(std::pairchar, int(z, 200));// 在map中插入一个键值对迭代器加判断是否插入成功std::pairstd::mapchar, int::iterator, bool ret;ret mymap.insert(std::pairchar, int(z, 500));if (ret.second false) {std::cout element z already existed;std::cout with a value of ret.first-second \n;}// 插入一个迭代器位置加值std::mapchar, int::iterator it mymap.begin();mymap.insert(it, std::pairchar, int(b, 300));mymap.insert(it, std::pairchar, int(c, 400));// 迭代器区间插入利用begin()到find(c)的位置std::mapchar, int anothermap;anothermap.insert(mymap.begin(), mymap.find(c));std::cout mymap contains:\n;for (it mymap.begin(); it ! mymap.end(); it)std::cout it-first it-second \n;std::cout anothermap contains:\n;for (it anothermap.begin(); it ! anothermap.end(); it)std::cout it-first it-second \n;
}还有一种很省力的方法使用make_pair匿名对象因为是make_pair返回的就是pairT1,T2(x, y)即自动识别类型。
#includeiostream
using namespace std;
int main()
{std::mapint, int map1;map1.insert(make_pair(1, 1));map1.insert(make_pair(2, 2));map1.insert(make_pair(3, 3));for(auto e : map1){cout e ;}cout endl;
}erase void testmap4()
{std::mapchar, int mymap;std::mapchar, int::iterator it;mymap.insert(make_pair(a, 10));mymap.insert(make_pair(b, 20));mymap.insert(make_pair(c, 30));mymap.insert(make_pair(d, 40));mymap.insert(make_pair(e, 50));mymap.insert(make_pair(f, 60));// 删除b这个位置的整个迭代器it mymap.find(b);mymap.erase(it);// 删除键值为c的元素mymap.erase(c);// 删除迭代器区间it mymap.find(e);mymap.erase(it, mymap.end());for (it mymap.begin(); it ! mymap.end(); it)std::cout it-first it-second \n;
}find void testmap5()
{std::mapchar, int mymap;std::mapchar, int::iterator it;mymap.insert(pairchar, int(a, 50));mymap.insert(make_pair(b, 100));mymap.insert(pairchar, int(c, 150));mymap.insert(pairchar, int(d, 200));// 找到b这个键值对it mymap.find(b);if (it ! mymap.end()) // 判断是否找到mymap.erase(it);std::cout elements in mymap: \n;std::cout a mymap.find(a)-second \n;std::cout c mymap.find(c)-second \n;std::cout d mymap.find(d)-second \n;
}count
void testmap6()
{std::mapchar, int mymap;char c;mymap.insert(make_pair(a, 101));mymap.insert(make_pair(b, 202));mymap.insert(make_pair(c, 303));mymap.insert(make_pair(d, 404));for (c a; c h; c){std::cout c;if (mymap.count(c) 0) // 数值大于0则输出是个有值的mapstd::cout is an element of mymap.\n;elsestd::cout is not an element of mymap.\n;}
}map的容量与元素访问 – operator[] empty和size都好讲一个是判空一个是算里面的数量而重头戏在operator[]。 []有插入、查找和修改的功能。 1、map中有这个key返回value的引用。 2、map中没有这个key的匹配值则先构造一个pair(key, T())先插入这个key值再将value进行默认构造最后返回value的引用。‘ []的底层实现 底层实现有两个pair的方式 第一个是像上面所述的当key在map中的时候返回的pairkey_iterator, false当key不在map中返回的是pairnew_key_iterator, true即返回的是迭代器和bool值。 第二种则是kv模型的pair是插入的pair的数据。
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V());return ret.first-second;
}利用map统计出现次数
用直接插入法
void test_map()
{string arr[] { 苹果,香蕉,橙子,苹果,香蕉,橙子,苹果,香蕉,橙子,梨,柠檬 };mapstring, int fruitcount;for (auto e : arr){mapstring, int::iterator it fruitcount.find(e);if (it ! fruitcount.end()){it-second;}else{// 刚进入fruitcount.insert(make_pair(e, 1));}}// 遍历mapstring, int::iterator it fruitcount.begin();while (it ! fruitcount.end()){cout it-first it-second endl;it;}cout endl;
}用[]法
void test_map1()
{string arr[] { 苹果,香蕉,橙子,苹果,香蕉,橙子,苹果,香蕉,橙子,梨,柠檬 };mapstring, int fruitcount;for (auto e : arr){//1、e不在fruitcount中插入pair(e, int()),然后对返回次数//2、e在的话就返回value的引用次数fruitcount[e];}// 遍历mapstring, int::iterator it fruitcount.begin();while (it ! fruitcount.end()){cout it-first it-second endl;it;}cout endl;
}multimap
multimap介绍
Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key, value其中多个键值对之间的key是可以重复的。在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对:typedef pairconst Key, T value_type;在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的。multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。multimap在底层用二叉搜索树(红黑树)来实现。
multimap的使用
void test_map2()
{multimapstring, string mdict;mdict.insert(make_pair(sort, 排序));mdict.insert(make_pair(left, 左边));mdict.insert(make_pair(left, 右边));mdict.insert(make_pair(left, 不知道));// 遍历for (auto e : mdict){cout e.first e.second endl;}cout endl;
}五、题目
前k个高频词
题目描述 解题思路 解题代码
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {// 用来记录次序的本身就是按照字典序进行统计次数的mapstd::string, int countmap;for(const auto e : words){countmap[e];}// 用来排序的multimapint, string, greaterint sortmap;// i - 2 love - 2 leetcode - 1 coding - 1for(auto e : countmap){sortmap.insert(make_pair(e.second, e.first));}// 开辟一个字符串数组vectorstring v;multimapint, string, greaterint::iterator it sortmap.begin();for(int i 0; i k; i){v.push_back(it-second);it;}return v;}
};两个数组的交集
题目描述 解题思路 解题代码
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(), nums1.end());setint s2(nums2.begin(), nums2.end());setint::iterator it1 s1.begin();setint::iterator it2 s2.begin();vectorint v;while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){it1;}else if(*it1 *it2){it2;}else{v.push_back(*it1);it2;it1;}}return v;}
};差集思想
