在STL源码当中,如何使用一颗红黑树同时实现map和set的?

简介: 在STL源码当中,如何使用一颗红黑树同时实现map和set的?

在STL源码当中,如何使用一颗红黑树同时实现map和set的?

直接去看stl源码

__rb_tree_node的定义

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;
  Value value_field;
};
template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {
protected:
  typedef void* void_pointer;
  typedef __rb_tree_node_base* base_ptr;
  typedef __rb_tree_node<Value> rb_tree_node;
}

这里是红黑树的定义。

然后看一下stl_map.h文件

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
  typedef Key key_type;
  typedef T data_type;
  typedef T mapped_type;
  typedef pair<const Key, T> value_type;
  typedef Compare key_compare;
  class value_compare : public binary_function<value_type, value_type, bool> 
  {
  friend class map<Key, T, Compare, Alloc>;
  protected :
    Compare comp;
    value_compare(Compare c) : comp(c) {}
  public:
    bool operator()(const value_type& x, const value_type& y) const
    {
      return comp(x.first, y.first);
    }
  };

然后再看stl_set.h文件

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
  // typedefs:
  typedef Key key_type;
  typedef Key value_type;
  typedef Compare key_compare;
  typedef Compare value_compare;
private:
  typedef rb_tree<key_type, value_type, 
                  identity<value_type>, key_compare, Alloc> rep_type;//红黑树重命名为rep_type
  rep_type t;  // red-black tree representing set
}

可以看到在红黑树当中,是用第二个模板参数来确定到底是map还是set的

template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {
protected:
  typedef __rb_tree_node<Value> rb_tree_node;
}
目录
相关文章
|
1月前
|
存储 JavaScript Java
(Python基础)新时代语言!一起学习Python吧!(四):dict字典和set类型;切片类型、列表生成式;map和reduce迭代器;filter过滤函数、sorted排序函数;lambda函数
dict字典 Python内置了字典:dict的支持,dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
156 1
|
4月前
|
存储 缓存 JavaScript
Set和Map有什么区别?
Set和Map有什么区别?
378 1
|
1月前
|
存储 算法 容器
set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
`set`基于红黑树实现,支持有序存储、自动去重,增删查效率为O(logN)。通过仿函数可自定义排序规则,配合空间配置器灵活管理内存。不支持修改元素值,迭代器失效需注意。`multiset`允许重复元素。常用于去重、排序及查找场景。
|
5月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些?
for...of循环在遍历Set和Map时的注意事项有哪些?
313 121
|
5月前
|
安全 Java 数据库连接
让我们讲解一下 Map 集合遍历的方式
我是小假 期待与你的下一次相遇 ~
223 43
使用 entrySet 遍历 Map 类集合 KV
使用 entrySet 遍历 Map 类集合 KV
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
Go 定位技术 索引
Go 语言Map(集合) | 19
Go 语言Map(集合) | 19
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set