为什么需要
set
和multiset
:
1.自动排序: set和multiset会自动按照元素的值进行排序。
2.快速查找: 由于元素是有序的,set和multiset可以提供对元素的快速查找,通常是基于二叉搜索树实现的,查找操作的时间复杂度为O(log n)。
3.set的唯一性保证: set保证了容器中元素的唯一性,即不会有重复的元素。这在需要确保数据集中没有重复项时非常有用。
1.实例化std::set和std::multiset
需要添加头文件<set>
//默认类型实例化
std::set<int> mySet;
std::multiset<int> myMultiSet;//自定义类实例化(假设有MyClass类)
std::set<MyClass> mySet;
std::multiset<MyClass> myMultiSet;
2.在set或multiset中插入元素
可以使用insert()
下面以set
为例子展示,multiset
操作与其一致,但允许插入重复元素
#include<iostream>
#include <set>
int main(){std::set<int> mySet;// 插入单个元素mySet.insert(10);for(int num:mySet){std::cout<<num<<" ";}//输出结果为10std::cout<<std::endl;// 插入多个元素mySet.insert({30, 20, 40});for(int num:mySet){std::cout<<num<<" ";}//输出结果10 20 30 40,因为会插入元素后会自动排序std::cout<<std::endl;// 插入迭代器范围内的元素int arr[] = {50, 60, 70};mySet.insert(std::begin(arr), std::end(arr));for(int num:mySet){std::cout<<num<<" ";}//输出结果为10 20 30 40 50 60 70system("pause");return 0;
}
3.在set或multiset中查找元素
使用find()
成员函数,用于查找容器中是否存在某个元素。它返回一个迭代器,如果元素存在,则指向找到的元素;如果元素不存在,则返回end()。
下面以set
为例子展示,multiset
操作与其一致,但若含有多个相同的符合条件的值,则只指向第一个
#include<iostream>
#include <set>
int main(){std::set<int> mySet = {1, 2, 3, 4, 5};auto it1 = mySet.find(3); // 查找元素 3if (it1 != mySet.end()) {// 找到元素std::cout << "Found: " << *it1 << std::endl;} else {// 元素不存在std::cout << "Not found" << std::endl;}//输出结果为“Found:3”auto it2 = mySet.find(6); // 查找元素 3if (it2 != mySet.end()) {// 找到元素std::cout << "Found: " << *it2 << std::endl;} else {// 元素不存在std::cout << "Not found" << std::endl;}//输出结果为“Not found”system("pause");return 0;
}
4.删除set或multiset中的元素
使用erase()
成员函数,有以下几个重载版本
删除特定元素
mySet.erase(someValue); // 删除一个特定值
删除迭代器指向的元素
auto it = mySet.find(someValue);
if (it != mySet.end()) {mySet.erase(it); // 删除迭代器指向的元素
}
删除一定范围内的元素
mySet.erase(mySet.begin(), mySet.end()); // 使用迭代器指定边界
下面以multiset
为例子,set
操作类似
#include <iostream>
#include <set>int main() {// 实例化一个 std::multisetstd::multiset<int> myMultiSet = {1, 2, 3, 4, 4, 5};// 创建一个副本,删除指定值4auto count1 = myMultiSet;count1.erase(4);for(auto num:count1){std::cout<<num<<" ";}//输出结果为1 2 3 5,会把所有符合条件的都删除std::cout<<std::endl;// 创建一个副本,删除迭代器指向的元素3auto count2 = myMultiSet;auto it = count2.find(3);if (it != count2.end()) {count2.erase(it);}for(auto num:count2){std::cout<<num<<" ";}//输出结果为1 2 4 4 5std::cout<<std::endl;// 创建一个副本,删除一定范围的元素auto count3 = myMultiSet;count3.erase(count3.begin(), count3.find(3));//把开头到元素3(不包括3)都删除for(auto num:count3){std::cout<<num<<" ";}//输出结果为3 4 4 5system("pause");return 0;
}
5.std::unordered_set
和std::unordered_multiset
从C++11起引入了这两种容器,它们是基于散列表(哈希表)实现的,相较于set和multiset,他们有以下优缺点:
优点
- 平均时间复杂度: 由于哈希表的特性,在理想情况下,插入、删除和查找操作平均时间复杂度为O(1),比set和multiset的O(log n)更快
- 更快的访问速度: 在元素较多且冲突较少的情况下,访问速度更快
缺点
- 最坏情况时间复杂度: 在最坏情况下,时间复杂度为O(n),比set和multiset更慢
- 不适合有序遍历: 这两种容器不保证元素的有序性