set

std::set 是 C++ 标准库中的有序关联容器，用来存储“唯一键集合”。

它的核心特点是：

1. 元素按比较规则自动有序。
2. 元素值本身就是键。
3. 键不允许重复。

头文件与基本特征

使用 set 时，需要包含头文件：

#include <set>

set 的常见特征如下：

特征	说明
键是否重复	不允许重复
是否有序	是
底层结构	通常为平衡二叉搜索树
查找复杂度	平均和最坏通常 O(log n)
修改元素值	不允许直接改键值

基本用法

#include <set>

int main() {
	std::set<int> s;

	s.insert(3);
	s.insert(1);
	s.insert(2);
	s.insert(2);  // 重复元素不会再次插入

	return 0;
}

set 中最终元素顺序是 1 2 3，并且只有一份 2。

遍历 set

#include <iostream>
#include <set>

int main() {
	std::set<int> s;
	s.insert(30);
	s.insert(10);
	s.insert(20);

	for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
		std::cout << *it << ' ';
	}
	std::cout << '\n';

	return 0;
}

遍历输出会按有序规则排列，而不是按插入顺序。

常用成员函数

函数	作用
insert()	插入元素
erase()	删除元素
find()	查找元素
count()	统计元素个数（set 中为 0 或 1）
lower_bound()	第一个不小于目标值的位置
upper_bound()	第一个大于目标值的位置
equal_range()	同时返回上下界
size() / empty()	数量与判空
clear()	清空容器

插入返回值

set::insert() 返回一个 pair<iterator, bool>，可用来判断是否插入成功：

#include <set>

int main() {
	std::set<int> s;
	std::pair<std::set<int>::iterator, bool> ret = s.insert(100);

	if (ret.second) {
		// 插入成功
	} else {
		// 元素已存在
	}

	return 0;
}

自定义排序

默认按升序排序，可以传入比较器改为降序等规则：

#include <set>

struct Greater {
	bool operator()(int lhs, int rhs) const {
		return lhs > rhs;
	}
};

int main() {
	std::set<int, Greater> s;
	s.insert(1);
	s.insert(3);
	s.insert(2);

	return 0;
}

set 与 map 的区别

1. set 存的是“值本身”，可看成只关心键的集合。
2. map 存的是“键值对”，适合做映射表。
3. 两者都默认有序，查找复杂度通常是 O(log n)。

使用注意

1. set 元素作为键，不应通过迭代器直接修改值。
2. 需要允许重复元素时，使用 multiset。
3. 如果不需要有序、只追求平均更快查找，可考虑 unordered_set（C++11 及以后更常见）。