cpp浅析STL-set

前言

CPP

集合(Set)t是一种元素唯一的、包含已排序对象的数据容器。

C++ STL中标准关联容器set， multiset， map， multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

对于map和set这种关联容器来说，不需要做内存拷贝和内存移动。以节点的方式来存储，其节点结构和链表差不多。

博主当前的CPP版本为c++14，所以相关源码内容就是以这个版本的为准。

Set定义

#include<set>
using namespace std;
 
set<int> s1;//空对象
set<int> s2{3, 4, 2, 1};//列表清单,默认less递增 ,输出为{1,2,3,4}
set<int, greater<int> > s3{6, 5, 7, 8};//列表清单 ,输出为{8.7.6.5}

Set常规操作

支持正向和反向迭代器，但是不支持随机迭代器访问元素。

C++中文在线手册：https://zh.cppreference.com/

增加元素

insert插入

允许多个元素的插入，使用迭代器指定位置。

/*
 * insert能插入多个，慢但是实用
 * */
void add1() {
    set<int> demo{1, 2};
    //在第一个元素后面插入3
    demo.insert(demo.begin()++, 3);//{1,2,3},结果遵循递增规则
 
    //直接插入元素,也是按照规则排列
    demo.insert(-1);//{-1,1,2,3}
    //C++11之后,可以用emplace_hint或者emplace替代
 
    //插入其他容器的部分序列
    vector<int> test{7, 8, 9};
    demo.insert(++test.begin(), --test.end()); //{-1,1,2,3,8}
 
    //插入初始化列表
    demo.insert({10, 11}); //{-1,1,2,3,8,10,11}
 
    set<int> s = demo;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}

emplace插入

注意是每次只能插入一个，而且是只有构造函数，效率高！

/*
 * emplace，只能插入一个
 * 而且如果元素已经存在，是不会再次插入的
 * */
void add2() {
    set<int> demo{1, 2};
 
    demo.emplace(4);//{1,2,4}
 
    demo.emplace(4);//还是{1,2,4}
 
    set<int> s = demo;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}

遍历元素

/*
 * 直接用迭代器，注意const_iterator还是iterator
 * */
void search() {
    set<int> demo{1, 2};
 
    // 如果参数为const vector<int> 需要用const_iterator
    // vector<int>::const_iterator iter=v.begin();
 
    set<int> s = demo;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}

删除元素

/*
 * 删除有两种方式，
 * clear是直接清空
 * erase是删除指定迭代器范围内的数字
 * 也可以用来删除指定的单个元素
 * */
void del() {
    set<int> demo{1, 2, 3, 4, 5};
    //清空
    demo.clear();//{}
    if (demo.empty()) {//判断Vector为空则返回true
        demo.insert({6, 7, 8, 9, 10, 11});//{ 6, 7, 8, 9, 10, 11 }
 
        //删除第一个元素
        demo.erase(demo.begin());//{7, 8, 9, 10, 11 }
        // 删除指定元素
        demo.erase(11);
        //删除前三个
        demo.erase(demo.begin(), next(demo.begin(), 3)); //{ 10, 11 }
        // 只保留最后一个
        demo.erase(demo.begin(), ++demo.end()); //{11}
    }
 
    set<int> s = demo;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}

比较函数

元素为基本类型

使用函数对象

当元素是基本类型，一般是变动规则为递增或者递减。

推荐使用自带的less或者greater函数比较。

// 基础类型，变动规则为递增或者递减
void BasicCompare() {
    set<int, less<int> > s2{6, 5, 7, 8};//小数靠前。递增,输出为{5,6,7,8}
    set<int, greater<int> > s3{6, 5, 7, 8};//大数靠前。递减,输出为{8,7,6,5}
 
    // 遍历查看内容
    set<int> s = s2;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}

类外重载括号

当元素是基本类型，变动规则后不能用自带的less或者greater函数比较，就只能新建一个结构体来描述规则。这种方式是适用性最广的。

// 基础类型，但是有特殊的比较规则
// 此处以递增递减为例
// 当然也可以指定为其他自定义类型
struct Special {
    bool operator()(const int &a, const int &b) {
        // return a > b;//等价greater<int>
        return a < b;//等价less<int>
    }
};
 
// 基础类型需要类外重载
void SpecialCompare() {
    set<int, Special> s2;
 
    s2.emplace(3);
    s2.emplace(2);
    s2.emplace(1);
    s2.emplace(4);
 
    // 遍历查看内容
    set<int, Special> s = s2;
    set<int>::iterator iter;
    for (iter = s.begin(); iter != s.end(); ++iter) {
        cout << *iter << " ";
    }
}
/*1 2 3 4 */

元素为自定义类型

当元素是自定义结构体，可以在类外重载括号()；也可以在类内重载小于号<，例子如下。

类内重载小于号

// 自定义结构体
struct Info {
    string name;
    float score;
 
    Info() {
        name = "a";
        score = 60;
    }
 
    Info(string sname, float fscore) {
        name = sname;
        score = fscore;
    }
 
    // 类内重载方法
    bool operator<(const Info &a) const {
        /*名字递减；若名字相同，则分数递减*/
        if (a.name < name)
            return true;
        else if (a.name == name) {
            return a.score < score;
        } else
            return false;
    }
};
 
void InfoCompare() {
    pair<set<Info>::iterator, bool> result;//获取插入的结果
    set<Info> s;
    // 插入默认对象和指定对象
    s.insert(Info());
    s.insert(Info("a", 53));
    s.insert(Info("keen", 68));
    result = s.insert(Info("keen", 60));
 
    // 遍历查看内容
    for (auto iter = s.begin(); iter != s.end(); ++iter) {
        cout << iter->name << " " << iter->score << endl;
    }
    cout << "插入元素的信息：" << result.first->name << " " << result.first->score << endl;
    cout << "插入是否成功" << boolalpha << result.second << endl;
 
    // 再次插入相同元素
    result = s.insert(Info("keen", 60));
    cout << "插入元素的信息：" << result.first->name << " " << result.first->score << endl;
    cout << "插入是否成功" << boolalpha << result.second << endl;
}
    /*
    keen 68
    keen 60
    a 60
    a 53
    插入元素的信息：keen 60
    插入是否成功true
    插入元素的信息：keen 60
    插入是否成功false
     */

类外重载括号

#include <iostream>
#include <set>
 
using namespace std;
 
/*Student结构体*/
struct Student {
    string name;
    int age;
    string sex;
 
    Student() {}
 
    Student(const string &name, int age, const string &sex) : name(name), age(age), sex(sex) {}
};
 
/*
 * 为Student指定排序准则
 * 先比较名字；若名字相同,则比较年龄。小的返回true
 * 如果想要部分参数匹配，可以用正则表达式来规定
 * */
class StudentCompare {
public:
    bool operator()(const Student &a, const Student &b) const {
        if (a.name < b.name)
            return true;
        else if (a.name == b.name) {
            if (a.age < b.age)
                return true;
            else
                return false;
        } else
            return false;
    }
};
 
int main() {
    set<Student, StudentCompare> stuSet;
 
    stuSet.insert(Student("张三", 13, "male"));
    stuSet.insert(Student("李四", 23, "female"));
 
    /*构造一个用来查找的临时对象,可以看到,即使stuTemp与stu1实际上并不是同一个对象,
     *但当在set中查找时,仍能够查找到集合中的元素成功。
     *这是因为已定义的StudentCompare的缘故。
     */
    Student stuTemp;
    stuTemp.name = "张三";
    stuTemp.age = 13;
 
    set<Student, StudentCompare>::iterator iter;
    iter = stuSet.find(stuTemp);
    if (iter != stuSet.end()) {
        cout << (*iter).name << " " << (*iter).age << " " << (*iter).sex << endl;
    } else {
        cout << "Cannot fine the student!" << endl;
    }
    return 0;
}

查找函数

count统计元素个数

count函数是用来统计一个元素在当前容器内的个数。由于Set的特性，所以只能返回1或者0。

/*
 * 用count函数寻找元素，
 * */
void find1(set<int> s ){
    if (s.count(4) == 1) {
        cout << "元素4存在"<<endl;
    }
    if (s.count(8) == 0) {
        cout << "元素8不存在";
    }
}

追查源码，我发现他是用的红黑树的__count_unique方法，从根节点开始比对，如果要查找的元素是比当前节点的数值要小就去左子树找，如果要查找的元素是比当前节点的数值要大就去右子树找，当匹配到节点值相等时，就返回1；当到最后的叶子结点仍然没有找到就返回0。

底层是使用的红黑树，所以查找起来还是很方便的。

源码如下。

size_type __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const
{
    __node_pointer __rt = __root();
    while (__rt != nullptr)
    {
        if (value_comp()(__k, __rt->__value_))
        {
            __rt = static_cast<__node_pointer>(__rt->__left_);
        }
        else if (value_comp()(__rt->__value_, __k))
            __rt = static_cast<__node_pointer>(__rt->__right_);
        else
            return 1;
    }
    return 0;
}

find获取元素迭代器

/*
 * 用find函数寻找元素，
 * */
void find2(set<int> s ){
 
    if (s.find(4)!= s.end() ) {
        cout << "元素4存在"<<endl;
    }else{
        cout << "元素4不存在";
    }
    if (s.find(8)!= s.end() ) {
        cout << "元素8存在"<<endl;
    }else{
        cout << "元素8不存在";
    }
}

追查源码，我发现他是用的红黑树的find方法，从根节点开始比对，如果要查找的元素是比当前节点的数值要大就去右子树找；如果查找的元素比当前节点的数值要小于等于匹配到节点值时，就赋值一次结果节点并去左子树找。一直到最后所查找的节点为空再结束。最终返回结果节点。

源码如下。

iterator __lower_bound(const _Key& __v,__node_pointer __root,__iter_pointer __result)
{
    while (__root != nullptr)
    {
        if (!value_comp()(__root->__value_, __v))
        {
            __result = static_cast<__iter_pointer>(__root);
            __root = static_cast<__node_pointer>(__root->__left_);
        }
        else
            __root = static_cast<__node_pointer>(__root->__right_);
    }
    return iterator(__result);
}

暂时看来，两个方法的底层实现逻辑是相似的，都是用平衡二叉树的方式去寻找节点。

区别是count返回1或0来标明元素是否存在；find函数是返回指针可以方便下一步修改或者取用。

感谢

谨以此文，送给未来笨兮兮又回来看的博主自己

哦，我看到了，过去那个很努力但是很皮的我哦

感谢现在努力的自己。

感谢现在的好奇，为了能成为更好的自己。

离线下载链接

C++中set用法详解

C++ STL set::find的用法

C++ STL set容器完全攻略