这篇文章主要为大家详细介绍了C++中set/multiset与map/multimap的使用,文中的示例代码讲解详细,具有一定的借鉴价值,需要的可以参考一下
一、关联式容器
vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
而关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是
关联式容器有两种,一种是map、set、multimap、multiset采用树形结构,他们的底层都是红黑树,另一种是哈希结构。
二、set的介绍
1、set是关联式容器,它表面上只存放value,实际底层中存放的是由
2、set调用find将采用中序遍历,可以用于排序+去重。
3、为了保证元素的唯一性,set中的元素均为const,所以并不能对元素进行修改,但可以进行插入删除。
1、接口count与容器multiset
count和find的作用一样,都是用于查找set中是否存在某个元素。
其实count是为了容器multiset设计的,该容器允许插入重复的元素,此时count会返回红黑树中被搜索元素的个数。
#include#include int main () { std::set myset; // set some initial values: for (int i=1; i<5; ++i) myset.insert(i*3); // set: 3 6 9 12 for (int i=0; i<10; ++i) { std::cout << i; if (myset.count(i)!=0) std::cout << " is an element of myset.\n"; else std::cout << " is not an element of myset.\n"; } return 0; }
2、接口lower_bound和upper_bound
lower_bound返回大于等于目标值的迭代器,upper_bound返回大于目标值的迭代器,在set中用于返回目标值的迭代器。(比如找到两个边界的迭代器,就可以使用erase对数据进行删除)
#include#include
三、map的介绍
map是关联式容器,根据特定的存储顺序,用于存储由键值及其映射值组合的元素。
可以看到Alloc中有一个键值对pair,这个pair是一个key/value结构的struct模板类。这个类将一对键值耦合在一起,所以,map的存储方式是通过在搜索二叉树中存储键值对pair,而搜索二叉树的k/v模型是在节点中存储key和value,并不相同。pair的结构:
templatestruct 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) {} };
1、接口insert
make_pair是一个函数模板:
templatepair make_pair (T1 x, T2 y) { return ( pair (x,y) ); }
2、接口insert和operator[]和at
使用map统计每个字符出现个数
写法2的[]详解:
Value& operator[] (const Key& k) { pairret=insert(make_pair(k,Value() ) ); //在结构体pair中找到first(一个map的迭代器),->解引用找到该迭代器的pair,再找该pair的second(即value) return ret.first->second; } //map的insert pair insert (const value_type& pair); //插入 dict["迭代器"];//在dict中找不到"迭代器"这个key,将新增一个节点,该节点的key为"迭代器",value为value类型的默认构造 //修改 dict["迭代器"]="iterator";//将key为"迭代器"的节点的value修改为"iterator"
不难看出map的operator[]兼具查找、插入、修改三种功能。(注意如果搜寻值不在map中,map可是会帮你新增一个节点的,map底层的红黑树将发生改变)
使用operator[],编译器会去调用insert(pair
at的功能和[]一样,区别在于用at找不到key将不会发生插入新节点,而是抛出异常。
3、容器multimap
multimap多个键值对中的key可以重复,所以并没有operator[]。同样的,使用find将返回中序遍历找到的第一个key值所处节点的迭代器。
四、map和set相关OJ
1、前K个高频单词
struct Compare { bool operator()(const pair& a,const pair & b) { return a.first>b.first || (a.first==b.first&&a.second topKFrequent(vector & words, int k) { vector ret; map dataMap; for(const auto& str : words) { dataMap[str]++; } vector > v; for(auto& kv : dataMap) { v.push_back(make_pair(kv.second,kv.first));//dataMap的first是string,second是int } sort(v.begin(),v.end(),Compare()); for(int i=0;i
2、两个数组的交集
class Solution { public: vectorintersection(vector & nums1, vector & nums2) { set s1(nums1.begin(),nums1.end());//nums1排序+去重 set s2(nums2.begin(),nums2.end());//nums2排序+去重 vector ret; for(auto& e : s1) { if(s2.find(e)!=s2.end()) { ret.push_back(e); } } return ret; } };
或者将两个数组排序+去重完毕后,使用双指针求解。(可用于找交集,差集)
以上就是C++中set/multiset与map/multimap的使用详解的详细内容,更多关于C++ set/multiset map/multimap的资料请关注0133技术站其它相关文章!
以上就是C++中set/multiset与map/multimap的使用详解的详细内容,更多请关注0133技术站其它相关文章!