突破编程_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 到 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;
}
在这个例子中，使用了 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;
}
面试题 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;
}
上面代码的输出为：
The element that appears the most frequently is: 6
The number of times it appears is: 5
在这个示例中，首先创建了一个 std::multiset 并插入了一些元素。然后，创建了一个 std::map，其键是 multiset 中的元素，值是该元素在 multiset 中出现的次数。遍历 multiset，并使用 map 来统计每个元素的出现次数。
接下来，遍历 map，找到出现次数最多的元素及其次数。
注意：如果有多个元素具有相同的最大出现次数，上述代码只会输出其中一个。如果需要找到所有出现次数最多的元素，则需要稍微修改代码，在找到最大出现次数后，再次遍历 map 来找出所有出现次数等于 maxCount 的元素。