set使用方法

简单介绍一下:

set容器,实现了红黑树的平衡二叉检索树的数据结构,插入元素时(元素是唯一的),它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等(所以不能指定插入位置)。
平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索,不可直接去修改键值。

构造形式:set<T> setT 尖括号里面可以自定义类型

常用函数:

setT.insert(x);  //插入一个元素,时间复杂度O(logn)
setT.erase(x);   //删除键值为x的元素,时间复杂度O(logn)
setT.count();    //返回匹配特定键的元素数量,时间复杂度O(logn)
setT.clear();    //清除内容,时间复杂度为O(n)
setT.size();     //返回容纳的元素数,时间复杂度O(1)
setT.empty();    //检查容器是否为空
setT.find(x);    //查找键值为x的元素,若找到,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置。
setT.begin();    //返回容器中第一个数据的迭代器。
setT.end();      //返回容器中最后一个数据之后的迭代器。
setT.rbegin();   //返回容器中倒数第一个元素的迭代器。
setT.rend();     //返回容器中倒数最后一个元素的后面的迭代器
set<int,less<int> >  setIntA;  //该容器是按升序方式排列元素。
set<int,greater<int>> setIntB;   //该容器是按降序方式排列元素。
//less<int>与greater<int>中的int可以改成其它类型,该类型主要要跟set容纳的数据类型一致

对于结构体,需要重载运算符才能实现set中的排序

struct node     //从小到大排序
{
    int x, y;
    bool operator<(const Node &t) const
    {
        if(x == t.x)
        {
            return y < t.y;
        }
        else return x < t.x;         //从大到小return x>t.x;
    }
};
Last modification:December 12th, 2019 at 11:50 pm
如果觉得我的文章对你有用,请随意赞赏