h5 移动 网站 开发,石家庄最新轨迹,域名138查询网,网站如何布局文章目录 1. 序列式容器和关联式容器2. set系列的使用2.1 set和multiset参考文档2.2 set类的介绍2.3 set的构造和迭代器构造函数#xff1a;双向迭代器迭代器#xff1a; 2.4 set的增删查2.5 insert和迭代器遍历使用样例#xff1a;2.6 find和erase使用样例#xff1a;2.7 … 文章目录 1. 序列式容器和关联式容器2. set系列的使用2.1 set和multiset参考文档2.2 set类的介绍2.3 set的构造和迭代器构造函数双向迭代器迭代器 2.4 set的增删查2.5 insert和迭代器遍历使用样例2.6 find和erase使用样例2.7 multiset和set的差异2.8 349. 两个数组的交集 - 力扣LeetCode2.9 142. 环形链表 II - 力扣LeetCode 3. map系列的使用3.1 map和multimap参考文档3.2 map类的介绍3.3 pair类型介绍3.4 map的构造3.5 map的增删查3.6 map的数据修改3.7 构造遍历及增删查使用样例3.8 map的迭代器和[]功能样例3.9 multimap和map的差异3.10 138. 随机链表的复制 - 力扣LeetCode3.11 692. 前K个高频单词 - 力扣LeetCode解决思路1解决思路2 1. 序列式容器和关联式容器
前面我们已经接触过STL中的部分容器如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换一下他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红黑树红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构map是key/value搜索场景的结构。 2. set系列的使用
2.1 set和multiset参考文档
https://legacy.cplusplus.com/reference/set/ 2.2 set类的介绍 set的声明如下T就是set底层关键字的类型 set默认要求T支持小于比较如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数 set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。 一般情况下我们都不需要传后两个模版参数。 set底层是用红黑树实现增删查效率是O(logN) 迭代器遍历是走的搜索树的中序所以是有序的。 前面部分我们已经学习了vector/list等容器的使用STL容器接口设计高度相似所以这里我们就不再一个接口一个接口的介绍而是直接挑比较重要的接口进行介绍。
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type
class set; // 声明这是一个名为set的类这是C STL中set容器的模板声明 template ... - 这是一个模板类声明包含三个模板参数 第一个参数 class T 这是set存储的元素类型也是key和value的类型(在set中key就是value)必须显式指定没有默认值 第二个参数 class Compare lessT 用于元素比较的仿函数类型默认使用lessT即按升序排序你可以自定义比较器来改变排序方式 第三个参数 class Alloc allocatorT 内存分配器类型默认使用标准allocator通常不需要修改此参数 2.3 set的构造和迭代器
set的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历遍历默认按升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围for,set的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。
// empty (1) 无参默认构造
explicit set (const key_compare comp key_compare(),const allocator_type alloc allocator_type());
// range (2) 迭代器区间构造
template class InputIteratorset (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type allocator_type());// copy (3) 拷贝构造
set (const set x);
// initializer list (5) initializer 列表构造
set (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();构造函数
默认构造函数
explicit set (const key_compare comp key_compare(),const allocator_type alloc allocator_type());创建空setexplicit防止隐式转换可选参数比较器和分配器key_compare comp key_compare() 比较器参数默认是lessT用于维护set的元素顺序 allocator_type alloc allocator_type() 内存分配器参数默认使用std::allocator负责set内存的分配和释放
迭代器区间构造
template class InputIterator
set (InputIterator first, // 起始迭代器InputIterator last, // 结束迭代器const key_compare comp key_compare(), // 可选的比较器const allocator_type allocator_type() // 可选的分配器
);用迭代器范围内的元素构造set常用于从其他容器构造settemplate class InputIterator 接受任何满足InputIterator输入迭代器要求的迭代器类型可以是来自不同容器的迭代器只要它们指向的元素类型可以转换为set的元素类型
拷贝构造
set (const set x);复制另一个set创建新set
初始化列表构造
set (initializer_listvalue_type il, // 初始化列表const key_compare comp key_compare(), // 可选的比较器const allocator_type alloc allocator_type() // 可选的分配器
);使用初始化列表构造set 双向迭代器
iterator - a bidirectional iterator to const value_type 描述的是set迭代器的特性 双向迭代器(bidirectional iterator) 可以前后移动和–操作不支持随机访问不能n或-n移动方向向前()或向后(–) const value_type set中的元素不能通过迭代器修改这是因为修改可能破坏set的有序性
示例代码
setint s {1, 2, 3, 4, 5};// 正确用法
setint::iterator it s.begin();
cout *it; // 可以读取
it; // 可以向前
--it; // 可以向后// 错误用法
*it 10; // 编译错误不能修改元素
it 2; // 编译错误不支持随机访问
it it 2; // 编译错误不支持随机访问// 正确的遍历方式
for(setint::iterator it s.begin(); it ! s.end(); it) {cout *it ; // 只能读取不能修改
}// 现代C的简化写法
for(const auto element : s) {cout element ;
}与vector的随机访问迭代器相比
vectorint v {1, 2, 3, 4, 5};
vectorint::iterator vit v.begin();vit 2; // vector支持随机访问
*vit 10; // vector允许修改元素迭代器
正向迭代器
iterator begin(); // 指向第一个元素
iterator end(); // 指向最后一个元素之后的位置反向迭代器
reverse_iterator rbegin(); // 指向最后一个元素
reverse_iterator rend(); // 指向第一个元素之前的位置使用示例
// 不同构造方式
setint s1; // 默认构造
setint s2({1,2,3,4}); // 初始化列表构造
vectorint vec {1,2,3,4};
setint s3(vec.begin(), vec.end()); // 迭代器区间构造
setint s4(s3); // 拷贝构造// 迭代器使用
for(auto it s1.begin(); it ! s1.end(); it) {// 正向遍历
}for(auto it s1.rbegin(); it ! s1.rend(); it) {// 反向遍历
}2.4 set的增删查
set的增删查关注以下几个接口即可
Member types
key_type - The first template parameter (T)
value_type - The first template parameter (T)// 单个数据插入如果已经存在则插入失败
pairiterator,bool insert (const value_type val);
// 列表插入已经在容器中存在的值不会插入
void insert (initializer_listvalue_type il);
// 迭代器区间插入已经在容器中存在的值不会插入
template class InputIteratorvoid 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;2.5 insert和迭代器遍历使用样例
#includeiostream
#includeset // 包含set容器头文件
using namespace std;int main()
{// set默认情况// 1. 去重相同元素只保留一个// 2. 升序使用lessT比较器从小到大排序setint s;// 如果想降序可以使用greaterint比较器//setint, greaterint s; // 注释掉的降序写法// 插入元素重复的5只会保存一次s.insert(5);s.insert(2);s.insert(7);s.insert(5); // 这个5会插入失败因为已经存在// 使用迭代器遍历//setint::iterator it s.begin(); // 完整的迭代器类型声明auto it s.begin(); // 使用auto自动推导类型while (it ! s.end()){// set中的元素不能修改因为修改可能会破坏有序性// *it 1; // 错误set迭代器指向的元素是只读的cout *it ; // 只能读取元素it; // 迭代器移动到下一个位置}cout endl;// 使用初始化列表插入多个元素// 如果元素已存在如2则该元素插入失败// 新元素如3,8,9会插入并保持有序s.insert({ 2,8,3,9 });// 使用范围for循环遍历for (auto e : s){cout e ;}cout endl;// 创建string类型的set// 使用初始化列表构造setstring strset { sort, insert, add };// string比较规则// 1. 按字典序ASCII码比较// 2. 从第一个字符开始按位比较ASCII值// 输出会按字典序排列add insert sortfor (auto e : strset){cout e ;}cout endl;return 0;
}补充说明 set的特性 元素唯一性去重自动排序元素不可修改const 排序规则 默认使用lessT升序排序可以使用greaterT或自定义比较器实现降序或其他排序方式 string的排序 按字典序比较即ASCII码值的大小例如“add” “insert” “sort” 迭代器 set的迭代器是只读的不能通过迭代器修改元素因为修改可能破坏set的有序性 2.6 find和erase使用样例
#includeiostream
#includeset // 包含set容器头文件
using namespace std;int main()
{// 使用初始化列表构造set// set会自动排序并去重{2,4,5,7,8,9}setint s { 4,2,7,2,8,5,9 }; // 使用范围for循环遍历set中的元素for (auto e : s){cout e ; // 输出每个元素}cout endl;// 删除最小值(即第一个元素)// s.begin()返回指向第一个元素的迭代器s.erase(s.begin());// 再次遍历输出set中的元素for (auto e : s){cout e ;}cout endl;// 方式1直接删除值为x的元素int x;cin x;// erase返回实际删除的元素个数存在则返回1不存在返回0int num s.erase(x);if (num 0){cout x 不存在 endl;}// 输出删除后的结果for (auto e : s){cout e ;}cout endl;// 方式2先查找再删除cin x;// find返回指向找到元素的迭代器如果没找到返回end()auto pos s.find(x);if (pos ! s.end()) // 找到了{s.erase(pos); // 使用迭代器删除元素}else{cout x 不存在 endl;}// 输出删除后的结果for (auto e : s){cout e ;}cout endl;// 两种查找方式的比较// 1. 算法库的find遍历查找时间复杂度O(N)auto pos1 find(s.begin(), s.end(), x); // 2. set容器自带的find二叉搜索树查找时间复杂度O(logN)auto pos2 s.find(x); // 使用count间接实现快速查找// count对于set来说返回值只可能是0或1因为set不允许重复cin x;if (s.count(x)) // 如果count返回1表示存在{cout x 在 endl;}else // 如果count返回0表示不存在{cout x 不存在 endl;}return 0;
}#includeiostream
#includeset // 包含set容器头文件
using namespace std;int main()
{// 创建空的set容器std::setint myset;// 插入1-9的10倍数到set中for (int i 1; i 10; i)myset.insert(i * 10); // 插入后set内容10 20 30 40 50 60 70 80 90// 遍历并打印set中的所有元素for (auto e : myset){cout e ;}cout endl;// lower_bound(key)返回指向大于或等于key的第一个元素的迭代器// 这里返回指向30的迭代器因为30是第一个大于等于30的元素auto itlow myset.lower_bound(30);// upper_bound(key)返回指向大于key的第一个元素的迭代器// 这里返回指向70的迭代器因为70是第一个大于60的元素auto itup myset.upper_bound(60);// erase(first, last)删除[first,last)区间的所有元素// 这里删除[30,60]这个闭区间的所有元素// 即删除30,40,50,60这些元素myset.erase(itlow, itup);// 再次遍历打印检查删除结果// 预期输出10 20 70 80 90for (auto e : myset){cout e ;}cout endl;return 0;
}补充说明 lower_bound和upper_bound都是基于二分搜索实现的时间复杂度为O(logN)区间[itlow,itup)是一个左闭右开区间 itlow指向第一个30的元素即30itup指向第一个60的元素即70因此这个区间包含了30,40,50,60这些元素 如果要删除的key不存在lower_bound和upper_bound会返回最接近的位置 如果key小于所有元素返回begin()如果key大于所有元素返回end() 2.7 multiset和set的差异
multiset和set的使用基本完全类似主要区别点在于multiset支持值冗余那么insert/find/count/erase都围绕着支持值冗余有所差异具体参看下面的样例代码理解。
#includeiostream
#includeset // 包含set/multiset容器头文件
using namespace std;int main()
{// multiset特点// 1. 有序默认按照小于比较从小到大排序// 2. 允许重复值存在// 排序后结果为{2,2,4,4,4,4,5,7,8,9}multisetint s { 4,2,7,2,4,8,4,5,4,9 };// 使用迭代器遍历multiset中的所有元素auto it s.begin(); // 获取指向第一个元素的迭代器while (it ! s.end()) // 当迭代器未到达末尾时继续循环{cout *it ; // 解引用迭代器输出当前元素it; // 迭代器移动到下一个位置}cout endl;// 查找元素xint x;cin x;// find在multiset中返回第一个等于x的元素位置// 如果有多个相同元素find返回中序遍历遇到的第一个auto pos s.find(x);// 通过迭代器遍历所有等于x的元素// 因为multiset是有序的所有相等的元素都是相邻的while (pos ! s.end() *pos x){cout *pos ; // 输出当前找到的xpos; // 移动到下一个位置继续查找}cout endl;// count返回元素x在multiset中出现的次数// 而在set中count只会返回0或1cout s.count(x) endl;// erase删除所有值等于x的元素// 而在set中最多只会删除一个元素s.erase(x);// 使用范围for循环遍历删除后的结果for (auto e : s){cout e ;}cout endl;return 0;
}multiset与set的主要区别 multiset允许重复元素set不允许find在multiset中返回第一个匹配的元素位置count在multiset中返回实际出现次数在set中只返回0或1erase在multiset中删除所有匹配的元素在set中最多删除一个 2.8 349. 两个数组的交集 - 力扣LeetCode
349. 两个数组的交集 - 力扣LeetCode class Solution {
public:// 函数功能求两个数组的交集// 参数两个整型vector数组的引用// 返回值包含交集元素的vectorvectorint intersection(vectorint nums1, vectorint nums2) {// 构造两个set利用set自动去重和排序的特性// 用nums1和nums2的迭代器区间初始化setsetint s1(nums1.begin(), nums1.end()); // nums1中的不重复元素setint s2(nums2.begin(), nums2.end()); // nums2中的不重复元素// 创建结果数组用于存储交集元素vectorint ret;// 获取两个set的起始迭代器auto it1 s1.begin();auto it2 s2.begin();// 同时遍历两个set直到其中一个遍历完while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2) {// 如果s1当前元素小移动s1的迭代器it1;}else if(*it1 *it2){// 如果s2当前元素小移动s2的迭代器it2;}else // *it1 *it2{// 相等说明是交集元素ret.push_back(*it1); // 将交集元素加入结果数组// 两个迭代器都要往后移动it1;it2;}}return ret; // 返回结果数组}
};算法思路解析 预处理 将两个数组转换为set实现去重和排序时间复杂度O(NlogN)空间复杂度O(N) 求交集 利用set有序的特性用双指针迭代器同时遍历两个set类似归并排序的思路比较两个当前元素 如果s1当前元素小移动s1迭代器如果s2当前元素小移动s2迭代器如果相等就是交集元素加入结果数组两个迭代器都移动 时间复杂度O(min(N,M))N和M是两个set的大小 优势 利用set的特性自动去重和排序双指针遍历的方式效率高代码简洁易懂 2.9 142. 环形链表 II - 力扣LeetCode
142. 环形链表 II - 力扣LeetCode
数据结构初阶阶段我们通过证明一个指针从头开始走一个指针从相遇点开始走会在入口点相遇理解证明都会很麻烦。这里我们使用set查找记录解决非常简单方便这里体现了set在解决一些问题时的价值完全是降维打击。 class Solution {
public:// 函数功能检测链表中的环并返回环的入口节点// 参数链表头节点指针// 返回值如果有环返回环的入口节点如果无环返回nullptrListNode *detectCycle(ListNode *head) {// 创建一个存储ListNode指针的set容器// 用于记录已经访问过的节点地址setListNode* s;// cur指针用于遍历链表ListNode* cur head;// 遍历链表while(cur){// 尝试将当前节点地址插入set中// insert返回一个pair:// - first是一个迭代器指向插入位置// - second是一个bool值表示插入是否成功// - true表示插入成功之前没有这个元素// - false表示插入失败已经存在这个元素auto ret s.insert(cur);// 如果插入失败(ret.second为false)// 说明这个节点之前已经访问过// 也就是找到了环的入口if(ret.second false)return cur; // 返回环的入口节点// 继续遍历下一个节点cur cur-next;}// 如果遍历完整个链表都没有找到重复节点// 说明链表中没有环return nullptr;}
};算法思路解析 基本思想 用set存储已经访问过的节点地址如果某个节点地址已经在set中存在说明找到了环 具体步骤 创建set存储节点地址遍历链表尝试将每个节点地址插入set如果插入失败说明这个地址之前已存在即找到环的入口如果遍历结束都没有重复地址说明无环 时间复杂度分析 O(N)N为链表节点数每个节点最多被访问一次set的插入操作是O(logN) 空间复杂度分析 O(N)需要额外空间存储访问过的节点地址 3. map系列的使用
3.1 map和multimap参考文档
https://legacy.cplusplus.com/reference/map/ 3.2 map类的介绍
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_type
class map;Key - key_type键类型
template class Key // 第一个模板参数用作map中的键必须支持比较操作能够排序不可重复
T - mapped_type值类型
class T // 第二个模板参数存储的实际数据类型可以修改没有特殊要求
Compare - key_compare比较器
class Compare lessKey // 第三个模板参数有默认值用于键的排序默认使用lessKey可自定义比较规则
Alloc - allocator_type分配器
class Alloc allocatorpairconst Key,T // 第四个模板参数有默认值内存分配器注意是pair的分配器键值对pair中的Key是const的 3.3 pair类型介绍
map底层的红黑树节点中的数据使用pairKey, T存储键值对数据。
// value_type定义了map中存储的键值对类型
// Key是const的防止键被修改
typedef pairconst Key, T value_type;// pair是一个通用的模板结构体用于存储两个不同类型的值
template class T1, class T2
struct pair
{// 定义first成员的类型别名typedef T1 first_type;// 定义second成员的类型别名typedef T2 second_type;// pair的两个公有成员变量T1 first; // 第一个成员T2 second; // 第二个成员// 默认构造函数// 使用T1和T2的默认构造函数初始化first和secondpair(): first(T1()), second(T2()){}// 带参数的构造函数// param a: first成员的初始值// param b: second成员的初始值pair(const T1 a, const T2 b): first(a), second(b){}// 拷贝构造函数模板// 允许从不同类型的pair进行构造如果类型可以转换// param pr: 源pair对象// template U: 源pair的first类型// template V: 源pair的second类型templateclass U, class V pair (const pairU,V pr): first(pr.first), second(pr.second){}
};// 辅助函数创建pair对象的便捷方式
// 通过类型推导自动确定pair的类型
// param x: 第一个值
// param y: 第二个值
// return: 返回构造好的pair对象
template class T1,class T2
inline pairT1,T2 make_pair (T1 x, T2 y)
{return ( pairT1,T2(x,y) );
}为什么写成pair(): first(T1()), second(T2())而不是pair(): first(T1), second(T2)
T1() vs T1 的区别
pair(): first(T1()), second(T2()) // 值初始化
pair(): first(T1), second(T2) // 默认初始化对于不同类型的影响
// 基本类型(int, double等)
int n1(); // 值初始化 - 0
int n2; // 默认初始化 - 未定义值// 示例
pairint, int p1; // 使用T1()
// p1.first 0, p1.second 0pairint, int p2; // 如果使用T1
// p1.first 未定义值, p1.second 未定义值3.4 map的构造
map的构造我们关注以下几个接口即可。
map的支持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围formap支持修改value数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。
// empty (1) 无参默认构造
explicit map (const key_compare comp key_compare(),const allocator_type alloc allocator_type());
// - explicit防止隐式转换
// - key_compare默认是lessKey
// - 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 列表构造
// 4. 初始化列表构造函数
map (// 接收初始化列表作为参数,类型为 initializer_list// 其中 value_type 通常是 pairconst Key, T// 例如: {key, value} 这样的初始化形式initializer_listvalue_type il,// 接收比较函数对象,用于定义键的排序规则// key_compare 默认是 lessKey// comp 参数可选,如果不传则使用默认构造的 key_compareconst key_compare comp key_compare(),// 接收内存分配器,用于管理map的内存分配// allocator_type 是分配器类型// alloc 参数可选,如果不传则使用默认构造的 allocator_typeconst allocator_type alloc allocator_type()
);// 迭代器是一个双向迭代器
// 这表示
// 1. 迭代器是双向的
// 2. 键是const的不能修改
// 3. value_type是pairconst Key, T类型
iterator - a bidirectional iterator to const value_type// 正向迭代器// 正向迭代器声明
iterator begin(); // 返回指向第一个元素的迭代器
iterator end(); // 返回指向最后一个元素后面的迭代器// 反向迭代器声明
reverse_iterator rbegin(); // 返回指向最后一个元素的反向迭代器
reverse_iterator rend(); // 返回指向第一个元素前面的反向迭代器3.5 map的增删查
map的增删查关注以下几个接口即可
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.6 map的数据修改
前面我提到map支持修改mapped_type 数据不支持修改key数据修改关键字数据破坏了底层搜索树的结构。
map第一个支持修改的方式时通过迭代器迭代器遍历时或者find返回key所在的iterator修改map还有一个非常重要的修改接口operator[]但是operator[]不仅仅支持修改还支持插入数据和查找数据所以他是一个多功能复合接口
需要注意从内部实现角度map这里把我们传统说的value值给的是T类型typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
Member typeskey_type - The first template parameter (Key)mapped_type - The second template parameter (T)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 theelement 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.7 构造遍历及增删查使用样例
#includeiostream
#includemap
using namespace std;
int main()
{// initializer_list构造及迭代遍历mapstring, string dict { {left, 左边}, {right, 右边},{insert, 插入},{ string, 字符串 } };//mapstring, string::iterator it dict.begin();auto it dict.begin();while (it ! dict.end()){//cout (*it).first :(*it).second endl;// map的迭代基本都使用operator-,这里省略了一个-// 第一个-是迭代器运算符重载返回pair*第二个箭头是结构指针解引用取pair数据//cout it.operator-()-first : it.operator-()-second endl;cout it-first : it-second endl;it;}cout endl;// insert插入pair对象的4种方式对比之下最后一种最方便pairstring, string kv1(first, 第一个);dict.insert(kv1);dict.insert(pairstring, string(second, 第二个));dict.insert(make_pair(sort, 排序));dict.insert({ auto, 自动的 });// left已经存在插入失败dict.insert({ left, 左边剩余 });// 范围for遍历for (const auto e : dict){cout e.first : e.second endl;}cout endl;string str;while (cin str){auto ret dict.find(str);if (ret ! dict.end()){cout - ret-second endl;}else{cout 无此单词请重新输入 endl;}}// erase等接口跟set完全类似这里就不演示讲解了return 0;
} 3.8 map的迭代器和[]功能样例
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{// 利用find和iterator修改功能统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// 先查找水果在不在map中// 1、不在说明水果第一次出现则插入{水果, 1}// 2、在则查找到的节点中水果对应的次数auto ret countMap.find(str);if (ret countMap.end()){countMap.insert({ str, 1 });}else{ret-second;}}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0;
}#includeiostream
#includemap
#includestring
using namespace std;
int main()
{// 利用[]插入修改功能巧妙实现统计水果出现的次数string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (const auto str : arr){// []先查找水果在不在map中// 1、不在说明水果第一次出现则插入{水果, 0}同时返回次数的引用一下就变成1次了// 2、在则返回水果对应的次数countMap[str];}for (const auto e : countMap){cout e.first : e.second endl;}cout endl;return 0;
}#includeiostream
#includemap
#includestring
using namespace std;
int main()
{mapstring, string dict;dict.insert(make_pair(sort, 排序));// key不存在-插入 {insert, string()}dict[insert];// 插入修改dict[left] 左边;// 修改dict[left] 左边、剩余;// key存在-查找cout dict[left] endl;return 0;
}3.9 multimap和map的差异
multimap和map的使用基本完全类似主要区别点在于multimap支持关键值key冗余那么insert/find/count/erase都围绕着支持关键值key冗余有所差异这里跟set和multiset完全一样比如find时有多个key返回中序第一个。其次就是multimap不支持[]因为支持key冗余[]就只能支持插入了不能支持修改。 3.10 138. 随机链表的复制 - 力扣LeetCode
138. 随机链表的复制 - 力扣LeetCode
数据结构初阶阶段为了控制随机指针我们将拷贝结点链接在原节点的后面解决后面拷贝节点还得解下来链接非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中控制随机指针会非常简单方便这里体现了map在解决一些问题时的价值完全是降维打击。 class Solution {
public:// 函数功能深拷贝带随机指针的链表// 参数原链表的头节点指针// 返回值拷贝后的新链表的头节点指针Node* copyRandomList(Node* head) {// 创建map用于存储原节点到拷贝节点的映射关系// key: 原链表节点地址// value: 对应的拷贝节点地址mapNode*, Node* nodeMap;// copyhead指向拷贝链表的头节点// copytail指向拷贝链表的尾节点Node* copyhead nullptr, *copytail nullptr;// 第一次遍历复制节点值和next指针Node* cur head;while(cur){// 如果是第一个节点if(copytail nullptr){// 创建头节点copyhead copytail new Node(cur-val);}else{// 创建新节点并连接到尾部copytail-next new Node(cur-val);copytail copytail-next;}// 建立原节点和拷贝节点的映射关系nodeMap[cur] copytail;// 继续处理下一个节点cur cur-next;}// 第二次遍历处理random指针cur head; // cur指向原链表Node* copy copyhead; // copy指向拷贝链表while(cur){// 如果原节点的random为空if(cur-random nullptr){copy-random nullptr;}else{// 通过map找到原节点random指向的节点对应的拷贝节点copy-random nodeMap[cur-random];}// 继续处理下一个节点cur cur-next;copy copy-next;}return copyhead;}
};算法思路解析 整体思路 分两次遍历完成深拷贝第一次遍历复制节点值和next指针同时建立映射关系第二次遍历处理random指针 具体步骤 第一次遍历 复制每个节点的值建立next连接将原节点和对应的拷贝节点存入map 第二次遍历 根据原节点的random指向通过map找到对应的拷贝节点建立random连接 时间复杂度 O(N)需要两次遍历链表map的插入和查找操作是O(logN) 空间复杂度 O(N)需要额外的map存储映射关系 3.11 692. 前K个高频单词 - 力扣LeetCode
692. 前K个高频单词 - 力扣LeetCode
本题目我们利用map统计出次数以后返回的答案应该按单词出现频率由高到低排序有一个特殊要求如果不同的单词有相同出现频率按字典顺序排序。
解决思路1
用排序找前k个单词因为map中已经对key单词排序过也就意味着遍历map时次数相同的单词字典序小的在前面字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求但是sort底层是快排是不稳定的所以我们要用stable_sort他是稳定的。 解决思路1
class Solution {
public:// 定义仿函数用于排序规则的比较struct Compare{// 重载operator()实现比较规则// 参数两个pairstring,int的常引用// 返回值bool表示x是否应该排在y前面bool operator()(const pairstring, int x, const pairstring, int y)const{// 按照频率降序排列即频率高的在前return x.second y.second;}};// 函数功能找出字符串数组中出现频率最高的k个字符串// 参数字符串数组的引用和需要返回的个数k// 返回值包含前k个高频字符串的vectorvectorstring topKFrequent(vectorstring words, int k) {// 统计每个字符串出现的频率// key: 字符串// value: 出现次数mapstring, int countMap;for(auto e : words){countMap[e]; // 统计频率}// 将map中的数据转换为pair的vector// 便于排序vectorpairstring, int v(countMap.begin(), countMap.end());// 使用stable_sort保持相同频率字符串的原有顺序// Compare()定义排序规则按照频率降序排列stable_sort(v.begin(), v.end(), Compare());// sort和stable_sort的区别// sort不保证相等元素的相对位置// stable_sort保证相等元素的相对位置不变//sort(v.begin(), v.end(), Compare());// 取排序后的前k个字符串vectorstring strV;for(int i 0; i k; i){strV.push_back(v[i].first); // 只需要字符串不需要频率}return strV;}
};算法思路解析 步骤分解 统计频率使用map记录每个字符串出现的次数转换数据将map转为pair的vector便于排序排序按照频率降序排列获取结果取前k个字符串 关键点解析 使用map统计频率的优势 自动去重按照key排序高效的查找和统计 Compare仿函数 定义排序规则按照pair的second频率降序排序可以方便地修改排序规则 stable_sort vs sort stable_sort能保持相同频率字符串的原有顺序在处理相同频率的字符串时更稳定 时间复杂度分析 统计频率O(NlogM)N是words长度M是不同字符串个数排序O(MlogM)M是不同字符串个数总体O(NlogM MlogM) 空间复杂度 O(M)M是不同字符串个数 解决思路2
将map统计出的次数的数据放到vector中排序或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的字典序小的在前面。
class Solution {
public:// 定义仿函数实现自定义排序规则struct Compare{bool operator()(const pairstring, int x, const pairstring, int y)const{// 排序规则// 1. 按频率降序排序频率高的在前// 2. 如果频率相同按字典序升序排序字母顺序小的在前return x.second y.second || // 频率降序(x.second y.second x.first y.first); // 频率相同时字典序升序}};// 函数功能找出字符串数组中出现频率最高的k个字符串// 要求1. 按照出现频率降序排列// 2. 频率相同时按照字典序升序排列vectorstring topKFrequent(vectorstring words, int k) {// 统计每个字符串出现的频率mapstring, int countMap;for(auto e : words){countMap[e];}// 将map转换为pair的vector以便排序vectorpairstring, int v(countMap.begin(), countMap.end());// 使用自定义的Compare仿函数排序// 不需要使用stable_sort因为已经在Compare中处理了相等情况sort(v.begin(), v.end(), Compare());// 取前k个字符串vectorstring strV;for(int i 0; i k; i){strV.push_back(v[i].first);}return strV;}
};算法思路解析 关键改进 在Compare仿函数中增加了第二个排序条件当频率相同时按字典序排序 Compare仿函数详解 x.second y.second || // 条件1频率降序
(x.second y.second x.first y.first) // 条件2频率相同时字典序升序条件1优先按频率降序排序条件2频率相同时按字符串字典序升序排序 不再需要stable_sort 因为Compare仿函数已经完整定义了相等情况的处理规则使用普通的sort即可 class Solution {
public:// 定义仿函数为优先级队列提供比较规则struct Compare{bool operator()(const pairstring, int x, const pairstring, int y)const{// 注意priority_queue默认是大顶堆但比较规则是相反的// 如果要实现次数降序反而要用小于号// 如果要实现字典序升序反而要用大于号return x.second y.second || // 频率降序(x.second y.second x.first y.first); // 频率相同时字典序升序}};vectorstring topKFrequent(vectorstring words, int k) {// 统计词频mapstring, int countMap;for(auto e : words){countMap[e];}// 创建优先级队列// 模板参数// 1. 存储的元素类型pairstring,int// 2. 底层容器vector// 3. 比较规则Compare仿函数priority_queuepairstring, int, vectorpairstring, int, Compare p(countMap.begin(), countMap.end());// 取出前k个元素vectorstring strV;for(int i 0; i k; i){strV.push_back(p.top().first); // 只需要单词不需要频率p.pop();}return strV;}
};算法思路解析 关键点优先级队列的特性 priority_queue默认是大顶堆但其比较规则与直觉相反 如果a b返回true则a排在b后面如果a b返回false则a排在b前面 Compare仿函数详解 x.second y.second || // 频率比较
(x.second y.second x.first y.first) // 字典序比较频率比较用号实际效果是频率高的在队列顶部字典序比较用号实际效果是字典序小的在顶部 处理流程 统计词频使用map记录每个单词出现次数构建优先级队列 直接用map的迭代器范围构造自动按照Compare规则排序 获取结果 连续k次取出队列顶部元素每次取出后删除顶部元素 则是相反的 // 如果要实现次数降序反而要用小于号 // 如果要实现字典序升序反而要用大于号 return x.second y.second || // 频率降序 (x.second y.second x.first y.first); // 频率相同时字典序升序 } };