C++ STL详解（3）

小鱼儿 2022-10-31 04:16 91阅读 0赞

**上一篇博客：[C++ STL详解（2）][C_ STL_2]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  刷题时常用的STL
 *   *  set / multiset
     *   *  简介
         *  insert()
         *  size()
         *  empty()
         *  clear()
         *  count()
         *  begin() / end()
         *  erase()
         *  lower\_bound()
         *  upper\_bound()
         *  max\_size()
         *  find()
     *  map / multimap
     *   *  简介
         *  insert()
         *  operator\[\]
         *  size()
         *  empty()
         *  clear()
         *  count()
         *  begin() / end()
         *  erase()
         *  lower\_bound() / upper\_bound()
         *  find()

# 刷题时常用的STL #

## set / multiset ##

### 简介 ###

**set** 是 `关联容器` 的一种，是排序好的集合（元素已经进行了排序）。**set** 和 **multiset** 类似，它和 **multiset** 的差别在于 **set** 中不能有重复的元素。**multiset** 的成员函数 **set** 中也都有。使用 **set** 必须包含 `#include<set>` 头文件。

在 **set** 中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。如果插入重复的元素，那么 **set** 将自动忽略该操作。**set** 中数元素的值不能直接被改变。C++ STL中标准关联容器 set, multiset, map, multimap 内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。 RB树的统计性能要好于一般平衡二叉树。这四种容器插入、查找、删除的时间复杂度都为 O( log ⁡ n \\log n logn)。

**map** 和 **set** 的插入删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。

### insert() ###

向容器中插入一个元素。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	set<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	// 使用迭代器遍历 set 
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	//输出结果：1 2 3 
    	return 0;
    }

### size() ###

返回容器中元素的个数。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	set<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	cout << "元素的个数为：" << s.size() << endl; 
    	// 使用迭代器遍历 set 
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	//输出结果：1 2 3 
    	return 0;
    }

### empty() ###

判断当前容器是否为空，如果为空，返回true；否则返回false。

### clear() ###

清除当前容器中的所有元素。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	set<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	cout << "元素的个数为：" << s.size() << endl; 
    	// 输出结果：元素的个数为：3 
    	// 清空容器中的所有元素 
    	s.clear();
    	cout << "元素的个数为：" << s.size() << endl; 
    	// 输出结果：元素的个数为：0
    	return 0;
    }

### count() ###

返回容器中某个值元素的个数。在 **set** 中返回的值只能是 `0` 或 `1`。而在 **multiset** 中返回的个数可能有多个。下面以 **multiset** 来进行举例：

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	s.insert(6);
    	s.insert(6);
    	s.insert(6);
    	cout << "元素 6 的个数为：" << s.count(6) << endl; 
    	// 输出结果：元素 6 的个数为：3 
    	return 0;
    }

### begin() / end() ###

**begin()** 返回指向第一个元素的迭代器。**end()** 返回指向最后一个元素之后一个元素的迭代器。这两个都支持 `++` 和 `--` 操作， 返回前驱和后继。

迭代器是 STL 中的重要概念，类似于指针。在这里迭代器的表示为 `set<int>::iterator`。在C++ 11 中可以使用 `auto` 关键字来代替 `set<int>::iterator`。`auto` 可以自动匹配类型，当变量名称比较长时可以使用 `auto` 来进行代替。比如 int、double、long long等都可以直接写成 `auto` 来进行代替。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	// 遍历方式 1: 
    	for (set<int>::iterator it = s.begin(); it != s.end(); it++) cout << *it << ' '; 
    	// 输出结果： 1 2 3
    	cout << endl; 
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	// 与上面的输出结果是一样的 
    	cout << endl;
    	// 遍历方式 2: 使用范围遍历 
    	for (auto x : s) cout << x << ' '; 
    	// 输出结果： 1 2 3
    	return 0;
    }

### erase() ###

删除等于key值的所有元素（返回被删除的元素的个数）。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	s.insert(3);
    	s.insert(3);
    	s.insert(3);
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	// 输出结果： 1 2 3 3 3 3
    	cout << endl; 
    	cout << s.erase(3);
    	// 输出结果： 4
    	cout << endl;
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	// 输出结果： 1 2
    	return 0;
    }

### lower\_bound() ###

返回指向 `大于（或等于）` 某值的第一个元素的 **迭代器**。返回类型类似一个指针，可以使用 `*` 进行解引用，输出其值。如果不存在则返回迭代器 **.end()**。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	for (int i = 1; i <= 10; i++) s.insert(i);
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	// 输出结果：1 2 3 4 5 6 7 8 9 10
    	cout << endl;
    	auto it = s.lower_bound(6);
    	cout << *it << endl;
    	// 输出结果：6 
    	it = s.lower_bound(15);
    	cout << *it; 
    	// 因为容器中没有 15，所以返回迭代器.end()。输出最后一个元素 10
    	return 0;
    }

### upper\_bound() ###

返回 `大于某个值` 元素的迭代器。注意：该方法与 `lower_bound()` 方法类似，只是返回的是大于某个元素的迭代器，而不是大于或等于某个元素的迭代器。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	for (int i = 1; i <= 10; i++) s.insert(i);
    	for (auto it = s.begin(); it != s.end(); it++) cout << *it << ' ';
    	// 输出结果：1 2 3 4 5 6 7 8 9 10
    	cout << endl;
    	auto it = s.upper_bound(6);
    	cout << *it << endl;
    	// 输出结果：7 
    	it = s.upper_bound(15);
    	cout << *it; 
    	// 因为容器中没有 15，所以返回迭代器.end()。输出最后一个元素 10
    	return 0;
    }

### max\_size() ###

返回当前集合能容纳元素的最大限值。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	set<int> s;
    	cout << s.max_size();
    	// 输出结果：461168601842738790
    	return 0;
    }

### find() ###

返回指向键等于 **key** 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

#include<iostream>
    #include<set>
    
    using namespace std;
    
    int main() { 
    	multiset<int> s;
    	s.insert(3);
    	s.insert(2);
    	s.insert(1);
    	
    	auto x = s.find(0);
    	if (x != s.end()) cout << "s 中有 0 元素";
    	else cout << "Not found!"; 
    	// 输出结果：Not found!
    	return 0;
    }

## map / multimap ##

### 简介 ###

**map** 和 **multimap** 将 **key/value pair**（键值/实值 队组）当作元素进行管理，根据 **key** 的排序准则将元素排序。**multimap** 允许重复元素，map则不允许。容器中元素默认按升序排序。**map** 和 **mutilmap** 容器的模板定义在 `#include<map>` 头文件中。基于 `红黑树` 实现。

### insert() ###

向容器中插入一个元素，插入的元素是一个 **pair**。

#include<iostream>
    #include<map>
    
    using namespace std;
    
    int main() { 
    	map<string, int> people;
    	people.insert({ "Chen", 24});
    	people.insert({ "Zhang", 23});
    	for (auto p : people) cout << p.first << ":" << p.second << endl;
    	return 0;
    }

### operator\[\] ###

使用 `[]` 可以返回到映射到等于 **key** 的关键的值的引用，若这种关键不存在则进行插入。通常使用这种方法进行插入。`[]` 里面的值为 **pair** 的第一个值。时间复杂度为 **O( log ⁡ n \\log n logn)**。

#include<iostream>
    #include<map>
    
    using namespace std;
    
    int main() { 
    	map<string, int> people;
    	people["Chen"] = 24;
    	cout << people["Chen"] << endl;
    	// 输出结果：24 
    	cout << people["Zhang"] << endl;
    	
    	for (auto p : people) cout << p.first << ":" << p.second << endl;
    	/* 输出结果：0 Chen:24 Zhang:0 */ 
    	return 0;
    }

### size() ###

返回容器中元素的个数。

### empty() ###

判断当前容器是否为空，如果为空，返回true；否则返回false。

### clear() ###

从容器擦除所有元素。此调用后 **size()** 返回零。

### count() ###

返回拥有关键比较等价于指定参数的元素数，即返回拥有关键 **key** 的元素数。因为 **map** 容器不允许重复故为 **1** 或 **0**。而 **multimap** 返回的个数可能有多个。

### begin() / end() ###

**begin()** 返回指向第一个元素的迭代器。**end()** 返回指向最后一个元素之后一个元素的迭代器。这两个都支持 `++` 和 `--` 操作， 返回前驱和后继。访问容器里面的元素可以使用迭代器访问，也可以使用范围访问。

#include<iostream>
    #include<map>
    
    using namespace std;
    
    int main() { 
    	map<string, int> people;
    	people["Chen"] = 24;
    	// 访问键为 Chen 的元素，如果有则返回其值，如果没有则添加 
    	cout << people["Chen"] << endl;
    	// 输出结果：24 
    	cout << people["Zhang"] << endl;
    	
    	// 1. 使用范围遍历 
    	for (auto p : people) cout << p.first << ":" << p.second << endl;
    	/* 输出结果：0 Chen:24 Zhang:0 */
    	cout << endl;
    	// 2. 使用迭代器遍历 
    	for (map<string, int>::iterator p = people.begin(); p != people.end(); p++) { 
    		cout << p -> first << ":" << p -> second << endl;
    		// 注意：使用迭代器访问返回的是一个指针，所以要使用 -> 访问符来访问 
    	} 
    	// 输出结果与上面的一样 
    	return 0;
    }

### erase() ###

从容器移除指定的元素。一般用法是移除关键等于 **key** 的元素。

#include<iostream>
    #include<map>
    
    using namespace std;
    
    int main() { 
    	map<string, int> people;
    	people["ZhangSan"] = 21;
    	people["LiSi"] = 24;
    	people["WangWu"] = 23;
    	 
    	for (auto p : people) cout << p.first << ":" << p.second << endl;
    	/* 输出结果： LiSi:24 WangWu:23 ZhangSan:21 */
    	puts(""); 
    	// 删除键为 LiSi 的元素 
    	people.erase("LiSi");
    	for (auto p : people) cout << p.first << ":" << p.second << endl;
    	/* 输出结果： WangWu:23 ZhangSan:21 */
    	return 0;
    }

### lower\_bound() / upper\_bound() ###

用法与 **set** 一样，按照 **键值** 进行返回。

### find() ###

返回指向 `键` 等于 **key** 的元素的迭代器。若找不到这种元素，则返回尾后（见 end() ）迭代器。

#include<iostream>
    #include<map>
    
    using namespace std;
    
    int main() { 
    	map<string, int> people;
    	people["ZhangSan"] = 21;
    	people["LiSi"] = 24;
    	people["WangWu"] = 23;
    	
    	auto p = people.find("ZhangSan");
    	if (p != people.end()) cout << p -> first << ":" << p -> second;
    	else cout << "Not found!";
    	return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![2021022215063692.png][]

[C_ STL_2]: https://ac-fun.blog.csdn.net/article/details/113894814
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[2021022215063692.png]: /images/20221024/e7090494bf374a608595135b8c9c4d31.png