电子商务的网站有哪些,怎么给网站做快照,自己如何开网站,大专毕业设计模板范文set和map的使用 1.关联式容器2.key模型和key_value模型3.set3.1一些注意点3.2set的使用3.3习题 4.multiset5.map5.1一些注意点5.2map的使用5.3习题 6.multimap 1.关联式容器
序列式容器#xff1a;比如我们之前讲的vector、string、list等均为序列式容器#xff0c;特点是按… set和map的使用 1.关联式容器2.key模型和key_value模型3.set3.1一些注意点3.2set的使用3.3习题 4.multiset5.map5.1一些注意点5.2map的使用5.3习题 6.multimap 1.关联式容器
序列式容器比如我们之前讲的vector、string、list等均为序列式容器特点是按元素顺序来保存和访问。 关联式容器比如本次讲的map和set和序列式容器不同其依靠键值来保存和访问数据检索效率闭序列式容器高。 PS本文只讲使用set和map底层是一颗平衡二叉搜索树。 2.key模型和key_value模型
1key模型主要解决在不在的问题比如现在录入人脸信息用户登录的判断就可以采用key模型set其实就是一个key模型。
#include iostream
#include string
#include map
#include set
#include vector
using namespace std;int main() {setstring s;vectorstring v {张三, 李四, 王五, 赵六};for (auto e : v) s.insert(e); //还没讲接口这里的作用是录入信息string input;while (cin input){if (s.count(input)) //这里的作用是在set中查找input是否存在{cout 存在查找成功 endl;}else{cout 不存在 endl;}}return 0;
}2key_value模型和key模型最大的不同就是存储key模型只存一个键值而key_value模型存储的是一个键值对。除了可以解决在不在的问题还可以通过键值找到对应信息map其实就是一个key_value模型。 键值对用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量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){}
};int main() {//还没讲接口知道大概意思就行mapstring, string mapTranslation; //就以英汉翻译词典为例子//录入词典的信息mapTranslation.insert(make_pair(left, 左边));mapTranslation.insert(make_pair(right, 右边));mapTranslation.insert(make_pair(sort, 排序));mapTranslation.insert(make_pair(father, 父亲));string input;while (cin input){if (mapTranslation.count(input)) //这里也是查找在不在{cout 中文为: mapTranslation[input] endl; //这里拿到value}else{cout 词典无记录 endl;}}return 0;
}3.set
3.1一些注意点
set不允许键值冗余比如插入3后不能再插入3。拒绝键值冗余本就是二叉搜索树的定义。故set中不会有重复的元素可以利用这一点对数据进行去重。set利用迭代器遍历元素可以得到一个有序序列可利用这一点对数据进行排序。原理是中序遍历二叉搜索树可以得到有序序列。set元素默认按小于比较即默认升序。set不允许修改元素如果支持修改会无法维护搜索二叉树的结构。set中查找某个元素时间复杂度为logN 3.2set的使用
1模板参数
2构造
函数声明功能set (const Compare comp Compare(), const Allocator Allocator())空构造set (InputIterator first, InputIterator last, 后面和空构造一样)迭代器区间构造set (const set x)拷贝构造
3迭代器
函数声明功能iterator begin()返回set中起始位置元素的迭代器iterator end()返回set中最后一个元素后面的迭代器reverse_iterator rbegin()反向迭代器返回end()reverse_iterator rend()反向迭代器返回begin()的前一个位置
4容量
函数声明功能bool empty ( ) const检测set是否为空空返回true否则返回falsesize_type size() const返回set中有效元素的个数
5增加、删除、查找
函数声明功能pairiterator,bool insert ( const value_type x )在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true如果插入失败说明x在set中已经存在返回x在set中的位置falsevoid erase ( iterator position)删除对应position位置的元素size_type erase ( const key_type x )删除set中值为x的元素返回删除的元素的个数void erase ( iterator first, iterator last )删除set中[first, last)区间中的元素iterator find ( const key_type x ) const返回set中值为x的元素的迭代器不存在返回end()size_type count ( const key_type x ) const返回set中值为x的元素的个数void swap (set sp )交换两个set中的元素void clear ( )将set中的元素清空
几个注意点
insert的返回值希望大家记一下方便大家理解map的核心接口。判断键值在不在set中有两种方法第一种是find(key)依据返回值判断是end()代表不在否则存在。第二种是count(key)如果存在返回非0不存在返回0也可以进行判断。选择习惯的方式即可。
3.3习题
链接两个数组交集 题目要求
代码加解析
//主要思想是利用set进行去重
//1先用set1存储nums1的值比如[1,2,2,1]-[1,2]set去重
//2定义一个set2,如果nums2的值在set1中可以找到就插入set2中
//注意因为nums2中可能存在多个相同值故用set可以进行去重
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint set_exist;setint result;for(auto e : nums1){set_exist.insert(e);}for(auto e : nums2){if(set_exist.find(e) ! set_exist.end()) //如果存在{result.insert(e);}}return vectorint(result.begin(), result.end());}
};//这个题也可以先去重加排序
//交集1不相等小的加加2相等是交集同时加加
//差集1不相等小的是差集小的加加2相等都不是差集同时加加 3一方走完剩下的都是差集4.multiset
multiset和set使用几乎一致唯一的不同就是允许键值冗余。
迭代器遍历依然可以得到有序序列count()接口对multiset非常重要multiset的find()查找返回的是中序遍历的第一个元素。multiset可以对存在重复元素的序列排序。 5.map
5.1一些注意点
在内部map中的元素总是按照键值key进行比较排序的和value无关。map不允许键值冗余map中的键值对是唯一的。利用迭代器遍历可以得到有序序列不过是按key来排序。map不允许修改key但可以修改value。支持修改键值会无法维护二叉搜索树结构。map中查找某个元素时间复杂度为logN 5.2map的使用
1模板参数
2构造
函数声明功能map (const key_compare comp key_compare(), const allocator_type alloc allocator_type())空构造map (InputIterator first, InputIterator last, 后面和空构造一样)迭代器区间构造map (const map x)拷贝构造
3迭代器
函数声明功能iterator begin()返回set中起始位置元素的迭代器iterator end()返回set中最后一个元素后面的迭代器reverse_iterator rbegin()反向迭代器返回end()reverse_iterator rend()反向迭代器返回begin()的前一个位置
4容量
函数声明功能bool empty ( ) const检测set是否为空空返回true否则返回falsesize_type size() const返回set中有效元素的个数
5增加、删除、修改、查找
函数声明功能pairiterator,bool insert ( const value_type x )在map中插入键值对x注意x是一个键值对返回值也是键值对iterator代表新插入元素的位置bool代表是否插入成功void erase ( iterator position)删除对应position位置的元素size_type erase ( const key_type x )删除map中键值为x的元素返回删除的元素的个数void erase ( iterator first, iterator last )删除map中[first, last)区间中的元素iterator find ( const key_type x ) const返回map中键值为x的元素的迭代器不存在返回end()size_type count ( const key_type x ) const返回map中键值为x的元素的个数mapped_type operator[] (const key_type k)非常重要返回key对应的valuevoid swap ( map mp )交换两个map中的元素void clear ( )将map中的元素清空
几个注意点
这里的接口中最重要的就是operator[]因为[]不仅可以访问value还可以进行插入。 operator[]的原理是 用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中如果key已经存在插入失败如果不存在就进行插入。insert返回的键值对第一个元素就是元素对应的迭代器operator[]函数通过迭代器最后返回键值对中的value的引用。对map的迭代器解引用得到是键值对结构体设迭代器为x拿value的方式有两种。(*x).second或x-second。map判断键值对在不在的方式和前面set一致。 5.3习题
链接前k个高频单词 题目要求 代码加解析
//这里的核心思路
//1用map统计每个字符串出现次数
//2对键值对进行排序出现次数相同的要按字典序来排
// 因为键值对自带的比较规则是只按key排序的所以我们需要自定义排序比较方法
//其实只是访问的话unordered_map更加快速但unordered_map迭代器遍历无法保证有序
class compare
{
public:bool operator()(pairstring,int p1, pairstring,int p2) const{if(p1.second p2.second){//出现次数相同按字典序排return p1.first p2.first;}else{//要排降序按大于排return p1.second p2.second;}}
};
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {mapstring, int count_map; //用map统计for(int i 0; i words.size(); i){count_map[words[i]] ;}//排序降序vectorpairstring,int result(count_map.begin(), count_map.end());;sort(result.begin(),result.end(),compare());vectorstring ret;for(int i 0; i k; i)ret.push_back(result[i].first);return ret;}
};
//也可以利用set进行排序
// setpairstring, int, compare sort_set(count_map.begin(), count_map.end());
// vectorstring ret;
// auto it sort_set.begin();
// while(k--)
// {
// ret.push_back(it-first);
// it;
// }
// return ret;6.multimap
multimap和map使用几乎一致最大的不同就是允许键值冗余。
multimap没有支持operator[]。原因是存在多个同键值的键值对不知道取谁的value。迭代器遍历依然可以得到有序序列。count()接口对multimap非常重要。multimap的find()查找返回的是中序遍历的第一个元素。multimap可以对存在重复元素的序列排序。
