STL中set的基本介绍

STl中的基本内容

容器

set/multiset

在集合中，所有的元素只能出现一次，并且默认按照元素的值从小到大自动排序

set不能通过迭代器来修改元素的值，即set的迭代器是一种const_iterator

multiset 和 set 的区别在于multiset中允许有重复的元素

内部采用的是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。这种结构使得集合在进行插入删除的时候，具有较高的效率，它不需要移动其他的元素，只需要改变个别元素之间的连接关系。同时，正式因为如此，在插入删除的过程中不会发生元素内存地址的改变（例如，如果在vector容器中，当加入的元素已经大于容器原来的最大容量时，就需要为容器申请新的更大的内存空间，并将之前的内容拷贝过去，这既降低了效率，又使得之前获取的迭代器失效），之前保存下来的迭代器仍然指向原来的内存地址，因此不会发生迭代器失效的问题。

set的声明和赋值

set<int> st;  //声明了一个int类型的集合 默认元素按照从小到大的顺序排序
set<int,cmp> stt;  //声明的stt集合中，元素按照cmp中规定的顺序进行排序
set<int> st_copy(st);  //使用拷贝构造函数
set<int> s_t;
swap(st,s_t);  //交换两个集合中的元素

set的大小和空判断

st.size();  //返回集合的大小也就是元素的个数
st.empty();  //返回集合是否为空，如果是空返回为真

set的插入操作

for(int i=10;i>0;i--)
    st.insert(i);   //按顺序插入，但是set中的顺序为从小到大
for(set<int>::iterator it=st.begin();it!=st.end();it++)
    cout<<*it<<" ";   //1 2 3 4 5 6 7 8 9 10

st.insert(it_begin,it_end);  //把[it_begin,it_end)区间内的值插入到st中

//由于集合中的元素只能出现一次,在执行st.insert(5);其实是没有进行操作的
pair<set<int>::iterator,bool> test=st.insert(5);
if(test.second)
    cout<<"插入成功"<<endl;
else
    cout<<"插入失败"<<endl;
//输出结果为插入失败

set的删除操作

st.erase(key);  //删除集合中值为5的元素
st.erase(it_begin,it_end);  //删除集合中[it_begin,it_end)之间的元素
st.erase(index);  //删除迭代器index所指向位置的元素
st.clear();  //删除集合中的全部元素

set的查找操作

st.find(key);  //在集合中查找键key是否存在，若存在则返回指向该位置处的迭代器，若不存在，则返回st.end()
st.count(key);  //返回值为集合中键key的元素个数 在set中只能是0/1
st.upper_bound(key);  //返回第一个键大于key的元素的迭代器
st.lower_bound(key);  //返回第一个键大于等于key的元素的迭代器
st.equal_range(key);  //返回集合中键与key相当的上下限的两个迭代器

下面来一个完整的示例

#include <iostream>
#include <set>
using namespace std;
class Student {
public:
    Student(char x, int y) :name(x), score(y) {};
    char name;
    int score;
    bool operator <(const Student& c) const
    {
        return this->score < c.score;
    }

};
struct cmp {
    bool operator()(Student a1, Student a2) const
    {
        return a1.score > a2.score;
    }
};
void show(set<Student> s)
{
    for (set<Student>::iterator it = s.begin(); it != s.end(); it++) 
        cout << it->name << " " << it->score << endl; 
    cout << endl;
}
void show(set<Student, cmp> s)
{
    for (set<Student>::iterator it = s.begin(); it != s.end(); it++)
        cout << it->name << " " << it->score << endl; 
    cout << endl;
}
int main()
{
    //按照自定义规则排序
    set<Student> s;
    set<Student, cmp> rs;
    for (int i = 0; i <= 5; i++)
        s.insert(Student('a'+i, (i+1)*10)), rs.insert(Student('a'+i, (i+1)*10));
    show(s);  //按照成绩升序排列
    show(rs);  //按照成绩降序排列
    rs.erase(rs.find(Student('d', 40)));  //删除('d',40)的元素
    show(rs); 
    s.erase(s.begin(), s.upper_bound(Student('b', 20)));  //删除所有成绩不大于20的元素
    show(s);
    while (!s.empty())  s.erase(s.begin());  //清空集合
    rs.clear();  //清空集合
}

运行结果如下