C++进阶：详细讲解容器set与map（pair、multiset、multimap）
上次介绍了搜索二叉树：C++进阶：二叉搜索树介绍、模拟实现（递归迭代两版本）及其应用
为了介绍后面的AVLTree和红黑树，我们要进行一些铺垫，就是set与map的介绍啦
1.关联式容器与序列式容器
关联式容器和序列式容器是 C++ 中两种不同的容器类型
-
关联式容器:
- 关联式容器主要包括
std::set,std::map,std::multiset,std::multimap等。 - 这些容器是基于键值对(
<key, value>结构)的概念，通过键==（key）来唯一标识元素==。 - 关联式容器内部使用二叉搜索树（通常是红黑树）或类似的数据结构，以保持元素的有序性。
- 插入、删除、查找等操作的平均时间复杂度是 O(log n)。
- 关联式容器主要包括
-
序列式容器:
- 序列式容器包括
std::vector,std::list,std::deque,std::array等。 - 这些容器是基于线性结构的，元素在容器中的位置是由插入的顺序决定的。
- 插入、删除、查找等操作的平均时间复杂度因容器类型而异，但在最差情况下，可能达到 O(n)。
- 序列式容器包括
2.C++中的键值对——pair
在C++中，键值对是一种数据结构，通常用于表示关联关系
键值对由两部分组成：键（Key）和值（Value）。这种结构允许通过键来检索和关联对应的值，key代表键值，value表示与key对应的信息
2.1pair定义
std::pair 是C++标准库中提供的一个简单的键值对实现。它包含在 <utility> 头文件中。一个 std::pair 有两个公有成员：first 和 second，分别表示键和值==（first<= =>key ; second<= =>value）==
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)
{}
};
2.2pair的对象创建与访问
文档中的构造函数的介绍：
- 默认构造函数：
pair();- 默认构造函数创建一个空的
std::pair对象，不包含任何值。
- 拷贝构造函数：
template<class U, class V> pair (const pair<U,V>& pr);- 拷贝构造函数用于从另一个
std::pair对象pr中复制键值对来构造一个新的std::pair对象。
- 初始化构造函数：
pair (const first_type& a, const second_type& b);- 初始化构造函数接受两个参数
a和b，分别用于初始化std::pair对象的first和second成员变量。
void test_pair()
{
pair<int, char> p1;//空参
pair<int, char> p2(2, '2');
pair<int, char> p3(p2);//拷贝构造
cout << p1.first << " " << p1.second << endl;;
cout << p2.first << " " << p2.second << endl;
cout << p3.first << " " << p3.second << endl;
}
int main()
{
test_pair();
return 0;
}
2.3make_pair() 函数和使用{} -简化创建过程
void test_pair2()
{
auto p4 = make_pair(2, 'c');//使用make_pair
pair<int, char> p5 = { 3,'d' };//c++11后，使用{ }
cout << p4.first << " " << p4.second << endl;
cout << p5.first << " " << p5.second << endl;
}
int main()
{
test_pair2();
return 0;
}
我们能使用
{}（初始化列表），是因为：构造函数匹配。如果使用花括号进行初始化，编译器会尝试匹配合适的构造函数。对于pair，存在接受两个参数的构造函数，因此可以通过初始化列表直接构造键值对
3. set容器
set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
set在底层是用二叉搜索树(红黑树)实现的
3.1Constructs构造函数
void test_set1()
{
set<int> s1;
vector<int> v = { 1,2,3,4,5 };
set<int> s2(v.begin(), v.end());//利用迭代区间
set<int> s3 = s2;//拷贝构造
for (auto e : s1)
{
cout << e << " ";
}
cout << endl;
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
for (auto e : s3)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_set1();
return 0;
}
3.2Iterator 迭代器
| 函数声明 | 功能 |
|---|---|
iterator begin(); |
返回指向set开头的迭代器 |
iterator end(); |
返回指向set最后一个元素后面的迭代器 |
const_iterator cbegin() const; |
返回指向set开头的const迭代器 |
const_iterator cend() const; |
返回指向set最后一个元素后面的const迭代器 |
reverse_iterator rbegin(); |
返回指向set最后一个元素的反向迭代器 |
reverse_iterator rend(); |
返回指向set第一个元素前面的反向迭代器 |
const_reverse_iterator crbegin() const; |
返回指向set最后一个元素的反向const迭代器 |
const_reverse_iterator crend() const; |
返回指向set第一个元素前面的反向const迭代器 |
3.3 插入、删除、查找、count
3.3.1 insert（）插入
声明：pair<iterator, bool> insert(const value_type& val);
- 插入元素到 set 中。
- 如果插入成功，返回一个迭代器指向插入的位置和
true。 - 如果元素已经存在，返回一个迭代器指向已存在的元素和
false。
-
返回一个
pair对象，包含插入的迭代器和插入是否成功的标志。
3.3.2 erase（） 删除
| 函数声明 | 功能介绍 | 返回值 |
|---|---|---|
iterator erase(iterator position); |
删除指定位置的元素，并返回指向被删除元素之后元素的迭代器。 | 指向被删除元素之后元素的迭代器。 |
size_type erase(const key_type& k); |
删除 set 中所有等于指定键值的元素。返回删除的元素个数。 | 删除的元素个数。 |
iterator erase(iterator first, iterator last); |
删除区间 [first, last) 中的所有元素，并返回最后一个被删除元素之后的迭代器。 |
指向被删除元素之后元素的迭代器。 |
3.3.3 find（）查找
find 函数用于在 set 中查找指定键值的元素，并返回指向该元素的迭代器。如果元素不存在，则返回 end()。
3.3.4 count（）函数
声明：size_type count (const key_type& k) const;
count 函数用于统计 set 中与指定键值相等的元素个数。由于 set 中元素的键值是唯一的，因此该函数的返回值要么是 0（元素不存在），要么是 1（元素存在）。
void test_set2()
{
// 排序+去重
set<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(5);
s.insert(1);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
set<int>::iterator pos = s.find(5);//找到5就删除
if (pos != s.end())
{
cout << "找到了" << endl;
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
if (s.count(1))
{
cout << "1在" << endl;
}
else
{
cout << "1不在" << endl;
}
}
int main()
{
test_set2();
return 0;
}
4.容器 multiset
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
multiset底层结构为二叉搜索树(红黑树)
注意：
multiset中再底层中存储的是<value, value>的键值对
mtltiset的插入接口中只需要插入即可
与set的区别是，multiset中的元素可以重复，set是中value是唯一的
使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
multiset中的元素不能修改
在multiset中找某个元素，时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
multiset的作用：可以对元素进行排序文章来源：https://www.toymoban.com/news/detail-848430.html
multiset 是 C++ 标准库中的关联式容器之一，属于有序容器。与 set 不同的是，multiset 允许键值重复，即可以包含相同键值的多个元素。
-
允许重复键值：
multiset允许容器中存在相同的键值，因此可以包含多个相同键值的元素。 -
有序性： 与
set类似，multiset也维护元素的有序性，根据键值进行排序。
- 当需要允许键值重复，并且希望保持元素有序时，可以选择使用
multiset。
5.map 容器
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在
[]中放入key，就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
5.1map 模板参数说明
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
5.2 对象的创建
void testmap1()
{
map<string, string> m1;//空的
map<string, string> m2(m1);//拷贝构造
}
5.3 迭代器，insert，find ，[]重载
5.3.1 迭代器
下面是关于 multiset 中成员函数 begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), 和 crend() 的函数声明和功能介绍：
| 函数声明 | 功能介绍 |
|---|---|
iterator begin(); |
返回 multiset 中首元素的位置的迭代器。 |
iterator end(); |
返回 multiset 中最后一个元素后面的位置的迭代器。 |
const_iterator cbegin() const; |
返回 multiset 中首元素的位置的 const 迭代器，不能修改所指向的元素。 |
const_iterator cend() const; |
返回 multiset 中最后一个元素后面的位置的 const 迭代器，不能修改所指向的元素。 |
reverse_iterator rbegin(); |
返回指向 multiset 中第一个元素的反向迭代器，即 end()。 |
reverse_iterator rend(); |
返回指向 multiset 中最后一个元素下一个位置的反向迭代器，即 rbegin()。 |
const_reverse_iterator crbegin() const; |
返回指向 multiset 中第一个元素的反向 const 迭代器，不能修改所指向的元素。 |
const_reverse_iterator crend() const; |
返回指向 multiset 中最后一个元素下一个位置的反向 const 迭代器，不能修改所指向的元素。 |
5.3.2 insert() 函数
void testmap2()
{
map<string, string> m1;//空的
m1.insert(pair<string, string>("sort", "排序"));//匿名对象
m1.insert(make_pair("apple", "苹果"));//使用make_pair函数
m1.insert({ "apple", "苹果" });// C++11 多参数隐式类型转换(构造函数支持)
}
5.3.3 find() 函数
在
map中，find函数用于查找指定键的元素，并返回指向该元素的迭代器。如果找到了指定的键，则返回指向该键值对的迭代器；如果未找到，则返回指向map末尾的迭代器。
| 函数声明 | 功能介绍 |
|---|---|
iterator find(const key_type& k); |
查找键值为 k 的元素，并返回一个指向该元素的迭代器。如果 k 存在于 map 中，则返回指向该元素的迭代器；如果不存在，则返回指向 map 末尾的迭代器。 |
const_iterator find(const key_type& k) const; |
在常量 map 中查找键值为 k 的元素，并返回一个指向该元素的迭代器。如果 k 存在于 map 中，则返回指向该元素的迭代器；如果不存在，则返回指向 map 末尾的迭代器。 |
5.3.4 []
-
读取元素：当使用
[]运算符时- 如果指定的键存在于
map中，则返回与该键关联的值 - 如果不存在，则会插入一个新的键值对，键为指定的键，值为默认构造的对应值类型的默认值，并返回该默认值的引用
- 如果指定的键存在于
-
插入元素：当使用
[]运算符向map中插入元素时- 如果指定的键不存在，则会创建一个新的键值对，键为指定的键，值为指定的值，并返回该值的引用
- 如果键已经存在，则直接返回对应的值的引用。
void testmap3()
{
map<string, string> m1;//空的
m1.insert(pair<string, string>("sort", "排序"));//匿名对象
m1.insert(make_pair("apple", "苹果"));//使用make_pair函数
m1.insert({ "left", "左边" });// C++11 多参数隐式类型转换(构造函数支持)
for (auto& kv : m1)
{
cout << kv.first << ":" << kv.second << " ";
}
cout << endl;
m1["right"];//这是插入一个right（key）
m1["apple"] = "青苹果";//这里是进行修改
for (auto& kv : m1)
{
cout << kv.first << ":" << kv.second << " ";
}
cout << endl;
}
int main()
{
testmap3();
return 0;
}
6.容器 multimap
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的
在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
multiset底层结构为二叉搜索树(红黑树)
注意
multiset中再底层中存储的是<value, value>的键值对
mtltiset的插入接口中只需要插入即可
与set的区别是，multiset中的元素可以重复，set是中value是唯一的
使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
multiset中的元素不能修改
在multiset中找某个元素，时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
multiset的作用：可以对元素进行排序
这次就到这里啦！！！感谢大家支持！！！文章来源地址https://www.toymoban.com/news/detail-848430.html
到了这里，关于C++进阶：详细讲解容器set与map（pair、multiset、multimap）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【C++】map/multimap/set/multiset的经典oj例题 [ 盘点＆全面解析 ] （28）](https://imgs.yssmx.com/Uploads/2024/02/765855-1.png)
![⚡【C++要笑着学】(31) 映射类：map 类 | pair 类型 (value_type) | map 的插入和遍历 | map 的 operator[] | multimap 类](https://imgs.yssmx.com/Uploads/2024/02/773036-1.png)
