(STL)map与set的封装--采用红黑树
目录
前言
STL(标准模板库)中的std::map
和std::set
容器在大多数实现中是基于红黑树来实现的。这些容器提供了对元素进行高效查找、插入和删除操作的能力,其时间复杂度通常为O(log n)。由于红黑树的自平衡特性,这些容器能够保证操作的高效性,即使在最坏的情况下。这使得std::map
和std::set
成为处理有序数据集的常用选择。不过,具体的实现细节可能因不同的编译器和STL版本而异。
map的实现
代码
namespace My_Map
{
template<class K, class V>//map是K/V结构
class map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& p)//T是pair<K, V>
{
return p.first;
}
}
// 对类模板取内嵌类型,加typename告诉编译器这里是类型
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
const_iterator begin() const
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& x)
{
return _t.Insert(x);
}
V& operator[] (const K& k)
{
//1.插入(可能失败)
pair<iterator, bool> ret = insert(make_pair(k, V()));//如果k不存在,则插入一个默认构造,如果k存在,则不插入,返回原来的pair与false
return ret.first->second;//返回值 这里的->second是因为pair<K, V>的第二个元素是V,所以用->second来访问V
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;//这里传入const K而不是K,是为了防止修改pair的第一个元素
};
}
讲解
这段代码定义了一个简单的 map
类,它模仿了 C++ 标准库中的 std::map
,实现了键值对 (key-value) 结构,并基于红黑树 (RBTree) 来存储键值对。下面逐行解析这段代码的关键部分。
命名空间和类定义
namespace My_Map
{
template<class K, class V> // K 是键的类型,V 是值的类型
class map
{
// ...
}
}
map
类被放在 My_Map
命名空间下,支持键类型 K
和值类型 V
的模板实现。
MapKeyOfT 结构体
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& p)
{
return p.first; // 返回 pair 的第一个元素 (键)
}
};
MapKeyOfT
是一个函数对象(functor),用于获取 pair<K, V>
中的键(first
成员)。这是为了在插入键值对到红黑树时能够方便地获取键值。
内嵌类型定义
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator
和const_iterator
是基于RBTree
的迭代器类型,它们允许遍历map
中的元素。pair<const K, V>
的使用是为了确保键是不可修改的,维护了键的唯一性和不可变性。
begin() 和 end() 方法
iterator begin()
{
return _t.begin();
}
const_iterator begin() const
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator end() const
{
return _t.end();
}
- 这些方法返回了红黑树的开始和结束迭代器。
- 有两对
begin()
和end()
方法:一种是非const
的,另一种是const
的。这允许使用map
对象的常量版本进行遍历。
插入方法
pair<iterator, bool> insert(const pair<K, V>& x)
{
return _t.Insert(x); // 调用红黑树的插入方法
}
insert
方法接收一个键值对(pair<K, V>
)并尝试将其插入到红黑树_t
中。- 返回的
pair<iterator, bool>
其中iterator
指向插入的元素(或者已存在的元素),bool
表示是否成功插入新元素。
下标运算符重载
V& operator[] (const K& k)
{
pair<iterator, bool> ret = insert(make_pair(k, V())); // 尝试插入 (k, V())
return ret.first->second; // 返回与键 k 对应的值
}
- 使用下标运算符(
operator[]
)可以通过键k
访问值。 - 如果键
k
不存在,则插入一个默认构造的值V
。如果键存在,则不插入,返回现有的值。
私有成员
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t; // 存储键值对的红黑树
_t
是一个红黑树实例,用于实际存储map
中的键值对。使用pair<const K, V>
作为值类型,以保护键的不可变性。
总结
map就是对红黑树进行了一层封装,使得map的功能通过红黑树得以实现。
这个 map
类通过结合模板、红黑树和合适的迭代器,使得存储和访问键值对变得高效。能进行高效的插入、查找和遍历操作,符合标准库 map
的基本特性。
特别需要注意的是operator[]总是要执行插入操作,只不过key相同时,插入失败。
set的实现
代码
namespace My_RBTreeSet{
template<typename K>//暂时抛弃T的概念,只用K
class set//包装了一层红黑树
{
public:
struct SetKeyOfT
{
const K& operator(const K& key)
{
return key;
}
};
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;//类比vector<int>::const_iterator
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;//告诉编译器,这是个类型,而不是静态成员
iterator begin() const//const成员内部只能调用const成员
{
return _t.begin();//返回红黑树的const版本的begin
}
iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)//插入元素,返回pair<iterator, bool>
{
return _t.Insert(key);//调用红黑树的insert函数,传入key(返回的Node*会隐式转化为iterator对象)
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
讲解
这段代码定义了一个名为 set
的类,它实现了一个简单的集合数据结构,使用红黑树 (RBTree
) 作为底层存储结构。下面是对这段代码的详细讲解。
命名空间和类定义
namespace My_RBTreeSet {
template<typename K> // K 是键的类型,暂时抛弃对值类型 T 的概念
class set // 包装了一层红黑树
{
// ...
};
}
set
类被封装在My_RBTreeSet
命名空间中,使用模板参数K
表示元素的类型。- 注意到这个实现的集合只存储键(不涉及值),这符合集合的基本概念,含有唯一的元素集合。
SetKeyOfT 结构体
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key; //返回传入的键
}
};
SetKeyOfT
是一个函数对象 (functor),其重载的operator()
函数返回给定键的引用。虽然在该上下文中简单地返回键的本身,但它为将来可能加入更复杂的键提取逻辑提供了方便。
类型定义
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator; // 常量迭代器类型
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; // 迭代器类型
const_iterator
和iterator
类型用来从红黑树中访问元素。- 注意这两个
typedef
定义的都是const_iterator
,这里似乎有一处错误,实际上应该是const_iterator
和iterator
两个不同的类型。
方法定义
begin()
和 end()
iterator begin() const // 返回红黑树的开始迭代器
{
return _t.begin(); // 调用红黑树的 const 版本的 begin
}
iterator end() const
{
return _t.end(); // 调用红黑树的 end
}
begin()
方法返回集合的开始迭代器,该迭代器指向集合中第一个元素。end()
方法返回集合的结束迭代器,通常表示集合后一个元素的位置。- 这两个方法都是
const
的版本,意味着你可以在一个常量集合上调用这些方法而不修改集合的状态。
insert()
方法
pair<iterator, bool> insert(const K& key) // 插入元素,返回一个 pair
{
return _t.Insert(key); // 调用红黑树的插入方法
}
insert()
方法接受一个键作为参数并试图将其插入集合。- 返回一个
pair<iterator, bool>
:- 第一个元素是指向插入的元素(或已存在的元素)的迭代器。
- 第二个元素是一个布尔值,表示插入是否成功(如果元素已存在则返回
false
)。
私有成员
private:
RBTree<K, K, SetKeyOfT> _t; // 存储集合元素的红黑树
_t
是一个红黑树实例,用于存储集合的数据。使用K
类型的元素作为键,意味着集合的每个元素都是唯一的。
总结
这个 set
类的实现通过红黑树提供了基本的集合操作。集合的特点如唯一性和无序性得以保证。它提供了插入和迭代功能,采用了 C++ 中常见的数据结构设计模式。在大多数情况下,这种集合结构具有良好的时间复杂度,适合高效地进行元素查找、插入和遍历。
需要特别注意的是所有的迭代器都是const版本,因为k不允许修改。所以迭代器成员函数都用const修饰,进入红黑树调用相应函数时,只能调用红黑树的const成员(const成员只能调用const成员)
原文地址:https://blog.csdn.net/2302_80190394/article/details/142708915
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!