文章目录

• C++ 中的容器分类
• • 1. 顺序容器
  • 2. 关联容器
  • 3. 无序容器
  • 4. 容器适配器
  • 5. 字符串容器
  • 6. 特殊容器
• set
• • 1.构造函数
  • 2.迭代器
  • 3.容量相关的成员函数
  • 4.修改器类的成员函数
  • 5.容器相关操作的成员函数
• multiset
• • 1.equal_range
• map
• • 1.初始化相关的函数
  • 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.构造函数

构造函数主要分为三个：无参构造，迭代器区间构造，拷贝构造

无参构造：

set s; 

迭代器区间构造：

vector  v{ 1,2,3,4,5,6,7 }; set s(v.begin(), v.end()); 

拷贝构造：

set s1{ 1,2,3,4 }; set s2(s1); 

赋值拷贝

set s1{ 1,2,3,4 }; set s2; s2 = s1; 

2.迭代器

迭代器遍历：

auto it = s1.begin(); while (it != s1.end()) { 	cout << *it << ' '; 	it++; } 

范围for：

for (auto e : s1) { 	cout << e << ' '; } 

3.容量相关的成员函数

int main() { 	set s1{ 1,2,3,4 }; 	cout << s1.size() << endl;//4 	cout << s1.empty() << endl;//0 	return 0; } 

4.修改器类的成员函数

insert：
有三个重载函数

支持迭代器区间插入。

int main() { 	set 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：

第二个重载函数：

int num = s1.erase(3); cout << endl << num << endl; 

删除成功返回1，删除失败返回0。

5.容器相关操作的成员函数

find：

int main() { 	set 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返回的是大于等于某个数的。

int main() { 	set 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唯一不同的区别是一个支持插入重复数据，一个不支持。

int main() { 	set s1; 	s1.insert(1); 	s1.insert(1); 	s1.insert(1); 	s1.insert(1); 	for (auto e : s1) cout << e << ' '; 	multiset 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

int main() { 	multiset 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：

int main() { 	map m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } }; 	for (auto e : m) 		cout << e.first << ':' << e.second << endl; } 

迭代器区间遍历：

int main() { 	map 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 m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } }; 	for (auto [a, b] : m) 		cout << a << ':' << b << endl; } 

3.容量相关的成员函数

和set的用法大差不差。

4.访问相关的成员函数

operator[]：

int main() { 	map 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 m{ { 1,'a' } ,{ 2,'b' },{ 3,'c' },{ 4,'d' },{ 5,'e' } }; 	cout << m.at(1) << endl; } 

用at进行索引value。

可以看见如果容器当中没有当前值的索引，则会抛出异常。

5.修改器类的成员函数

这里修改器类的成员函数和set相同，但是insert，需要插入一个键值对：

m.insert({ 6,'f' }); m.insert(pair(6, 'f')); m.insert(make_pair(6, 'f')); 

6.容器相关操作的成员函数

这些和set都是一样的。

总结

在本篇博客中，我们深入探讨了C++标准库中的map和set容器。通过详细的示例和解释，我们了解了它们的基本用法、常用操作以及在不同场景下的应用。map和set不仅为我们提供了高效的键值对存储和有序集合管理功能，还在复杂数据结构和算法设计中扮演了重要角色。

掌握map和set的使用，不仅能够提升我们的编程效率，还能帮助我们编写出更为高效和可靠的代码。在实际开发中，合理地选择和使用这些容器，可以显著优化程序的性能和可维护性。

希望通过这篇博客，大家能够对map和set有更深入的理解，并在以后的编程实践中灵活运用它们。如果你有任何疑问或建议，欢迎在评论区留言讨论。