本文主要简述集合的原理和用法,便于快速学习和查阅。
集合的原理
set是一个内部自动有序且不含重复元素的容器。
set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的数据结构,在插入元素时,它会自动调整二叉树的排列,把该元素放到适当的位置,以确保每个子树根节点的键值大于左子树所有节点的键值,而小于右子树所有节点的键值。
另外,还得确保根节点左子树的高度与右子树的高度相等,这样,二叉树的高度最小,从而检索速度最快。
要注意的是,它不会重复插入相同键值的元素,而采取忽略处理。如图是一个典型的红黑树。
平衡二叉检索树的检索使用中序遍历算法,中序遍历算法可将键值由小到大遍历出来,所以,可以理解为平衡二叉检索树在插入元素时,就会自动将元素按键值由小到大的顺序排列。
集合的使用
#include<set>
创建集合时需要指定元素的类型。
set<Data_Type> name;
Data_Type 为集合存储的数据的类型,name 为集合的名称。例如:
set<int> s; // 命名为s的集合存储整型数据
s.insert(Data_Type);
Data_Type 类型与声明集合时的类型相同。
例如:
s.insert(1);
默认的比较规则下,是按元素值由小到大插入;如果自己指定了比较规则函数,则按自定义比较规则函数插入。
- 遍历
begin()
和 end()
两个方法分别表示集合中第一个和最后一个元素。
set<int>::iterator it; // 定义向前迭代器
for (it = s.begin(); it != s.end(); it++) // 由第一个元素至最后一个元素
cout << *it << endl; // 输出该值
使用反向迭代器reverse_iterator
可以反向遍历集合。需要使用 rbegin()
和 rend()
两个方法,分别给出反向遍历的开始位置和结束位置。
set<int>::reverse_iterator rit; // 定义反向迭代器
for (rit = rbegin(); rit != rend(); rit++)
cout << *rit << endl;
删除的对象可以是某个迭代器位置上的元素、等于某键值的元素、一个区间上的元素。
删除某个元素用erase()
。
s.erase(Data_Type);
Data_Type 为定义时集合存储数据的类型。
例如:
s.erase(1);
运用clear()
将集合中元素全部删除。
s.clear();
使用find()
方法对集合进行检索。如果找到该值,就返回该值迭代的位置;否则返回集合最后一个元素后一个位置,即end()
。
set<int>::iterator it;
it = s.find(Data_Type);