纸 技术支持 东莞网站建设,深圳建设集团招标,学校培训,怎么制作网站上传目录
一、关联式容器
二、set的介绍
1、接口count与容器multiset
2、接口lower_bound和upper_bound
三、map的介绍
1、接口insert
2、接口insert和operator[]和at
3、容器multimap
四、map和set相关OJ
1、前K个高频单词
2、两个数组的交集 一、关联式容器
vector、… 目录
一、关联式容器
二、set的介绍
1、接口count与容器multiset
2、接口lower_bound和upper_bound
三、map的介绍
1、接口insert
2、接口insert和operator[]和at
3、容器multimap
四、map和set相关OJ
1、前K个高频单词
2、两个数组的交集 一、关联式容器
vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。
而关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 插入删除只需挪动指针指向无需挪动数据查找时间logN
关联式容器有两种一种是map、set、multimap、multiset采用树形结构他们的底层都是红黑树另一种是哈希结构。
二、set的介绍 1、set是关联式容器它表面上只存放value实际底层中存放的是由value,value组成的键值对。
2、set调用find将采用中序遍历可以用于排序去重。
3、为了保证元素的唯一性set中的元素均为const所以并不能对元素进行修改但可以进行插入删除。
1、接口count与容器multiset
count和find的作用一样都是用于查找set中是否存在某个元素。
其实count是为了容器multiset设计的该容器允许插入重复的元素此时count会返回红黑树中被搜索元素的个数。
#include iostream
#include setint main ()
{std::setint myset;// set some initial values:for (int i1; i5; i) myset.insert(i*3); // set: 3 6 9 12for (int i0; i10; i){std::cout i;if (myset.count(i)!0)std::cout is an element of myset.\n;elsestd::cout is not an element of myset.\n;}return 0;
} 2、接口lower_bound和upper_bound
lower_bound返回大于等于目标值的迭代器upper_bound返回大于目标值的迭代器在set中用于返回目标值的迭代器。比如找到两个边界的迭代器就可以使用erase对数据进行删除
#include iostream
#include mapint main ()
{std::mapchar,int mymap;std::mapchar,int::iterator itlow,itup;mymap[a]20;mymap[b]40;mymap[c]60;mymap[d]80;mymap[e]100;itlowmymap.lower_bound (b); // itlow points to bitupmymap.upper_bound (d); // itup points to e (not d!)mymap.erase(itlow,itup); // a 20 e 100// print content:for (std::mapchar,int::iterator itmymap.begin(); it!mymap.end(); it)std::cout it-first it-second \n;return 0;
} 三、map的介绍 map是关联式容器根据特定的存储顺序用于存储由键值及其映射值组合的元素。
可以看到Alloc中有一个键值对pair这个pair是一个key/value结构的struct模板类。这个类将一对键值耦合在一起所以map的存储方式是通过在搜索二叉树中存储键值对pair而搜索二叉树的k/v模型是在节点中存储key和value并不相同。pair的结构
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){}
}; 1、接口insert make_pair是一个函数模板:
template class T1,class T2
pairT1,T2 make_pair (T1 x, T2 y)
{return ( pairT1,T2(x,y) );
} 2、接口insert和operator[]和at
使用map统计每个字符出现个数 写法2的[]详解
Value operator[] (const Key k)
{pairiterator,bool retinsert(make_pair(k,Value() ) );//在结构体pair中找到first(一个map的迭代器)-解引用找到该迭代器的pair再找该pair的second(即value)return ret.first-second;
}
//map的insert
pairiterator,bool insert (const value_type pair);
//插入
dict[迭代器];//在dict中找不到迭代器这个key将新增一个节点该节点的key为迭代器,value为value类型的默认构造
//修改
dict[迭代器]iterator;//将key为迭代器的节点的value修改为iterator 不难看出map的operator[]兼具查找、插入、修改三种功能。(注意如果搜寻值不在map中map可是会帮你新增一个节点的map底层的红黑树将发生改变)
使用operator[]编译器会去调用insert(pairconst key,value())进行插入如果没有找到key所对应的节点则会新增一个节点并将该节点中pair的value置为value类型的默认构造如果找到了则返回该节点pair中value的引用。(可读可写)
at的功能和[]一样区别在于用at找不到key将不会发生插入新节点而是抛出异常。
3、容器multimap
multimap多个键值对中的key可以重复所以并没有operator[]。同样的使用find将返回中序遍历找到的第一个key值所处节点的迭代器。
四、map和set相关OJ
1、前K个高频单词 struct Compare
{bool operator()(const pairint,string a,const pairint,string b){return a.firstb.first || (a.firstb.firsta.secondb.second);}
};
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {vectorstring ret;mapstring,int dataMap;for(const auto str : words){dataMap[str];}vectorpairint,string v;for(auto kv : dataMap){v.push_back(make_pair(kv.second,kv.first));//dataMap的first是stringsecond是int}sort(v.begin(),v.end(),Compare());for(int i0;ik;i){ret.push_back(v[i].second);}return ret;}
}; 2、两个数组的交集 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(),nums1.end());//nums1排序去重 setint s2(nums2.begin(),nums2.end());//nums2排序去重vectorint ret;for(auto e : s1){if(s2.find(e)!s2.end()){ret.push_back(e);}}return ret;}
}; 或者将两个数组排序去重完毕后使用双指针求解。可用于找交集差集
