[STL] set & multiset

前言

第一次写这种关于某一个类的常用方法的总结, 参考了Sam 大叔的文章STL之list容器详解, 之后根据cppreference.com网站的资料归纳而来

Set 与 multiset 容器

template<
	class Key, 
	class Compare = std::less<Key>, 
	class Allocator = std::allocator<Key>
> class set;
template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class multiset;

set 是C++标准模版库(STL)中的部分内容.
通过比较函数 Compare 进行排序, 通常使用红黑树实现(还没有学到, 暂时理解为二叉搜索树)
multiset 与 set 差不多, 不同之处在于它允许拥有多个相同键的值
使用这两个容器之前必须添加头文件 #include <set>, 它们都属于std命名域

常用函数描述及示例

函数	复杂度	描述	示例
构造函数	(O(1))	创建一个集合/复合集合容器	set S; multiset S;
size()	(O(1))	返回set中的元素数	cout << S.size()
clear()	(O(n))	清空set	S.clear()
begin()	(O(1))	返回指向set开头的迭代器	set::iterator it = S.begin();
end()	(O(1))	返回指向set末尾的迭代器	set::iterator end = S.end();
insert(k)	(O(log_{n}))	向set中插入元素k	S.insert(6);
erase(k)	(O(log_{n}))	删除键值为k的元素	S.erase(6);
find(k)	(O(log_{n}))	搜索键值为k的元素, 并返回指向该元素的迭代器, 如果没有, 则返回末尾end()	if (S.find(6) != S.end()) cout << "find 6";
count(k)	(O(log_{n}))	返回与k键值相同的元素的数量	cout << S.count(6);
lower_bound(k)	(O(log_{n}))	搜索第一个不小于k键值的元素, 并返回指向该元素的迭代器, 如果没有则返回末尾end()	set::iterator it = S.lower_bound(6);
upper_bound(k)	(O(log_{n}))	搜索第一个大于k键值的元素, 并返回指向该元素的迭代器, 如果没有则返回末尾end()	set::iterator it = S.upper_bound(6);

练习题目

Set: Search
Set: Delete
Set: Range Search
Multi-Set

以下为当时写的代码, 虽然不够简洁, 但是基础的函数都用到了

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n, com, x;
	set<int> s;
	scanf("%d", &n);
	while (n--) {
		scanf("%d %d", &com, &x);
		if (com == 0) {
			s.insert(x);
			printf("%d
", s.size());
		} else {
			if (s.find(x) != s.end())
				printf("1
");
			else 
				printf("0
");
		}
	}	
}

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	set<int> S;
	int q, com, value;
	cin >> q;
	while (q--) {
		cin >> com >> value;
		switch (com) {
			case 0:
				S.insert(value);
				cout << S.size() << endl;
				break;
			case 1:
				if (S.find(value) != S.end()) {
					cout << "1
";
				} else {
					cout << "0
";
				}
				break;
			case 2:
				S.erase(value);
				break;
		}
	}
}

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	set<int> S;
	int q, com, x, y;
	cin >> q;
	while (q--) {
		cin >> com;
		switch (com) {
			case 0:
				cin >> x;
				S.insert(x);
				cout << S.size() << endl;
				break;
			case 1:
				cin >> x;
				if (S.find(x) != S.end()) {
					cout << "1
";
				} else {
					cout << "0
";
				}
				break;
			case 2:
				cin >> x;
				S.erase(x);
				break;
			case 3:
				cin >> x >> y;
				set<int>::iterator it = S.lower_bound(x);
				set<int>::iterator end = S.upper_bound(y);
				while (it != end) {
					cout << *it << endl;
					it++;
				}
				break;
		}
	}
}

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	multiset<int> S;
	int q, com, x, y;
	cin >> q;
	while (q--) {
		cin >> com;
		switch (com) {
			case 0:
				cin >> x;
				S.insert(x);
				cout << S.size() << endl;
				break;
			case 1:
				cin >> x;
				cout << S.count(x) << endl;
				break;
			case 2:
				cin >> x;
				S.erase(x);
				break;
			case 3:
				cin >> x >> y;
				set<int>::iterator it = S.lower_bound(x);
				set<int>::iterator end = S.upper_bound(y);
				while (it != end) {
					cout << *it << endl;
					it++;
				}
				break;
		}
	}
}