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

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

---

一、set和map的简介

在C++中，set和map是常用的关联容器，分别用于存储不重复的元素和键值对(key-value pairs)。它们都在和

set

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

特点：

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

map

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

特点：

1. 键的唯一性：map 中键不能重复。
2. 自动排序：按键值升序排列。
3. 时间复杂度：插入、查找、删除的平均时间复杂度为 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_typeiterator 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 9return 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 9return 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，9return 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 wantreturn 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 90for (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，9return 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()
{// 直接查找在利⽤迭代器删除xset<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 9return 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_comparetypedef 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 typeskey_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冗余，[]就只能⽀持插⼊了，不能⽀持修改。