set容器

set/multiset容器简介

• set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按照一定的顺序排列（默认升序）。元素插入过程是按照排序规则插入，所以不能指定插入位置
• set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树，在插入操作和删除操作上比vector快
• set不可以直接存元素（不可以使用at.(pos)和 [] 操作符）
• multiset与set区别：set支持唯一键值，每个元素只能出现一次；而multiset中同一值可以出现多次
• 不可以直接修改set或multiset容器中的元素值，因为是自动排序。如果修改，只能先删除，在插入新的元素
• #include<set>

构造

set<T> s;

multiset<T> mulset

set<int> setInt;

multiset<int> mulsetInt;

插入和迭代器

set.insert(elem); //插入elem元素

set.begin(); //返回容器第一个元素的迭代器

set.end(); //返回容器最后一个元素之后的迭代器

set.rbegin(); //返回最后一个元素的反向迭代器

set.rend(); //返回反向的最后一个元素（第一个元素）的迭代器

拷贝构造与赋值

set(const set &st); //拷贝构造函数

set &operator=(const set &st); //=操作符重载，直接进行复制

set.swap(st); //交换两个set容器

大小

set.size(); //返回容器中元素数目

set.empty(); //判断容器是否为空

删除

set.clear(); //清除所有元素

set.erase(pos); //删除pos所指的元素，返回下一个元素的迭代器

set.erase(beg, end); //删除[beg, end)的所有元素

set.erase(elem); //删除容器中elem元素，返回值为true; 如果elem不在容器中，返回值为false

set容器的erase不支持通过反向迭代器进行删除

元素排序

set<int, less<int>> setIntA; //按升序方式排列元素

set<int, greater<int>> setIntB; //按降序方式排序元素

class Student{
    private:
    int m_iID;	//学号
    string m_strName;	//姓名
    
    public:
    CStudent(int iID, string strName){
    	m_iID = iID;
        m_strName = strName;
    }
};

//伪函数类
class StuFunctor{
    public:
	bool operator()(const CStudent &s1, const CStudent &s2){
   	  return s1.m_iID < s2.m_iID;	//升序排列
  }  
};

set<CStudent, StuFunctor> stu;
stu.insert(CStudent(1, "A"));
stu.insert(CStudent(3, "B"));
stu.insert(CStudent(2, "C"));
stu.insert(CStudent(4, "D"));

// 1 2 3 4 / A C B D

查找

set.find(elem); //查找elem元素，返回指向elem的迭代器

set.count(elem); //返回容器中elem的个数（对set：0或1；对multiset：可能大于1）

set.lower_bound(elem); //返回第一个>=elem元素的迭代器

set.upper_bound(elem); //返回第一个>elem元素的迭代器

equal_range

set.equal_range(elem);

返回两个迭代器：分别为lower_bound 和 upper_bound

set<int> s1; 	//1 3 5 6 7 8 10

pair<set<int> :: iterator, set<int> :: iterator> p = s1.equal_range(5);
cout << *(p.first) << endl;		//5
cout << *(p.second) << endl;	//6