【深入C++】map和set的使用
CSDN 2024-07-28 11:35:01 阅读 86
文章目录
C++ 中的容器分类1. 顺序容器2. 关联容器3. 无序容器4. 容器适配器5. 字符串容器6. 特殊容器
set1.构造函数2.迭代器3.容量相关的成员函数4.修改器类的成员函数5.容器相关操作的成员函数
multiset1.equal_range
map1.初始化相关的函数2.迭代器3.容量相关的成员函数4.访问相关的成员函数5.修改器类的成员函数6.容器相关操作的成员函数
总结
C++ 中的容器分类
在C++中,标准库提供了多种容器,这些容器可以根据其数据存储方式和功能进行分类。以下是C++中常见容器的分类:
1. 顺序容器
这些容器按顺序存储元素,适用于需要保持元素顺序的场景。
vector: 动态数组,支持快速随机访问和在末尾高效插入和删除操作。deque: 双端队列,支持快速随机访问和在两端高效插入和删除操作。list: 双向链表,支持在任何位置高效插入和删除操作,但随机访问较慢。forward_list: 单向链表,只支持在头部高效插入和删除操作。array: 固定大小的数组,大小在编译时确定。
2. 关联容器
这些容器根据键值对存储元素,并自动按键排序,适用于需要快速查找的场景。
set: 集合,存储唯一的元素,元素自动按键排序。multiset: 允许重复元素的集合,元素自动按键排序。map: 键值对存储的映射,键唯一且自动排序。multimap: 允许重复键的映射,键自动排序。
3. 无序容器
这些容器使用哈希表存储元素,适用于需要快速查找和插入的场景,但不保证元素顺序。
unordered_set: 无序集合,存储唯一的元素。unordered_multiset: 无序多重集合,允许重复元素。unordered_map: 无序映射,键唯一。unordered_multimap: 无序多重映射,允许重复键。
4. 容器适配器
这些不是独立的容器,而是对现有容器的包装,提供特定用途的接口。
stack: 栈,后进先出(LIFO)结构,通常使用deque或vector实现。queue: 队列,先进先出(FIFO)结构,通常使用deque或list实现。priority_queue: 优先队列,元素按优先级排序,通常使用vector和heap算法实现。
5. 字符串容器
string: 用于存储和操作字符序列,类似于动态数组,但专门针对字符。
6. 特殊容器
bitset: 固定大小的二进制数组,提供按位操作。
这些容器各有优缺点和适用场景,选择合适的容器可以显著提高程序的性能和可维护性。
这篇文章讲的两个容器都是关联式容器
set
在C++标准库中,set容器的底层实现通常是基于红黑树这种自平衡二叉搜索树。红黑树是一种能够在插入、删除和查找操作中保持对数时间复杂度的树结构。
1.构造函数
构造函数主要分为三个:无参构造,迭代器区间构造,拷贝构造
无参构造:
<code>set<int> s;
迭代器区间构造:
vector<int> v{ 1,2,3,4,5,6,7 };
set<int> s(v.begin(), v.end());
拷贝构造:
set<int> s1{ 1,2,3,4 };
set<int> s2(s1);
赋值拷贝
set<int> s1{ 1,2,3,4 };
set<int> s2;
s2 = s1;
2.迭代器
迭代器遍历:
<code>auto it = s1.begin();
while (it != s1.end())
{
cout << *it << ' ';
it++;
}
范围for:
for (auto e : s1)
{
cout << e << ' ';
}
3.容量相关的成员函数
<code>int main()
{
set<int> s1{ 1,2,3,4 };
cout << s1.size() << endl;//4
cout << s1.empty() << endl;//0
return 0;
}
4.修改器类的成员函数
insert:
有三个重载函数
支持迭代器区间插入。
<code>int main()
{
set<int> s1;
s1.insert(2);
s1.insert(3);
s1.insert(6);
s1.insert(1);
s1.insert(5);
s1.insert(7);
for (auto e : s1)
{
cout << e << ' ';
}
return 0;
}
erase:
第二个重载函数:
<code>int num = s1.erase(3);
cout << endl << num << endl;
删除成功返回1,删除失败返回0。
5.容器相关操作的成员函数
find:
<code>int main()
{
set<int> s1;
s1.insert(2);
s1.insert(3);
s1.insert(6);
s1.insert(1);
s1.insert(5);
s1.insert(7);
auto it = s1.find(2);
if (it != s1.end()) cout << *it << endl;
else cout << "does not exist" << endl;
return 0;
}
如果找到了返回找到的迭代器,如果没有找到则返回的是end()。
count:
count返回的是对应元素的个数:在set中存在就返回1,不存在就返回0。
lower_bound:
lower_bound返回的是大于等于某个数的。
<code>int main()
{
set<int> s1;
s1.insert(2);
s1.insert(3);
s1.insert(6);
s1.insert(1);
s1.insert(5);
s1.insert(7);
auto lower = s1.lower_bound(4);
cout << *lower << endl;
return 0;
}
这里输出的是大于等于4的数,所以这里输出的是5。
upper_bound:
auto upper = s1.upper_bound(6);
cout << *upper << endl;
这里输出的是大于6的数,所以输出的是7。
set有一个致命的缺陷,在插入重复数据时,是插入不进去的,所以这里我们需要了解multiset。
multiset
multiset和set唯一不同的区别是一个支持插入重复数据,一个不支持。
<code>int main()
{
set<int> s1;
s1.insert(1);
s1.insert(1);
s1.insert(1);
s1.insert(1);
for (auto e : s1) cout << e << ' ';
multiset<int> s2;
s2.insert(1);
s2.insert(1);
s2.insert(1);
s2.insert(1);
cout << endl;
for (auto e : s2)cout << e << ' ';
return 0;
}
可以set不支持插入重复数据,multiset支持插入重复数据。
在查找数据的时候multiset查找的是第一个数据。
删除数据:multiset删除数据,删除的是所有重复的数据,而不是删除第一个数据。
1.equal_range
<code>int main()
{
multiset<int> s{ 1,1,4,4,4,3,3,3,3,3,5,5,5, 6 };
auto [a, b] = s.equal_range(3);
s.erase(a, b);
for (auto e : s)
{
cout << e << ' ';
}
}
equal_range可以求出指定值的范围区域,两个迭代器。
一个首一个尾。
map
map属于KV模型,用一个k值索引v值。
在C++标准库中,map 容器的底层实现通常是基于红黑树(Red-Black Tree)这种自平衡二叉搜索树(Self-balancing Binary Search Tree)。红黑树是一种能够在插入、删除和查找操作中保持对数时间复杂度的树结构。
1.初始化相关的函数
构造函数:
map和set的构造方式是一样的,也是三种构造函数。
2.迭代器
map的迭代器和set的迭代器稍有区别,但不多。
返回for:
<code>int main()
{
map<int, char> m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } };
for (auto e : m)
cout << e.first << ':' << e.second << endl;
}
迭代器区间遍历:
int main()
{
map<int, char> m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } };
auto it = m.begin();
while (it != m.end())
{
cout << it->first << ':' << it->second << endl;
it++;
}
}
结构化绑定:
int main()
{
map<int, char> m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } };
for (auto [a, b] : m)
cout << a << ':' << b << endl;
}
3.容量相关的成员函数
和set的用法大差不差。
4.访问相关的成员函数
operator[]:
<code>int main()
{
map<int, char> m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } };
cout << m[1] << endl;
cout << m[2] << endl;
cout << m[3] << endl;
}
map可以通过一个成员的第一个键值来索引当前成员的第二个键值,就是用key索引value。
at:
int main()
{
map<int, char> m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } };
cout << m.at(1) << endl;
}
用at进行索引value。
可以看见如果容器当中没有当前值的索引,则会抛出异常。
5.修改器类的成员函数
这里修改器类的成员函数和set相同,但是insert,需要插入一个键值对:
<code>m.insert({ 6,'f' });
m.insert(pair<int, char>(6, 'f'));
m.insert(make_pair(6, 'f'));
6.容器相关操作的成员函数
这些和set都是一样的。
总结
在本篇博客中,我们深入探讨了C++标准库中的<code>map和set
容器。通过详细的示例和解释,我们了解了它们的基本用法、常用操作以及在不同场景下的应用。map
和set
不仅为我们提供了高效的键值对存储和有序集合管理功能,还在复杂数据结构和算法设计中扮演了重要角色。
掌握map
和set
的使用,不仅能够提升我们的编程效率,还能帮助我们编写出更为高效和可靠的代码。在实际开发中,合理地选择和使用这些容器,可以显著优化程序的性能和可维护性。
希望通过这篇博客,大家能够对map
和set
有更深入的理解,并在以后的编程实践中灵活运用它们。如果你有任何疑问或建议,欢迎在评论区留言讨论。
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。