在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;
}
目录
相关文章
|
2月前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
77 0
|
2月前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
62 0
|
18天前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
52 18
你对Collection中Set、List、Map理解?
|
11天前
|
存储 缓存 安全
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
49 20
|
28天前
|
存储 C++ 容器
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对,每个键唯一;而`set`存储唯一元素,不包含值。两者均基于红黑树实现,支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口,并简要对比了`map`与`set`的主要差异。此外,还介绍了允许重复元素的`multiset`和`multimap`。
30 3
【C++】map、set基本用法
|
28天前
|
存储 算法 C++
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
22 5
|
2月前
|
Java 开发者
在Java的集合世界里,Set以其独特的特性脱颖而出,它通过“哈希魔法”和“红黑树防御”两大绝技
【10月更文挑战第13天】在Java的集合世界里,Set以其独特的特性脱颖而出。它通过“哈希魔法”和“红黑树防御”两大绝技,有效抵御重复元素的侵扰,确保集合的纯洁性和有序性。无论是“人海战术”还是“偷梁换柱”,Set都能从容应对,成为开发者手中不可或缺的利器。
34 6
|
2月前
|
算法 Java 程序员
Map - TreeSet & TreeMap 源码解析
Map - TreeSet & TreeMap 源码解析
42 0
|
2月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
3月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
48 6
【数据结构】map&set详解