建站申请,交互性强的网站,wordpress单位内网做网站,电脑培训班有哪些科目目录
关联式容器
概念
键值对
树形关联式容器
set
介绍
定义方式
使用
map
介绍
使用 multiset
介绍
使用
multimap
介绍
使用
相关的OJ题
前K个高频单词 关联式容器
概念 我们之前接触过的一些容器#xff0c;比如#xff1a;vector、list、deque、forwa…目录
关联式容器
概念
键值对
树形关联式容器
set
介绍
定义方式
使用
map
介绍
使用 multiset
介绍
使用
multimap
介绍
使用
相关的OJ题
前K个高频单词 关联式容器
概念 我们之前接触过的一些容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 键值对
键值对是关联式容器特殊的结构。
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)
{}
};树形关联式容器
map、set、multimap、multiset。这些都是树形关联式容器因为他们的底层都是平衡搜索树红黑树容器中的元素都是有序的。
set
介绍 set是按照一定次序存储元素的容器。在set中元素的value也标识它并且每个value必须是唯一的。set中的元素不能在容器中修改元素总是const因为底层是平衡二叉树如果修改可能会破坏平衡二叉树的性质。在内部set中的元素总是按照其内部比较对象类型比较所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层使用平衡二叉树红黑树实现的。与map/multimap不同map/multimap中存储的是真正的键值对key,valueset中只放value但在底层实际存放的是由value,value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复因此可以使用set进行去重不可以重复的原因也是底层是平衡二叉树。使用set中的元素默认按照小于来比较。set中查找某个元素时间复杂度为log2 nset中的元素不允许修改因为底层是平衡二叉树如果修改的话很可能会破坏平衡二叉树的结构。注意平衡二叉树AVL是一种特殊的搜索二叉树BST
定义方式
//构造空容器
setint s1;//拷贝构造set容器
setint s2(s1);//使用迭代器拷贝某一段内容
string str(abcdef);
setchar s3(str.begin(),str.end());//比较方式指定为大于
setint,greaterint s4;
使用 Compare比较容器set默认按照小于来比较如果要对自定义类型进行比较的时候可以传入自定义的比较容器。
详细见代码
void test_set1()
{setint s;//插入s.insert(3);s.insert(2);s.insert(1);s.insert(1);s.insert(6);s.insert(7);s.insert(4);//利用迭代器去遍历set//setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;//利用范围for去遍历for (auto e : s){cout e ;}cout endl;//查找-找到就返回该元素的迭代器 否则返回end//两种find的查找方式是不一样的//O(logN) 这个是根据树的特殊结构来查找的auto pos s.find(3);//O(N) 暴力查找//auto pos find(s.begin(), s.end(), 3);if (pos ! s.end()){s.erase(pos);}//删除 //有就删没有就不操作//s.erase(4)像这种是有返回值的//删除成功就返回1删除失败返回0cout s.erase(4) endl;cout s.erase(100) endl;for (auto e : s){cout e ;}cout endl;//count 返回该值在set里面的个数//其实count对set意义不大//但是对multiset意义更大//cout s.count(3) endl;}
注意这里只列举一些常用的set的操作。
map
介绍 map是关联式容器它按照特定的次序按照key来比较存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和唯一的标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key和value通过成员类型value_type绑定在一起并为其取别名为pairtypedef pair value_type在内部map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代即对map中的元素进行迭代时可以得到一个有序的序列。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为平衡二叉搜索树红黑树。使用 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)。
int main()
{//定义一个空容器mapstring, string dict;//插入key和valuedict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));//operator[]dict[迭代器] iterator;//插入修改dict[insert];//插入dict[insert] 插入;//修改cout dict[insert] endl;//查找如果不在就是插入//插入失败因为已经有key对应的值了//dict.insert(pairstring, string(右边, xxx));//make_pair是一个函数模板 可以根据你传入的值来推断具体的类型dict.insert(make_pair(字符串, string));//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.find(e);if (it countMap.end()){countMap.insert(make_pair(e, 1));//第一次遇见这个水果直接给对应的key的value值插入1}else{it-second;}}//用for循环进行遍历for (const auto kv : countMap){cout kv.first : kv.second endl;}return 0;
}
注意map是支持[]操作符的。
operator[]的原理是 用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中如果key已经存在插入失败insert函数返回该key所在位置的迭代器如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回。 multiset
介绍
multiset是按照特定顺序存储元素的容器其中元素是可以重复的。在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除。在内部multiset中的元素总是按照其内部比较规则类型比较所指示的特定严格弱排序准则进行排序。multiset底层结构是一个平衡二叉树红黑树。与set的区别是multiset中的元素是可以重复的set中value是唯一的。
使用
void test_set2()
{multisetint s;//插入 可以插入重复的值s.insert(2);s.insert(1);s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(3);s.insert(6);s.insert(7);s.insert(1);//setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;//注意//用来验证如果有多个相同的值的时候//find找到是中序遍历的第一个auto pos s.find(3);while (pos ! s.end()){cout *pos ;pos;}//两种find的查找方式是不一样的//O(logN)//auto pos s.find(3);//O(N)/*auto pos find(s.begin(), s.end(), 3);if (pos ! s.end()){s.erase(pos);}*///有就删没有就不操作//s.erase(4)像这种是有返回值的//删除成功就返回1删除失败返回0/*cout s.erase(4) endl;cout s.erase(100) endl;for (auto e : s){cout e ;}cout endl;*///count 返回该值在set里面的个数//其实count对set意义不大//但是对multiset意义更大cout s.count(3) endl;cout s.count(1) endl;
}注意multiset的find与set有所不同由于multiset中允许键值冗余所以multiset如果查找成功的话返回的是中序遍历该元素所出现的第一次的迭代器。
set中的count没什么意义但是在multiset中count非常有意义它能很好的计算出该元素在multiset容器中的具体数量。
multimap
介绍
multimap与set和multiset的区别非常相像在这里不多介绍。
multimap不支持[]因为multimap允许键值冗余[]不能确切的知道我们要访问的是哪个值。
multimap中的key是可以重复的。
使用
int main()
{multimapstring, string dict;dict.insert(make_pairstring, string(left, 左边));dict.insert(make_pairstring, string(left, 左边));dict.insert(make_pairstring, string(right, 右边));dict.insert(make_pair(string, 字符串));for (const auto kv : dict){cout kv.first : kv.second endl;}
}
相关的OJ题
前K个高频单词
题目地址
力扣https://leetcode.cn/problems/top-k-frequent-words/description/ 我们这里使用multimap非常契合我们的思路就是首先使用multimap特殊的性质允许键值冗余并且有两个键值。两个键值一个存放单词一个存放次数。
记录完毕数据之后使用次数进行排序如果有相同的就设置特殊的比较容器具进行字典序排序。
最后输出前十个。
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k){//为stable_sort来创建比较容器struct Compare{bool operator()(const pairint,stringl,const pairint,string r){return l.firstr.first;}};mapstring,int mapCount;//巧妙的使用了[] //不仅将words中的单词给插入进map并且还统计了次数for(auto kv: words){mapCount[kv];//访问key对应的value给value进行}vectorpairint,string v;//注意这里value与key换了位置为了保证排序的时候直接使用第一个键值进行排序for(auto kv : mapCount){v.push_back(make_pair(kv.second,kv.first));}//切记不要使用sort 因为sort底层为快排不稳定//然而stable_sort底层为归并稳定stable_sort(v.begin(),v.end(),Compare());vectorstring ret;for(size_t i0;ik;i){ret.push_back(v[i].second);}return ret;}
};
