C++ 标准容器实现原理-Set

set定义

  • set是关联数据的一种,其中存放的数据是唯一且不重复的
  • set的底层实现是平衡二叉搜索树(也就是红黑树)
  • set的元素是排序的,所以为了保持这种特性,不能够直接修改元素,正常是应该把元素删除然后插入新的元素

set的定义如下:

template < class Key, class Pred = less<Key>, class A = allocator<Key> > class set {...}

set的排序

set是默认排序的,排序函数由构造函数的第二个参数传入,默认情况下是按照从小到大的顺序进行排序,默认排序实现如下:

        // TEMPLATE STRUCT less
        template<class _Ty = void>
    struct less
    {    // functor for operator<
    typedef _Ty first_argument_type;
    typedef _Ty second_argument_type;
    typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {
             // apply operator< to operands
         return (_Left < _Right);
    }
    };

根据上面的默认排序函数可以得出以下两点结论:

  1. 如果set存放的是类的实体,那么该类必须重载了operator <才可以实现排序(string)
  2. 如果set存放的是指针,那么实际上是按照指针值的大小进行排序。

set自定义排序规则

既然有默认的排序,那么我们也可以自定义排序规则,具体主要有以下两种方法:

  • 重载operator <函数
  • 参考上述struct less实现一个自定义的operator()函数

具体可参考:参考文章

set元素的修改

set为了保证其元素按照既定规则排序的有序性,返回的迭代器都是const类型的,因此set里面的元素是完全不能改变的。
至于如果set中存放的是指针,通过迭代器来修改指针指向的内存的值,本质上不是对set元素的修改,在此不做讨论。

文章版权:My-World - 勿于浮沙筑高台

本文链接:http://www.doachieveit.cn/index.php/archives/92.html

版权声明:本文为作者原创,转载请注明文章原始出处 !

添加新评论