商业网站建设费用,商丘网络科技有限公司,阿里建站官网,酷炫网站模板目录1. 关联式容器2. 键值对3. 树形结构的关联式容器3.1 set3.1.1 set的介绍3.1.2 set的使用3.2 multiset3.2.1 multiset的介绍3.2.2 multiset的使用3.3 map3.3.1 map的介绍3.3.2 map的使用operator[]3.4 multimap3.4.1 multimap的介绍3.4.2 multimap的使用3.5 map和set在OJ中的…
目录1. 关联式容器2. 键值对3. 树形结构的关联式容器3.1 set3.1.1 set的介绍3.1.2 set的使用3.2 multiset3.2.1 multiset的介绍3.2.2 multiset的使用3.3 map3.3.1 map的介绍3.3.2 map的使用operator[]3.4 multimap3.4.1 multimap的介绍3.4.2 multimap的使用3.5 map和set在OJ中的使用1. 关联式容器
STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。 那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对。序列式容器中存储的元素默认都是未经过排序的而使用关联式容器存储的元素默认会根据各元素的键值的大小做升序排序在数据检索时比序列式容器效率更高。
2. 键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义英文单词与其 中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。 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. 树形结构的关联式容器
根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、multimap、set、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
3.1 set
3.1.1 set的介绍
set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。
注意
与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列排序set中的元素默认按照小于来比较(升序)set中查找某个元素时间复杂度为log2nlog_2 nlog2nset中的元素不允许修改set中的底层使用二叉搜索树(红黑树)来实现。
3.1.2 set的使用
1.set的模板参数列表
T: set中存放元素的类型实际在底层存储value, value的键值对。 Compareset中元素默认按照小于来比较升序 Allocset中元素空间的管理方式使用STL提供的空间配置器管理
2.set的构造
函数声明功能介绍set (const Compare comp Compare(), const Allocator Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区间中的元素构造setset ( const setKey,Compare,Allocator x);set的拷贝构造
3.set的迭代器
函数声明功能介绍iterator begin()返回set中起始位置元素的迭代器iterator end()返回set中最后一个元素后面的迭代器const_iterator cbegin()const返回set中起始位置元素const迭代器const_iterator cend() const返回set中最后一个元素后面的const迭代器reverse_iterator rbegin()返回set第一个元素的反向迭代器即rendreverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器即rbeginconst_reverse_iterator crbegin() const返回set第一个元素的反向const迭代器即crendconst_reverse_iterator crend() const返回set最后一个元素下一个位置的反向const迭代器即crbegin
set的容量
函数声明功能介绍bool empty ( ) const检测set是否为空空返回true否则返回truesize_type size() const返回set中有效元素的个数
5.set修改操作
函数声明功能介绍pairiterator,bool insert (const value_type x )在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true,如果插入失败说明x在set中已经存在返回x在set中的位置falsevoid erase ( iterator position )删除set中position位置上的元素size_type erase ( const key_type x )删除set中值为x的元素返回删除的元素的个数void erase ( iterator first,iterator last )删除set中[first, last)区间中的元素void swap (setKey,Compare,Allocatorst );交换set中的元素void clear ( )将set中的元素清空iterator find ( const key_type x ) const找到了返回set中值为x的元素的位置没有找到返回end()size_type count ( const key_type x ) const返回set中值为x的元素的个数,在set中不是1就是0而在multiset中允许插入重复值就不一定是0或1了
其他
函数声明功能介绍iterator lower_bound (const value_type val) const;返回第一个大于等于val的迭代器iterator upper_bound (const value_type val) const;返回第一个大于val的迭代器
6.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, array sizeof(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;
}运行结果自动排序去重
3.2 multiset
3.2.1 multiset的介绍
multiset是按照特定顺序存储元素的容器其中元素是可以重复的。在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列。multiset底层结构为二叉搜索树(红黑树)。
注意
multiset中再底层中存储的是value, value的键值对需要注意的是由于multiset有允许元素重复find函数找的时候是中序的第一个位置。例如多个重复值中序遍历结果是3 3 3使用find函数会把第一个3的迭代器位置返回。mtltiset的插入接口中只需要插入即可与set的区别是multiset中的元素可以重复set是中value是唯一的使用迭代器对multiset中的元素进行遍历可以得到有序的序列multiset中的元素不能修改在multiset中找某个元素时间复杂度为O(log2N)O(log_2 N)O(log2N)multiset的作用可以对元素进行排序
3.2.2 multiset的使用
此处只简单演示set与multiset的不同其他接口接口与set相同。
#include set//头文件和set是一样的
void TestSet()
{int array[] { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };// 注意multiset在底层实际存储的是int, int的键值对multisetint s(array, array sizeof(array) / sizeof(array[0]));for (auto e : s)cout e ;cout endl;
}3.3 map
3.3.1 map的介绍 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 在map中键值key通常用于排序和唯一的标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可以不同。在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为 pair即typedef pairconst key, T value_type;。举个例子mapstring,int My_Map单拿出来My_Map中的每一个元素都是一个一个的pairstring,int区分不同的pair时就用pair的first也就是string来区分每一个pair。下图为pair的成员变量first和second以及对于value_type的定义。 在内部map中的元素总是按照键值key进行比较排序的。 map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。 map支持下标访问符即在[]中放入key就可以找到与key对应的value。 map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
3.3.2 map的使用
1.map的模板参数说明
key: 键值对中key的类型 T 键值对中value的类型 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器。 注意在使用map时需要包含头文件。
map的构造
函数声明功能介绍map (const key_compare comp key_compare(),const allocator_type alloc allocator_type());构造一个空的mapmap (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type());用[first, last)区间中的元素构造mapmap (const map x);map的拷贝构造
map的迭代器
函数声明功能介绍begin()和end()begin:首元素的位置end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同但cbegin和cend所指向的元素不能修改rbegin()和rend()反向迭代器rbegin在end位置rend在begin位置其和–操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同操作相同但crbegin和crend所指向的元素不能修改
map的容量与元素访问
函数声明功能简介bool empty ( ) const检测map中的元素是否为空是返回true否则返回falsesize_type size() const返回map中有效元素的个数mapped_type operator[] (const key_type k)返回去key对应的value
map中元素的修改
函数声明功能简介pairiterator,bool insert (const value_type x )在map中插入键值对x注意x是一个键值对返回值也是键值对iterator代表新插入元素的位置bool代表释放插入成功void erase ( iterator position )删除position位置上的元素size_type erase ( const key_type x )删除键值为x的元素void erase ( iterator first,iterator last )删除[first, last)区间中的元素void swap (mapKey,T,Compare,Allocatormp )交换两个map中的元素void clear ( )将map中的元素清空iterator find ( const key_type x)在map中插入key为x的元素找到返回该元素的位置的迭代器否则返回endconst_iterator find ( const key_type x ) const在map中插入key为x的元素找到返回该元素的位置的const迭代器否则返回cendsize_type count ( const key_type x ) const返回key为x的键值在map中的个数注意map中key是唯一的因此该函数的返回值要么为0要么为1因此也可以用该函数来检测一个key是否在map中
operator[] insert函数的返回值 //将上面蓝框的内容化简可得
V operatort[](const K k
{pairiterator,bool ret insert(make_pair(kV()));return ret.first-second;
}operator[]的原理是 用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中 如果key已经存在插入失败insert函数返回该key所在位置的迭代器。 如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回。
注意在元素访问时有一个与operator[]类似的操作at()(该函数不常用)函数 都是通过key找到与key对应的value然后返回value的引用返回引用表示可以对value进行写和读 不同的是当key不存在时operator[]调用 value的默认构造 与 key的构造 二者组成键值对然后插入返回该 默认value而at()函数直接抛异常。
来咱用一用请看使用示例代码
#includeiostream
#includestring
#include map
using namespace std;int main()
{///operate[]的不同使用场景mapstring, string dict;dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));dict.insert(make_pair(字符串, string)); dict[迭代器] iterator; // 插入修改dict[insert]; // 插入 key不在就是插入// 插入失败搜索树只比较keydict.insert(pairstring, string(左边, xxx)); dict[insert] 插入; //修改cout dict[左边] endl; // 查找 key在就是查找//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){//cout (*it).first:(*it).second endl;cout it-first : it-second endl;it;}cout endl;for (const auto kv : dict){cout kv.first : kv.second endl;}// 统计水果出现的次数/string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;//for (auto e : arr)//{// //mapstring, int::iterator it countMap// auto it countMap.find(e);// if (it countMap.end())// {// countMap.insert(make_pair(e, 1));// }// else// {// it-second;// }//}for (auto e : arr){countMap[e];}for (const auto kv : countMap){cout kv.first : kv.second endl;}return 0;
}向map中插入元素的方式insert、operator[]、erase的使用举例
#include string
#include map
void TestMap()
{mapstring, string m;// 将键值对peach,桃子插入map中用pair直接来构造键值对m.insert(pairstring, string(peach, 桃子));// 将键值对peach,桃子插入map中用make_pair函数来构造键值对m.insert(make_pair(banan, 香蕉));// 借用operator[]向map中插入元素// 将apple, 插入map中插入成功返回value的引用将“苹果”赋值给该引用结果m[apple] 苹果;// key不存在时抛异常//m.at(waterme) 水蜜桃;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;}【总结】
map中的的元素是键值对map中的key是唯一的并且不能修改默认按照小于的方式对key进行比较map中的元素如果用迭代器去遍历可以得到一个有序的序列map的底层为平衡搜索树(红黑树)查找效率比较高O(log2N)O(log_2 N)O(log2N)支持[]操作符operator[]中实际进行 插入 查找 修改。
3.4 multimap
3.4.1 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和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。
3.4.2 multimap的使用
multimap中的接口可以参考map功能都是类似的。 注意
multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较multimap中没有重载operator[]操作因为这里是一对多的结构。使用时与map包含的头文件相同。
3.5 map和set在OJ中的使用
1、前K个高频单词 题目链接 思路定义一个 mapstring,int类型的map将vectorstring words中的元素利用operator[]插入到map中此时已经自动将所有字符串按字典序排序 并在int中记录出现次数。 然后转移到 vectorpairstring,int v方便下一步对于出现次数的排序排序时要对int进行排序但是题中又说 如果不同的单词有相同出现频率 按字典顺序排序。 面临的问题有两个 1、pair默认的比较大小方式并不适合此题需要自己写仿函数 2、sort排序是不稳定的排序对于出现次数相同的两个单词可能会把它们的字典序也打乱所以要使用稳定的排序stable_sort。 代码
class Solution {
public:class compare{public://需要自己按照题目要求定义一个仿函数bool operator()(const pairstring,int x, const pairstring,int y) const{return x.second y.second;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int CountMap;for(const auto one_words:words){CountMap[one_words];//关键的第一步}//然后转移到vector中vectorpairstring,int v;for(auto sp:CountMap){v.push_back(sp);}//使用稳定排序对pair的second也就是int进行排序——关键的第二步stable_sort(v.begin(),v.end(),compare());vectorstring ret;for(int i0;ik;i){ret.push_back(v[i].first);}return ret;}
};2、两个数组的交集 题目链接 思路创建两个set int 类型的对象s1和s2分别来“装”num1和num2以此达到对num1和num2实现排序去重的目的然后就是遍历s1和s2。
相等就是交集值插入到要返回的vector int 中同时让s1和s2的迭代器不相等对应的值小的 迭代器 有一个set到结尾end了那么就结束统计了。
代码
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1,s2;//自动排序去重for(auto n1:nums1){s1.insert(n1);}for(auto n2:nums2){s2.insert(n2);}vectorint ret;auto it1s1.begin();auto it2s2.begin();while(it1!s1.end()it2!s2.end())//遍历s1和s2{if(*it1*it2){ret.push_back(*it1);it1;it2;}else if(*it1*it2){it2;}else{it1;}}return ret;}
};
