突破编程_C++_面试（STL 编程 set 与 multiset）

面试题 1 ：解释一下 set 和 multiset 在 STL 中的区别。

在 C++ 的 STL（Standard Template Library）中，set 和 multiset 都是关联容器，它们存储的元素都是唯一的，并且默认按照升序对元素进行排序。然而，它们在处理重复元素时存在关键的区别。

set：

（1）唯一性： set中的元素是唯一的，即每个元素只能出现一次。如果尝试向set中插入一个已经存在的元素，操作将不会成功，且容器的内容不会改变。

（2）插入和查找： 由于set内部使用了红黑树（一种自平衡的二叉搜索树）作为底层数据结构，因此插入和查找操作的平均时间复杂度都是O(log n)，其中n是容器中元素的数量。

（3）用途： set通常用于需要快速查找唯一元素的情况，比如检查一个值是否存在于某个集合中。

multiset：

（1）允许重复： 与 set 不同，multiset 允许存储重复的元素。可以多次插入相同的元素，每次插入都会成功，并且元素会在容器中保持其插入顺序（或根据提供的比较函数进行排序）。

（2）插入和查找： multiset 同样使用红黑树作为底层数据结构，因此其插入和查找操作的平均时间复杂度也是 O(log n)。

（3）用途： multiset 适用于需要存储可能重复的元素，并且需要按某种顺序对这些元素进行排序的情况。例如，可以使用 multiset 来跟踪某个值出现的次数，或者存储一个按分数排序的学生列表，其中可能有多个学生获得相同的分数。

总结来说，set 和 multiset 的主要区别在于它们对重复元素的处理方式：set 不允许重复元素，而 multiset 则允许。这使得它们各自适用于不同的场景和需求。

面试题 2 ：如何在 set 中查找一个元素？请提供代码示例。

在 std::set 中查找一个元素，可以使用 find 成员函数。find 函数接受一个键作为参数，并返回一个迭代器，指向在容器中第一个等于该键的元素。如果未找到元素，则返回 end() 迭代器。

下面是一个如何在 std::set 中查找一个元素的代码示例：

#include <iostream>  
#include <set>  
  
int main() 
{  
    // 创建一个set容器并插入一些元素  
    std::set<int> mySet = {1, 2, 3, 4, 5};  
  
    // 要查找的元素  
    int elementToFind = 3;  
  
    // 使用find函数查找元素  
    auto it = mySet.find(elementToFind);  
  
    // 检查是否找到了元素  
    if (it != mySet.end()) {  
        // 如果找到了，输出元素的值  
        std::cout << "找到了元素: " << *it << std::endl;  
    } else {  
        // 如果没有找到，输出相应的消息  
        std::cout << "未找到元素" << std::endl;  
    }  
  
    return 0;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在这个例子中，创建了一个包含整数 1 到 5 的 std::set。然后，尝试查找值为 3 的元素。find 函数返回一个指向找到元素的迭代器，或者如果未找到元素，则返回 end() 迭代器。接下来使用 if 语句来检查迭代器是否等于 end()，以确定是否找到了元素。如果找到了元素，则使用解引用迭代器（使用 *it）来获取并输出元素的值。如果未找到元素，则输出一个相应的消息。

面试题 3 ：描述 set 的底层实现原理，以及它是如何保证元素唯一性的。

std::set 在 C++ STL 中的底层实现原理主要依赖于一种特殊的平衡二叉搜索树，通常是红黑树。红黑树是一种自平衡的二叉搜索树，它在插入、删除和查找操作上都能提供相对稳定的对数时间复杂度。这种数据结构保证了 std::set 能够在动态环境中高效地维护元素的排序和唯一性。

下面是关于 std::set 底层实现原理的详细描述：

红黑树的特性：

• 节点着色：每个节点都有一个颜色属性，通常是红色或黑色。
• 根节点特性：根节点是黑色的。
• 所有叶子节点（ NIL 或空节点）都是黑色的：这些叶子节点并不真正存在于树中，而是作为树结束的标记。
• 红色节点的子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
• 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

这些特性保证了红黑树的平衡性，从而确保了 std::set 在插入、删除和查找操作上的效率。

保证元素唯一性的方法：

std::set使用红黑树的特性来确保元素的唯一性。当向 std::set 中插入一个元素时，它会按照以下步骤操作：

• 比较元素：使用提供的比较函数（默认为 std::less），将待插入的元素与树中的元素进行比较。
• 查找插入位置：从根节点开始，沿着树向下搜索，找到待插入元素应该插入的位置。由于红黑树是二叉搜索树，所以这一步骤的时间复杂度是对数的。
• 检查唯一性：如果在搜索过程中找到了与待插入元素相等的节点，说明该元素已经存在于 std::set 中，因此插入操作不会执行，函数会立即返回。
• 插入新节点：如果未找到相等的元素，则在找到的位置插入新的节点，并重新调整树的结构以保持红黑树的特性。这可能包括旋转和重新着色等操作。

由于 std::set 使用红黑树来维护元素的排序和唯一性，所以它的插入、删除和查找操作的平均时间复杂度都是 O(log n)，其中 n 是容器中元素的数量。这使得 std::set 在处理大量数据时仍然能够保持高效的性能。

面试题 4 ：如果一个 set 中有 1000 个元素，如何找到第 500 个插入的元素？

在 C++ 的 std::set 中，元素是按照特定的顺序（默认为升序）存储的，但是 std::set 并不直接提供根据插入顺序来访问元素的功能。这是因为 std::set 是基于红黑树实现的，它主要关注的是元素的唯一性和排序，而不是元素的插入顺序。

如果需要追踪元素的插入顺序，则应该使用另一种容器，比如 std::vector 或者 std::deque，它们保留了元素的插入顺序。

一种可能的方法是使用另一个容器（如 std::list 或 std::vector）来跟踪插入顺序。每次向 std::set 中插入元素时，也同时在跟踪容器中插入该元素的指针或迭代器。这样，就可以通过访问跟踪容器的第 500 个元素来找到 std::set 中第 500 个插入的元素。但

下面是一个简单的示例代码，展示了如何使用 std::set 和 std::list 来跟踪元素的插入顺序：

#include <iostream>  
#include <set>  
#include <list>  
#include <iterator>  

int main()
{
	std::set<int> mySet;
	std::list<std::set<int>::iterator> insertionOrder;

	// 假设插入了一些元素  
	for (int i = 0; i < 1000; ++i) {
		auto it = mySet.insert(mySet.end(), i); // 插入元素到set  
		insertionOrder.push_back(it); // 将迭代器添加到插入顺序列表中  
	}

	// 找到第500个插入的元素  
	if (insertionOrder.size() >= 500) {
		auto it = insertionOrder.begin();
		std::advance(it, 499); // 移动到第500个位置（因为是从0开始计数的）  
		std::cout << "The 500th inserted element is: " << *(*it) << std::endl;
	}
	else {
		std::cout << "There are less than 500 elements in the set" << std::endl;
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

在这个例子中，使用了 std::list 来跟踪向 std::set 中插入元素的顺序。然后，通过使用 std::advance 函数和迭代器来找到第 500 个插入的元素。

需要注意的是，这种方法的效率并不是最优的，因为 std::advance 可能需要O(n)的时间复杂度来移动迭代器到指定的位置。如果你需要频繁地访问特定顺序的元素，可能需要考虑使用不同的数据结构或方法来存储和管理你的数据。

面试题 5 ：如何在 multiset 中查找并删除所有特定的元素？

在 std::multiset 中查找并删除所有特定的元素可以使用 erase 成员函数来完成。erase 成员函数接受一个要删除的元素，然后在 multiset 中查找并删除所有被与输入相等的元素。下面是一个示例代码，展示了如何在 std::multiset 中查找并删除所有特定的元素：

#include <iostream>  
#include <set>  

int main()
{
	// 创建一个multiset并插入一些元素  
	std::multiset<int> myMultiset = { 1, 2, 2, 3, 3, 3, 4, 5 };

	// 要删除的元素  
	int elementToDelete = 3;

	// 使用 erase 删除所有特定元素  
	myMultiset.erase(elementToDelete);

	// 输出 multiset 的内容以验证元素已被删除  
	for (const auto& elem : myMultiset) {
		std::cout << elem << ' ';
	}
	std::cout << std::endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题 6 ：如何在 multiset 中查找并删除所有特定的元素？

为了找到 std::multiset 中出现次数最多的元素及其出现次数，可以遍历整个容器并使用一个辅助容器（如 std::map 或 std::unordered_map）来记录每个元素的出现次数。然后，遍历这个辅助容器来找到出现次数最多的元素。以下是实现这个功能的示例代码：

#include <iostream>  
#include <set>  
#include <map>  
#include <utility>  

int main() 
{
	// 创建一个multiset并插入一些元素  
	std::multiset<int> myMultiset = { 1, 2, 2, 3, 3, 3, 6, 6, 6, 6, 6, 5 };

	// 使用map来记录每个元素的出现次数  
	std::map<int, int> elementCounts;
	for (const auto& elem : myMultiset) {
		elementCounts[elem]++;
	}

	// 初始化出现次数最多的元素及其出现次数  
	int maxCount = 0;
	int mostFrequentElement = 0;

	// 遍历map找到出现次数最多的元素  
	for (const auto& pair : elementCounts) {
		if (pair.second > maxCount) {
			maxCount = pair.second;
			mostFrequentElement = pair.first;
		}
	}

	// 输出结果  
	std::cout << "The element that appears the most frequently is: " << mostFrequentElement << std::endl;
	std::cout << "The number of times it appears is: " << maxCount << std::endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

上面代码的输出为：

The element that appears the most frequently is: 6
The number of times it appears is: 5
1
2

在这个示例中，首先创建了一个 std::multiset 并插入了一些元素。然后，创建了一个 std::map，其键是 multiset 中的元素，值是该元素在 multiset 中出现的次数。遍历 multiset，并使用 map 来统计每个元素的出现次数。

接下来，遍历 map，找到出现次数最多的元素及其次数。

注意：如果有多个元素具有相同的最大出现次数，上述代码只会输出其中一个。如果需要找到所有出现次数最多的元素，则需要稍微修改代码，在找到最大出现次数后，再次遍历 map 来找出所有出现次数等于 maxCount 的元素。