【C++】STL----map和set

🕗 发布于 2024-11-05 18:01 c++ 开发语言 数据结构

🔥个人主页🔥：孤寂大仙V
🌈收录专栏🌈：C++从小白到高手
🌹往期回顾🌹：[C++]二叉搜索树
🔖 流水不争，争的是滔滔不息

一、set和map的简介

在C++中，set和map是常用的关联容器，分别用于存储不重复的元素和键值对(key-value pairs)。它们都在和头文件中定义，并基于红黑树实现，具有对数时间复杂度的插入、查找和删除操作。

set

set：集合
set 是一个有序集合，其中的元素不重复，自动按升序排列（可以自定义比较函数）。

特点：

元素唯一性：set 不允许重复元素。
自动排序：插入的元素自动排序，默认按升序排列。
时间复杂度：插入、查找、删除的平均时间复杂度为 O(log n)。

map

map：映射
map 是一个有序字典，用于存储键值对，键唯一，且自动按键值升序排列（可自定义比较函数）。

特点：

键的唯一性：map 中键不能重复。
自动排序：按键值升序排列。
时间复杂度：插入、查找、删除的平均时间复杂度为 O(log n)。

二、序列式容器和关联式容器

STL中，常见的sting、vector、list等都是序列式容器。序列式逻辑结构为线性序列的数据结构，两个位置存储的值一般没有紧密的关联关系。比如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

三、set

在这里插入图片描述

1.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 InputIterator>
  set (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_list<value_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();

2.set的增删查

set的大部分接口不常用，只有插入、删除、查找、比较常用。

 // 单个数据插⼊，如果已经存在则插⼊失败
 pair<iterator,bool> insert (const value_type& val);
 
 // 列表插⼊，已经在容器中存在的值不会插⼊
 void insert (initializer_list<value_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);
 
 // 删除val，val不存在返回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;

set的插入

set容器额普通插入的用法

int main()
{
//set插入使用样例
set<int> s;
s.insert(6);
s.insert(8);
s.insert(5);
s.insert(2);
s.insert(9);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//输出2 5 6 8 9
return 0;
}

set是有去重功能的，当插入数据有重复数据的时候就会自动去重。

int main()
{
//set插入使用样例
set<int> s;
s.insert(6);
s.insert(8);
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(9);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//输出 2 5 6 8 9
return 0;
}

可以插入列值表，插入列值表也是会自动去重。

int main()
{
set<int> s;
s.insert({ 4,6,8,9,6,3 });

for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//输出 3，4，6，8，9
return 0;
}

插入string比较ascll码值的顺序

int main()
{
set<string> s;
s.insert({ "want","can","i","say" });
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//输出can i say want
return 0;
}

set的查找

直接进行查找

int main()
{
set<int> s;
s.insert({ 4,6,8,9,6,3 });

for (auto e : s)
{
cout << e << " ";
}
cout << endl;

int x = 0;
cin >> x;
auto  pos = s.find(x);
if (pos != s.end())
{
cout << x << "存在" << endl;
}
else
{
cout << x << "不存在！" << endl;
}


return 0;

}

利用count函数进行快速查找

int main()
{
set<int> s;
s.insert({ 4,6,8,9,6,3 });

for (auto e : s)
{
cout << e << " ";
}
cout << endl;

int x = 0;
cin >> x;
if (s.count(x))
{
cout << x << "存在" << endl;

}
else
{
cout << x << "不存在！" << endl;
}
return 0;

}

查找区间数据

 int main()
 {
 std::set<int> myset;
 for (int i = 1; i < 10; i++)
 myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
 for (auto e : myset)
 {
 cout << e << " ";
 }
 cout << endl;
 // 实现查找到的[itlow,itup)包含[30, 60]区间
 // 返回 >= 30 auto itlow = myset.lower_bound(30);
 // 返回 > 60 auto itup = myset.upper_bound(60);
 // 删除这段区间的值
 
 myset.erase(itlow, itup);
 for (auto e : myset)
 {
 cout << e << " ";
 }
 cout << endl;
 return 0;
 }

set的删除

直接删除x

int main()
{
set<int> s;
s.insert({ 4,6,8,9,6,3 });

for (auto e : s)
{
cout << e << " ";
}

cout << endl;
int x = 0;
cin >> x;
s.erase(x);

for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//假如要删除的数是4，输入4。直接删除4输出 3，6，8，9
return 0;

 }

直接查找在利用迭代器删除x

set<int> s;
s.insert({ 4,6,8,9,6,3 });
cin >> x;
    auto pos = s.find(x);
    if (pos != s.end())
    {
            s.erase(pos);
    }
    else
    {
            cout << x << "不存在！" << endl;
    }
    for (auto e : s)
    {
            cout << e << " ";
    }
    cout << endl;

利用find和erase结合还可以进行查找数据把所查找的数据删除

int main()
{
// 直接查找在利⽤迭代器删除x
set<int> s;
s.insert({ 4,6,8,9,6,3 });
int x = 0;
cin >> x;

auto pos = s.find(x);
if (pos != s.end())
{
s.erase(pos);
}
else
{
cout << x << "不存在！" << endl;
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}

四、 multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那insert/find/count/erase都围绕着⽀持值冗余有所差异。

multiset排序的时候不去重

int main()
{
multiset<int> s;
s.insert({ 4,7,9,1,6,6,7 });
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//输出1 4 6 6 7 7 9
return 0;
}

相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个

int main()
{   multiset<int> s;
s.insert({ 4,7,9,1,6,6,7 });
    int x;
 cin >> x;
auto pos = s.find(x);
 while (pos != s.end() && *pos == x)
 {
 cout << *pos << " ";
 ++pos;
 }
 cout << endl;
 cout << s.count(x) << endl;
}

// 相⽐set不同的是，count会返回x的实际个数

multiset<int> s;
s.insert({ 4,7,9,1,6,6,7 });
 cout << s.count(x) << endl;

// 相⽐set不同的是，erase给值时会删除所有的x

multiset<int> s;
s.insert({ 4,7,9,1,6,6,7 });
s.erase(x);
 for (auto e : s)
 {
 cout << e << " ";
 }
 cout << endl;
 return 0;

五、map

在这里插入图片描述
Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是O(logN)，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。

1.pair类型

map底层的红⿊树节点中的数据，使⽤pair<Key,T>存储键值对数据。

 typedef pair<const Key, T> value_type;
 template <class T1, class T2>
 struct pair 
{
 // map::key_type
 // map::mapped_type
 // map::key_compare

 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)
 {}
 template<class U, class V> 
 pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
 {}
 };
 template <class T1,class T2>
 inline pair<T1,T2> make_pair (T1 x, T2 y)
 {
 return ( pair<T1,T2>(x,y) );
 }

map的数据修改

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

map支持修改mapped_type数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接口。

map把value值给的是T类型，typedf为mappd_type。而value_typed是红黑树中储存的pair键值对值。日常我们还是把T映射的值叫做value，所以不要混淆。

下面来讲讲文档中insert返回值的说明。

pair<iterator,bool> insert (const value_type& val);

在这里插入图片描述
insert插入一个一个pairkey,T>对象。如果key在map中，就插入失败，返回一个pair<iterator,bool>对象，返回pair对象first是key所在节点的迭代器，second是false。如果key不在map中，就插入成功，返回一个pair<iterator,bool>对象，返回的pair对象first是新插入节点的迭代器，second是true。

不管是插入成功还是失败，都会返回pair对象first所指的key所在的迭代器。如果插入失败就充当查找的功能，所以也是这一点insert可以实现operator[]。

注意：两个pair，一个是map底层红黑树节点存在的pair<key,T>,另一个是insert的返回值pair<iterator,bool>。

operator[]

mapped_type& operator[] (const key_type& k);

// operator的内部实现
mapped_type& operator[] (const key_type& k)
{
pair<iterator, bool> ret = insert({ k, mapped_type() });
    iterator it = ret.first;
    return it->second;
}

如果k不在map中，insert就会插入k和mapped_typed的值。然后返回[]节点中存储mapped_type值的引用，可以通过引用修改映射值。[]具备了插入修改的功能。
如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能。

2.map的构造和迭代器

map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，map⽀持修改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_list<value_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.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   -> pair<const key_type,mapped_type>
 // 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
 
pair<iterator,bool> insert (const value_type& val);
 // 列表插⼊，已经在容器中存在的值不会插⼊
 
void insert (initializer_list<value_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);
 // 删除k，k存在返回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;

map的构造遍历

int main()
{
    // initializer_list构造及迭代遍历

    map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插⼊"},{ "string", "字符串" } };

    //map<string, 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;

map的插入

using namespace std;
int main()
{
//四种插入方式
map<string, string> dict;
pair<string, string> kv1("first", "第一个");
dict.insert(kv1);

dict.insert(pair < string, string>("second", "第二个"));

dict.insert(make_pair("sort", "排序"));

dict.insert({ "auto","自动的" });

for (const auto& e : dict)
{
cout << e.first << ":" << e.second << endl;
}
cout << endl;

return 0;
}

map的删除

和set类似

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;
 }

map的查找

可以利用find，也可以用operator[]。和operator[]的一些其他功能，如插入修改查找。

int main()
{
map<string, string> dict;
dict.insert({ "sort","排序" });

//插入
dict["auto"];

//插入加修改
dict["left"] = "左边";

//key存在 查找

dict["left"];

auto it = dict.begin();
while (it!= dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
return 0;
}

六、multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。

原文地址：https://blog.csdn.net/GGDxianv/article/details/143081757

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【c语言篇】指针进阶
下一篇：PotPlayer教程：如何锁定播放屏幕尺寸

两台手机如何提词呢，一台手机后置高清摄像一台手机前置提词+实时监测状态的解决方案来喽
双机提词，只需要连接到共同WiFi。拍视频只会用前置摄像头可不行啊，你看哦，我用的是后置摄像头拍摄，还能把后面手机画面投影到前面手机。有时候我们看不到自己的状态，这样呀，我们就能一边看台词。才发现姿势
阅读更多2024-11-06
【IEEE出版】第六届国际科技创新学术交流大会暨信息技术与计算机应用学术会议（ITCA 2024，12月06-08)
第六届信息技术与计算机应用学术会议(ITCA 2024) 依旧作为第六届国际科技创新学术交流大会的分会场开展，大会将于2024年12月06-08日在中国广州隆重举行。
阅读更多2024-11-06
练习LabVIEW第三十七题
利用XY GRAPH 构成李萨如图形
阅读更多2024-11-06
ReactNative中实现图片保存到手机相册
以上代码，`ImagePicker.launchCameraAsync()` 用于启动相机并获取图片，然后使用 `saveImage()` 函数将获取到的图片保存到手机相册。在 Expo 中，要将图片
阅读更多2024-11-06
如何解决传统能源企业后备人才不足、人才规划缺失问题
很多传统能源企业都面临着老员工逐渐退休，新员工还没有培养起来的问题，缺乏提前对人力资源规划的意识，导致当企业要开展新业务时或者老员工离职的时候，缺乏合适的人选。特别是对于国有企业来说，人才全流程管理体
阅读更多2024-11-06
第二章：快速体验 TDengine
初步了解与掌握tdengine SQL写入与查询
阅读更多2024-11-06
【ARM Linux 系统稳定性分析入门及渐进 2.2 -- Crash 命令 Crash Usage】
转储任务的打开文件描述符数据；最有用的是每个打开文件描述符的文件、dentry 和 inode 结构地址。还可以转储地址空间中每个页面的物理地址，或者如果没有映射，显示其在文件或交换设备中的位置。工具
阅读更多2024-11-06
真实线上DB存储架构升级实战
前言交易系统1.0的存储架构采用了单库单表，随着业务快速发展，订单量从日单量十万级别快速增长到日单量百万级别，预计在未来两三个月就存储就会出现瓶颈，DB存储架构升级迫在眉睫。交易系统如何做到平滑迁移？
阅读更多2024-11-06
解读《ARM Cortex-M3 与Cortex-M4 权威指南》——第3章技术综述
Thumb 是 ARM ISA 的一个扩展，目的是在需要节省内存和提高代码密度的应用中，提供更高效的指令集。D-CODE 总线主要负责处理器内部和内存之间的数据传输，而系统总线则协调各个模块之间的通信
阅读更多2024-11-06
「Mac畅玩鸿蒙与硬件29」UI互动应用篇6 - 多选问卷小应用
本篇将带你实现一个多选问卷小应用，用户可以勾选选项并点击提交按钮查看选择的结果。通过本教程，你将学习如何使用 Checkbox 组件、动态渲染列表、状态管理及用户交互，构建完整的应用程序。
阅读更多2024-11-06