建设银行网站邮箱,wordpress管理工具,公司企业黄页,在哪里查关键词排名我们之前已经学习过string,vector,list,queue,priority_queue等容器#xff0c;这些容器我们统称为序列式容器#xff0c;因为它们的数据的逻辑结构呈线性。因为这些容器中存储的数据即便二者之间发生交换#xff0c;也不会对原有的容器结构造成太大影响。
但上篇文章我们介…我们之前已经学习过string,vector,list,queue,priority_queue等容器这些容器我们统称为序列式容器因为它们的数据的逻辑结构呈线性。因为这些容器中存储的数据即便二者之间发生交换也不会对原有的容器结构造成太大影响。
但上篇文章我们介绍到了二叉搜索树如果之前有在leetcode上刷过题目的朋友肯定会遇到哈希表这一种题型标签。它的最简单的形式就是我们的鸽巢数组我们能够通过下标来快速索引目标值以O(1)的时间复杂度。这种容器其实就是我们今天所要介绍的关联式容器因为它们的位置和自身存储的值都有着密切关系一旦数据发生交换原有的容器结构将会造成极大的破坏我们先从最简单的set和multiset关联式容器开始介绍
一set系列容器
set - C Reference set的底层是一棵红黑树。但我们这里先暂且不介绍红黑树的模拟实现我们先来了解set系列容器的用法这会对我们之后文章模拟实现红黑树有很大帮助
1.1set类的介绍
set类的声明如下
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_typeclass set;
可以看到大致上与我们之前所学容器一致1.键值(k)类型2.升或降序(仿函数注意这里的反人设计我们在优先级队列处也知道传lessT建的是大堆而greaterT则是小堆这里也类似)。
其他的几点注意事项
set底层存储数据的内存是从空间配置器申请的如果需要可以⾃⼰实现内存池传给第三个参数。⼀般情况下我们都不需要传后两个模版参数set底层是⽤红⿊树实现增删查效率是O(logN)迭代器遍历是⾛的搜索树的中序所以是有序的。 1.2set的构造和迭代器
set的⽀持正向和反向迭代遍历遍历默认按升序顺序因为底层是⼆叉搜索树迭代器遍历⾛的中序⽀持迭代器就意味着⽀持范围forset的iterator和const_iterator都不⽀持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。
1.3set的增删查改
// 单个数据插⼊如果已经存在则插⼊失败
pairiterator, bool insert(const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert(initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert(InputIterator first, InputIterator last);
// 查找val返回val所在的迭代器没有找到返回end()
iterator find(const value_type val);
// 查找val返回Val的个数
size_type count(const value_type val) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除valval不存在返回0存在返回1
size_type erase(const value_type val);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等val位置的迭代器
iterator lower_bound(const value_type val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type val) const;
重点了解以上几个即可我们注意到上面出现了一个我们之前没有见过的新类型pair这个我们下面介绍map时会着重介绍。
这里读者可以自行下去进行实验与我们所学过的二叉搜索树大致用法相同。
1.3multiset与set的区别
set所存储的数据中不会出现重复的元素。而multiset允许重复元素的存在这就是这二者的最大区别。需要注意的是如果我们想要删除某一特定键值结点我们必须要传入它的迭代器位置而不是传入它的迭代器的值后者会把所有与输入键值相同的结点完全删除。
1.4以set的视角来看待两道力扣题
. - 力扣LeetCode
这道题要求我们去找两个数组的交集如果是我们还没有学set时我们的第一想法可能是先分别对两个数组进行排序然后利用双指针来找相等元素进行解决。但此时我们了解set中不能存在重复元素的特性后我们可以用以下的这种解法
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());auto i s1.begin(),j s2.begin();vectorint ans;while(i ! s1.end() j ! s2.end()){if(*i *j) i;else if(*i *j) j;else{ans.push_back(*i);i;j;}}return ans;}
};
虽然时间复杂度与前者别无二至但确实是一种在博主看来比较新颖的一种做法。 下面这道题我们在学习链表数据结构时做过就是leetcode的环形链表II当时我们第一次做的时候可能还废了点力气去推导为甚么快指针最后一定会与慢指针相遇且在环口处相遇。但这里如果用上了set那简直就是降维打击
. - 力扣LeetCode
class Solution {
public:ListNode *detectCycle(ListNode *head) {setListNode* s;ListNode* cur head;while(cur){auto ret s.insert(cur);if(ret.second false)return cur;cur cur-next;}return nullptr;}
};
简介明了而且在使用过set后会非常容易想到虽然要耗费额外的空间但在大家都会双指针的情况下这种方式是不是更新颖而且能够耗费更少的时间去推导呢所以不仅仅是对博主自己的建议也是对大家的建议或许我们选择解法时都会尽可能的选择最优算法但最优的算法往往没有那么容易想到或许我们退而求其次不追求极致的优化或许也会逊色于最优但却也能让人眼前一亮。
二Pair类型介绍
map底层的红⿊树节点中的数据使⽤pair存储键值对数据。 所以在介绍map之前我们先来了解一下pair。有助于我们接下来了解 map。
typedef pairconst Key, T value_type;
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){}templateclass U, class Vpair(const pairU, V pr) : first(pr.first), second(pr.second){}
};template class T1, class T2
inline pairT1, T2 make_pair(T1 x, T2 y)
{return (pairT1, T2(x, y));
} 现在我们转过来了解下set中的这串声明
// 单个数据插⼊如果已经存在则插⼊失败
pairiterator, bool insert(const value_type val);
我们知道在set中插入元素后根据我们以往的经验它应该是返回插入元素的下标。但这里又多了个bool。因此我们结合上面pair的定义可以大致推出无论是否插入成功insert函数都会返回插入元素的迭代器所在位置而bool类型数据则是记录插入是否成功
//比如我们有以下一个定义式
pairiterator,bool n Set.insert(9);//n.first ...:插入的数据的迭代器位置
//n.second true/false//插入成功/失败
三map系列容器 3.1map的定义
map - C Reference
map的声明如下Key就是map底层关键字的类型T是map底层value的类型set默认要求Key⽀持⼩于⽐较如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数map底层存储数据的 内存是从空间配置器申请的。⼀般情况下我们都不需要传后两个模版参数。map底层是⽤红⿊树实现增删查改效率是 O(logN) 迭代器遍历是⾛的中序所以是按key有序顺序遍历的。
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key, T //map::allocator_typeclass map; 3.2map的构造
map的⽀持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是⼆叉搜索树迭代器遍历⾛的中序。⽀持迭代器就意味着⽀持范围formap⽀持修改value数据不⽀持修改key数据修改关键字数据破坏了底层搜索树的结构。
// empty (1) ⽆参默认构造
explicit map(const key_compare comp key_compare(),const allocator_type alloc allocator_type());
// range (2) 迭代器区间构造
template class InputIterator
map(InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());
// copy (3) 拷⻉构造
map(const map x);
// initializer list (5) initializer 列表构造
map(initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());
// 迭代器是⼀个双向迭代器
iterator-a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
3.3map的增删查
map增接⼝,插⼊的pair键值对数据,跟set所有不同,但是查和删的接⼝只⽤关键字key跟set是完全类似的,不过find返回iterator,不仅仅可以确认key在不在,还找到key映射的value,同时通过迭代 还可以修改value。
Member types
key_type-The first template parameter(Key)
mapped_type-The second template parameter(T)
value_type-pairconst key_type, mapped_type
// 单个数据插⼊如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pairiterator, bool insert(const value_type val);
// 列表插⼊已经在容器中存在的值不会插⼊
void insert(initializer_listvalue_type il);
// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert(InputIterator first, InputIterator last);
// 查找k返回k所在的迭代器没有找到返回end()
iterator find(const key_type k);
// 查找k返回k的个数
size_type count(const key_type k) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除kk存在返回0存在返回1
size_type erase(const key_type k);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等k位置的迭代器
iterator lower_bound(const key_type k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound(const key_type k) const;
3.4map的数据修改
map第⼀个⽀持修改的⽅式时通过迭代器迭代器遍历时或者find返回key所在的iterator修改map 还有⼀个⾮常重要的修改接⼝operator[]但是operator[]不仅仅⽀持修改还⽀持插⼊数据和查找数据所以他是⼀个多功能复合接⼝需要注意从内部实现⻆度map这⾥把我们传统说的value值给的是T类型typedef为 mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。⽇常使⽤我们还是习惯将这⾥的T映射值叫做value。
value_type-pairconst key_type, mapped_type
// 查找k返回k所在的迭代器没有找到返回end()如果找到了通过iterator可以修改key对应的
//mapped_type值
iterator find(const key_type k);
// ⽂档中对insert返回值的说明
// The single element versions (1) return a pair, with its member pair::first
//set to an iterator pointing to either the newly inserted element or to the
//element with an equivalent key in the map.The pair::second element in the pair
//is set to true if a new element was inserted or false if an equivalent key
//already existed.
// insert插⼊⼀个pairkey, T对象
// 1、如果key已经在map中插⼊失败则返回⼀个pairiterator,bool对象返回pair对象
//first是key所在结点的迭代器second是false
// 2、如果key不在在map中插⼊成功则返回⼀个pairiterator,bool对象返回pair对象
//first是新插⼊key所在结点的迭代器second是true
// 也就是说⽆论插⼊成功还是失败返回pairiterator,bool对象的first都会指向key所在的迭
//代器
// 那么也就意味着insert插⼊失败时充当了查找的功能正是因为这⼀点insert可以⽤来实现
//operator[]
// 需要注意的是这⾥有两个pair不要混淆了⼀个是map底层红⿊树节点中存的pairkey, T另
//⼀个是insert返回值pairiterator, bool
pairiterator, bool insert(const value_type val);
mapped_type operator[] (const key_type k);
// operator的内部实现
mapped_type operator[] (const key_type k)
{// 1、如果k不在map中insert会插⼊k和mapped_type默认值同时[]返回结点中存储// mapped_type值的引⽤那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ 修改功能// 2、如果k在map中insert会插⼊失败但是insert返回pair对象的first是指向key结点的//迭代器返回值同时[]返回结点中存储mapped_type值的引⽤所以[]具备了查找 修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second;
} 3.5map与multimap的区别
multimap和map的使⽤基本完全类似主要区别点在于multimap⽀持关键值key冗余那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异这⾥跟set和multiset完全⼀样⽐如find时有多个key返回中序第⼀个。其次就是multimap不⽀持[]因为⽀持key冗余[]就只能⽀持插⼊了不能⽀持修改。
下面两道是可以使用map来解决的两道题目这里我们就不再给出解决方法了我们可以先用一般思路来做这两道题之后再用map相关知识来做能够对map有一个更深的了解:
. - 力扣LeetCode
. - 力扣LeetCode
