STL源码剖析-set容器

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877141

SGI STL中的容器set,以RB-Tree作为其底层的实现(rb_tree的大体分析见上文)。在set容器键值key和实值value是相同的,且在容器里面的元素是根据元素的键值自动排序的,同时我们不能修改set容器里面的元素值,所以set的迭代器是采用RB-Tree的const_iterator,不允许用户对其进行修改操作。

首先,给出上面的rb_tree的更详细的定义(主要给出模板Value的声明):

template<typename Key, typename Value, typename Compare>
class rb_tree1{
protected:
    typedef typename __rb_tree_node_base* base_ptr;
    // Value是rb_tree的节点值,Key用于排序
    typedef __rb_tree_node<Value> rb_tree_node;
    // 空间配置器
    typedef allocator<rb_tree_node> rb_tree_node_allocator;
};

下面看下set, map中rb_tree的使用:

在set中对于rb_tree而言key, value都是一样的,内部成员就只有一个rb_tree

template <typename Key, class Compare = std::less<Key>>
class set{
    public:
        typedef Key key_type;
        typedef Key value_type;

        typedef Compare key_compare;

    private:
        // 对于set而言,Key, Value类型是一样的
        typedef rb_tree1<key_type, value_type, key_compare> rep_type;

        // set的成员变量
        rep_type t;
};

在map中对于rb_tree而言key, value不一样,key用于rb_tree排序,pair

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // 用于re_tree排序
    typedef Key    key_type;
    // rb_tree节点的value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // 对于map而言,Key, Value类型不一样,一个排序,另一个节点实值
    typedef rb_tree1<key_type, value_type, key_compare> rep_type;

    // map的成员变量
    rep_type t;
};

首先看构造函数:

set():t(Compare()){}

template<typename InputIterator>
set(InputIterator first, InputIterator last):t(Compare()){
    // 直接调用rb_tree的insert_unique
    t.insert_unique(first, last);
}

其他的操作基本上也是调用rb_tree的函数.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

golang的内存模型与new()与make()

要彻底理解new()与make()的区别, 最好从内存模型入手. golang属于c family, 而c程序在unix的内在模型: |低地址|text|dat...

36350
来自专栏用户2442861的专栏

STL源码剖析-map/multimap容器

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

24520
来自专栏desperate633

深度解析Java多线程的内存模型内部java内存模型硬件层面的内存模型Java内存模型和硬件内存模型的联系小结

Java内存模型很好的说明了JVM是如何在内存里工作的,JVM可以理解为java执行的一个操作系统,作为一个操作系统就有内存模型,这就是我们常说的JAVA内存模...

8010
来自专栏北京马哥教育

只需9个步骤,完美实现自动化运维异常处理!

1异常 异常就是非正常状态,在Python中使用异常对象来表示异常。若程序在编译或运行过程中发生错误,程序的执行过程就会发生改变,抛出异常对象,程序流进入异常处...

32250
来自专栏chenjx85的技术专栏

leetcode-811-Subdomain Visit Count

407110
来自专栏互联网研发闲思录

C++ study

3、数组析构方式为delete []arr;其中arr要指向初始地址,如中间有移动需析构前移动到出始地址。

9700
来自专栏跟着阿笨一起玩NET

数据库模糊搜索时,关键字中有%号,怎么办?

本文转载:http://www.cnblogs.com/lmfeng/archive/2013/02/26/2932963.html

38420
来自专栏JAVA技术站

shell学习三参数传递 原

echo "Shell 传递参数实例" echo "执行的文件名:$0" echo "第一个参数为:$1" echo "第二个参数为:$2" echo ...

5320
来自专栏阮一峰的网络日志

xpath路径表达式笔记

xpath可以用来选择这7种节点。不过,下面的笔记只涉及最常用的第一种element(元素节点),因此可以将下文中的节点和元素视为同义词。

19020
来自专栏农夫安全

【weakfilescan】敏感文件扫描工具

weakfilescan 基于爬虫,动态收集扫描目标相关信息后进行二次整理形成字典规则,利用动态规则的多线程敏感信息泄露检测工具,支持多种个性化定制选项,包括...

48880

扫码关注云+社区

领取腾讯云代金券