set¶
set 是一种存储同一数据类型的集合容器,在 set 中每个元素的值都是唯一的;set 内部由 红黑树 实现
environment
下面的示例代码均在该代码框架下运行,若有特定的函数库会另外写出
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main() {
// example code here;
return 0;
}
set 的创建及初始化¶
可以通过初始化列表的形式构造 set,也可以通过复制
set<int> nums1{1, 2, 3, 4, 5};
for (auto& num: nums1) {
cout << num << " ";
}
// 1 2 3 4 5
set<int> nums2(nums1.begin(), nums1.end());
// which equal to
// set<int> nums2(nums1);
for (auto& num: nums2) {
cout << num << " ";
}
// 1 2 3 4 5
属性查询函数¶
empty
¶
返回 set 是否为空
set<int> s;
cout << s.empty() << endl; // true
s.insert(13);
cout << s.empty() << endl; // false
size
¶
返回 set 中的元素个数
set<int> s{1, 2, 3};
cout << s.size() << endl; // 3
查询函数¶
count
¶
使用 set.count(key)
将返回 set 内部 key 的个数,但是由于每个 key 都是 唯一的,因此返回的只能是 0 或者 1
set<int> s{1, 2, 3, 4};
cout << "there is " << s.count(4) << " `4` in set\n";
// there is 1 `4` in set
cout << "there is " << s.count(0) << " `0` in set\n";
// there is 0 `0` in set
find
¶
使用 set.find(key)
将返回 set 内部 key 对应的迭代器,如果没有则返回 end()
set<int> s{1, 2, 3, 4};
int key = 1;
auto it = set.find(key);
if (it != s.end()) {
cout << "we find" << (*it) << " in set\n";
}
else {
cout << "we can not find" << key << " in set\n";
}
// we find 1 in set
lower_bound
¶
使用 lower_bound(iterator begin, iterator end, key)
返回首个 不小于 (即大于等于)对应 key 的元素的迭代器;如果查找不到返回 set.end()
set<int> t{3, 1, 4, 5}
cout << *lower_bound(t.begin(), t.end(), 3) << endl; // 3
cout << *upper_bound(t.begin(), t.end(), 3) << endl; // 4
upper_bound
¶
使用 upper_bound(iterator begin, iterator end, key)
返回首个 大于 对应 key 的元素的迭代器;如果查找不到返回 set.end()
set<int> t{3, 1, 4, 5}
cout << *lower_bound(t.begin(), t.end(), 3) << endl; // 3
cout << *upper_bound(t.begin(), t.end(), 3) << endl; // 4
修改函数¶
insert
¶
若 set 中没有对应元素,则在 set 中插入新的元素;
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
for (auto& i : s) cout << i << ' ';
// 1 2 3
emplace
¶
若 set 中没有对应元素,则在 set 中插入以给定的 参数 原位构造的新元素;返回由指向被插入元素,或若不发生插入则为既存元素的迭代器,和指代插入是否发生的 bool
(若发生插入则为 true
,否则为 false
)构成的 pair<iterator, bool>
set<int> s;
s.emplace(1);
s.emplace(2);
s.emplace(3);
for (auto& i : s) cout << i << ' '; // 1 2 3
Tip
emplace
在 C++11 添加,相较于 insert
效率上有一定提升;emplace
最大的作用是避免产生不必要的临时变量,详情参考 https://en.cppreference.com/w/cpp/container/set/emplace
clear
¶
清除 set 中的所有元素
set<int> s{1, 2, 3};
cout << s.size() << endl; // 3
s.clear();
cout << s.size() << endl; // 0
erase
¶
移除 set 中的对应键,返回被移除的元素个数。(0 或 1)
set<int> s{1, 2, 3};
for (auto& i : s) cout << i << ' '; // 1 2 3
cout << endl;
s.erase(3);
for (auto& i : s) cout << i << ' '; // 1 2