考研复试，机试，set用法
1. 包含头文件
要使用 set，需要包含 <set> 头文件。
#include <set>
2. 定义和初始化 set
#include <iostream>
#include <set>
using namespace std;
int main() {
// 定义一个存储 int 类型元素的 set
set<int> s;
// 也可以在定义时初始化
set<int> s2 = {3, 1, 2};
return 0;
}
3. 插入元素
使用 insert 方法向 set 中插入元素。如果插入的元素已经存在，insert 操作不会产生实际效果。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(5);
s.insert(3);
s.insert(7);
s.insert(3); // 重复元素，不会插入
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
4. 查找元素
使用 find 方法查找元素。如果找到，返回指向该元素的迭代器；如果未找到，返回 end() 迭代器。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {1, 3, 5, 7};
auto it = s.find(3);
if (it != s.end()) {
cout << "Found: " << *it << endl;
} else {
cout << "Not found" << endl;
}
return 0;
}
5. 删除元素
使用 erase 方法删除元素，可以通过元素值或迭代器来指定要删除的元素。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {1, 3, 5, 7};
s.erase(3); // 通过元素值删除
auto it = s.find(5);
if (it != s.end()) {
s.erase(it); // 通过迭代器删除
}
for (int num : s) {
cout << num << " ";
}
cout << endl;
return 0;
}
6. 遍历 set
可以使用迭代器或范围 for 循环来遍历 set 中的元素。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {2, 4, 6, 8};
// 使用迭代器遍历
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// 使用范围 for 循环遍历
for (int num : s) {
cout << num << " ";
}
cout << endl;
return 0;
}
7. 获取 set 的大小
使用 size 方法获取 set 中元素的数量。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s = {1, 2, 3};
cout << "Size of set: " << s.size() << endl;
return 0;
}
8. 检查 set 是否为空
使用 empty 方法检查 set 是否为空。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
if (s.empty()) {
cout << "Set is empty" << endl;
}
return 0;
}
-----------------------------------------------------
std::set 之外，还有 std::multiset、std::unordered_set 和 std::unordered_multiset
在 C++ 中，除了 std::set 之外，还有 std::multiset、std::unordered_set 和 std::unordered_multiset 这几种容器，它们在有序性、元素重复性方面各有特点，下面分别介绍。
1. std::set
- 有序性：
set是有序容器，元素会根据元素类型的比较运算符（默认是<）进行自动排序，插入和查找操作都会维护这种有序性。 - 元素重复性：不允许有重复元素，插入重复元素时，操作会被忽略。
示例代码
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(1); // 重复元素，插入无效
for (int num : s) {
cout << num << " "; // 输出: 1 2 3
}
cout << endl;
return 0;
}
2. std::multiset
- 有序性：和
set一样，multiset也是有序容器，元素会按照元素类型的比较运算符自动排序。 - 元素重复性：允许有重复元素，插入重复元素时，会将其正常添加到容器中。
示例代码
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms;
ms.insert(3);
ms.insert(1);
ms.insert(2);
ms.insert(1); // 重复元素，正常插入
for (int num : ms) {
cout << num << " "; // 输出: 1 1 2 3
}
cout << endl;
return 0;
}
3. std::unordered_set
- 有序性：
unordered_set是无序容器，它使用哈希表来存储元素，元素的存储顺序是根据哈希函数计算的哈希值决定的，不会按照元素值的大小进行排序。 - 元素重复性：不允许有重复元素，插入重复元素时，操作会被忽略。
示例代码
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> us;
us.insert(3);
us.insert(1);
us.insert(2);
us.insert(1); // 重复元素，插入无效
for (int num : us) {
cout << num << " "; // 输出顺序不确定
}
cout << endl;
return 0;
}
4. std::unordered_multiset
- 有序性：同样是无序容器，基于哈希表实现，元素存储顺序由哈希函数决定。
- 元素重复性：允许有重复元素，插入重复元素时，会将其正常添加到容器中。
示例代码
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_multiset<int> ums;
ums.insert(3);
ums.insert(1);
ums.insert(2);
ums.insert(1); // 重复元素，正常插入
for (int num : ums) {
cout << num << " "; // 输出顺序不确定
}
cout << endl;
return 0;
}
选择建议
- 需要有序且无重复元素：使用
std::set，例如存储不重复的学号并按学号升序排列。 - 需要有序且允许重复元素：使用
std::multiset，例如存储学生成绩，可能有多个学生成绩相同且需要按成绩排序。 - 不需要有序且无重复元素：使用
std::unordered_set，例如检查一个字符串中是否有重复字符，无序情况下可以提高插入和查找效率。 - 不需要有序且允许重复元素：使用
std::unordered_multiset，例如统计一篇文章中每个单词的出现次数，不关心单词的顺序。
--------------------------------------------------------------------
补充set的find和count
1. find 函数
功能
find 函数用于在 set 中查找具有指定值的元素。如果找到该元素，它会返回一个指向该元素的迭代器；如果未找到，它会返回 end() 迭代器，这表示超出了 set 中元素的范围。
语法
iterator find(const value_type& val); const_iterator find(const value_type& val) const;
其中，value_type 是 set 中存储的元素类型，val 是要查找的值。
示例代码
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> mySet = {1, 3, 5, 7, 9};
// 查找值为 5 的元素
auto it = mySet.find(5);
if (it != mySet.end()) {
cout << "Found element: " << *it << endl;
} else {
cout << "Element not found." << endl;
}
// 查找值为 4 的元素
it = mySet.find(4);
if (it != mySet.end()) {
cout << "Found element: " << *it << endl;
} else {
cout << "Element not found." << endl;
}
return 0;
}
代码解释
- 首先创建了一个
set并初始化了一些元素。 - 然后使用
find函数查找值为 5 的元素，由于 5 在set中，所以能找到并输出该元素。 - 接着查找值为 4 的元素，由于 4 不在
set中，find函数返回end()迭代器，因此输出“Element not found.”。
2. count 函数
功能
count 函数用于统计 set 中具有指定值的元素的数量。因为 set 中的元素是唯一的，所以 count 函数的返回值只有两种可能：0 或 1。如果元素存在，返回 1；如果元素不存在，返回 0。
语法
size_type count(const value_type& val) const;
其中，size_type 是表示容器大小的无符号整数类型，val 是要统计的元素的值。
示例代码
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> mySet = {2, 4, 6, 8};
// 统计值为 6 的元素数量
size_t count6 = mySet.count(6);
cout << "Count of 6: " << count6 << endl;
// 统计值为 5 的元素数量
size_t count5 = mySet.count(5);
cout << "Count of 5: " << count5 << endl;
return 0;
}
代码解释
- 同样先创建一个
set并初始化元素。 - 使用
count函数统计值为 6 的元素数量，由于 6 在set中，所以返回 1。 - 再统计值为 5 的元素数量，由于 5 不在
set中，所以返回 0。
总结
find函数主要用于查找元素并返回其迭代器，方便后续对该元素进行操作。count函数则用于快速判断元素是否存在于set中，返回值简洁明了。在实际使用中，可以根据具体需求选择合适的函数。
考研机试常用的数据结构 文章被收录于专栏
考研机试常用的数据结构
