一、set容器介绍
Set是C++ STL的一种关联式容器,它类似于一个集合,其中不可以出现相同的元素,同时元素是按照一定顺序排列的。
Set容器是通过对元素进行排序和去重来实现这些特性的,因此在使用时需要注意元素的比较和去重规则。
Set的内部实现是红黑树,因此插入、删除和查找元素操作都具有较好的时间复杂度,常数级别的低。
二、set容器的基本操作
对于Set容器,最基本的操作包括插入元素、删除元素和查找元素。下面是对这三个操作的介绍:
1. 插入元素
#include <set>
#include <iostream>
int main() {
std::set
s;
s.insert(3);
s.insert(1);
s.insert(4);
s.insert(1);
for (auto it = s.begin(); it != s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}
输出结果为:1 3 4。
从结果可以看到,1并没有被重复插入,这是因为Set容器的特性,它会自动去重。
2. 删除元素
#include <set>
#include <iostream>
int main() {
std::set
s;
s.insert(3);
s.insert(1);
s.insert(4);
s.erase(1);
for (auto it = s.begin(); it != s.end(); it++) {
std::cout << *it << " ";
}
return 0;
}
输出结果为:3 4。
从结果可以看到,我们通过erase函数删除了Set容器中的一个元素1,Set容器的自动去重特性也保证了删除操作的正确性。
3. 查找元素
#include <set>
#include <iostream>
int main() {
std::set
s;
s.insert(3);
s.insert(1);
s.insert(4);
auto it = s.find(3);
if (it != s.end()) {
std::cout << "Found " << *it << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
return 0;
}
输出结果为:Found 3。
从结果可以看到,我们通过find函数在Set容器中查找了元素3,并输出了查找结果。
三、set容器的排序规则
Set容器的特性使得其中的元素按照一定规则排序,常见的排序规则包括从小到大排序和从大到小排序。
在C++ STL的Set容器中,默认的排序规则是从小到大排序,即元素类型的小于号(<)被定义为元素的比较运算符。如果需要修改Set容器的排序规则,可以通过自定义比较函数来实现。
1. 从小到大排序
#include <set>
#include <iostream>
struct Student {
std::string name;
int age;
bool operator<(const Student& other) const {
return name < other.name;
}
};
int main() {
std::set
s;
s.insert({"Tom", 18});
s.insert({"Alice", 20});
s.insert({"Bob", 19});
for (auto& it : s) {
std::cout << it.name << " " << it.age << std::endl;
}
return 0;
}
输出结果为:Alice 20
Bob 19
Tom 18
从结果可以看出,这里我们自定义了Student结构体的小于号比较运算符为按照姓名从小到大排序,因此Set容器中的元素被按照这个规则排序了。
2. 从大到小排序
#include <set>
#include <iostream>
struct Student {
std::string name;
int age;
bool operator<(const Student& other) const {
return name > other.name;
}
};
int main() {
std::set
s;
s.insert({"Tom", 18});
s.insert({"Alice", 20});
s.insert({"Bob", 19});
for (auto& it : s) {
std::cout << it.name << " " << it.age << std::endl;
}
return 0;
}
输出结果为:Tom 18
Bob 19
Alice 20
从结果可以看出,这里我们同样自定义了Student结构体的小于号比较运算符,不同的是按照姓名从大到小排序。这个比较函数和从小到大排序的比较函数仅仅是在小于号的返回值上取反了而已。
四、set容器的应用场景
Set容器作为一个可以去重排序的容器,在实际开发中有许多应用场景,下面介绍其中的两个常见的应用场景。
1. 统计单词数目
#include <set>
#include <iostream>
#include <sstream>
int main() {
std::string str = "apple banana apple orange banana";
std::istringstream iss(str);
std::set
s;
std::string word;
while (iss >> word) {
s.insert(word);
}
std::cout << s.size() << std::endl;
return 0;
}
输出结果为:3。
这里我们利用了Set容器的自动去重特性来统计字符串中单词数目。将字符串中的单词插入到Set容器中,这样Set容器中的元素就是不重复的单词,Set容器的size()函数就可以得到单词数目了。
2. 求两个数组的交集
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector
v1 = {1, 3, 5, 7, 9};
std::vector
v2 = {2, 3, 5, 7, 8};
std::set
s1(v1.begin(), v1.end());
std::set
s2(v2.begin(), v2.end());
std::vector
v3; std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(v3)); for (auto& it : v3) { std::cout << it << " "; } return 0; }
输出结果为:3 5 7。
这里我们利用了Set容器的自动去重和排序特性,将两个数组分别转换为Set容器,这样两个Set容器的交集就是两个数组的交集,利用STL的set_intersection算法,便可以得到两个数组的交集。
总结
本文对Set容器进行了一系列的介绍和讲解,从基本操作到排序规则再到实际应用场景,都有详细的阐述。Set容器是C++ STL中十分常用且实用的容器,掌握Set容器的使用方法和特性对于编程开发人员来说是很重要的。