Skip to content

set

set 是一种存储同一数据类型的集合容器，在 set 中每个元素的值都是唯一的；set 内部由 红黑树 实现

environment

下面的示例代码均在该代码框架下运行，若有特定的函数库会另外写出

template.cpp
#include <iostream>
#include <string>
#include <set>

using namespace std; 

int main() {
    // example code here; 
    return 0; 
}

set 的创建及初始化

可以通过初始化列表的形式构造 set，也可以通过复制

init.cpp
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 是否为空

isEmpty.cpp
set<int> s; 

cout << s.empty() << endl;    // true

s.insert(13); 

cout << s.empty() << endl;    // false

size

返回 set 中的元素个数

getSize.cpp
set<int> s{1, 2, 3}; 

cout << s.size() << endl;    // 3

查询函数

count

使用 set.count(key) 将返回 set 内部 key 的个数，但是由于每个 key 都是 唯一的，因此返回的只能是 0 或者 1

count.cpp
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()

find.cpp
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()

lower_bound.cpp
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()

upper_bound.cpp
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 中插入新的元素；

insert.cpp
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>

emplace.cpp
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 中的所有元素

clear.cpp
set<int> s{1, 2, 3}; 

cout << s.size() << endl;   // 3

s.clear(); 

cout << s.size() << endl;   // 0

erase

移除 set 中的对应键，返回被移除的元素个数。（0 或 1）

erase.cpp
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