STL中关于集合的容器主要是set，multiset，unordered_set和unordered_multiset四者，后两者是c++11开始引入的，其主要区别可以如下表所示
| set | multiset | unordered_set | |
|---|---|---|---|
| 模板原型 | template<class Key, class Compare = [std::less]<Key>, class Allocator = [std::allocator]<Key>> class set; | template < class T, class Compare = less<T>, class Alloc = allocator<T> > > class multiset; | template < class Key, class Hash = hash<Key>, class Pred = equal_to<Key>, class Alloc = allocator<Key> > class unordered_set; |
| 简介 | 在容器中快速查找键，无重复 | 同前，有重复 | 快速查找 ，无重复 |
| 头文件 | <set> |
<set> |
<unordered_set> |
| 底层实现 | 红黑树 | 红黑树 | 哈希表 |
| 顺序 | 有序，默认升序 | 同前 | 无序 |
| 查找 | 同前 | 平均 |
|
| 插入 | 同前 | 平均 |
|
| 删除 | 同前 | 平均 |
初始化
unordered_set<int> s1
unordered_set<int> s2 {1, 2, 3}
set<string> s3 {"abcc", "123"}
unordered_set<string> s4(s3.begin(), s3.end());
set<string, greater<> > s;
常用方法
几者使用方式很类似。
- 插入：
insert()，支持单个元素和范围 - 查找：
find()，返回指向元素的迭代器，如果没有找到返回end() - 删除：
erase()，删除指定key或者迭代器指向的key或范围 - 清空：
clear()，清空set - 空否：
empty()
set支持的其他方法 - 统计个数：
count() -
set.lower_bound(x) / upper_bound(x)，s.lower_bound(x)表示查找>= x的元素中最小的一个，并返回指向该元素的迭代器，s.upper_bound(x)表示查找>x的元素中最小的一个，并返回指向该元素的迭代器 - 其他结构，可以通过重载
<，
bool operator <(const node &ai,const node &bi)
{
return ai.x > bi.x;
}
其他注意事项
unordered_set不能用来保存pair，但是set可以。如果需要用unordered_set保存其他结构，需要自己手写hash方法。
网友评论