前言
作者：小蜗牛向前冲
名言：我可以接受失败，但我不能接受放弃
如果觉的博主的文章还不错的话，还请点赞，收藏，关注支持博主。如果发现有问题的地方欢迎❀大家在评论区指正
目录
一、键值对
二、set
1、set的基本知识
2、set的使用
三、map
1、map的基本知识
2、map的使用
3、multiset和multimap
4、oj的运用
四、map和set的模拟实现
1、红黑树迭代器
2、set.h模拟实现
3、map.h模拟实现
本期学习目标：理解什么是键值对，实现红黑树的迭代器，模拟实现map和set.
一、键值对
键值对是一种简单但强大的数据表示方式，通常用于构建关联关系。它由两部分组成：键（Key）和值（Value）。每个键都唯一地标识一个值。这种数据结构被广泛用于编程中的各种场景
举例来说，考虑一个电话簿，其中每个人的名字（键）都对应着他们的电话号码（值）。在这个例子中，名字就是键，电话号码就是值。这样的组织方式使得我们可以通过名字快速查找到对应的电话号码。
SGI-STL中关于键值对的定义：
template
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
}
在map和set我们的都有键值对的运用，具体运用场景下面会一一道来，这里我们知要明白键值对有二个按键，都能唯一 标识一个值。
二、set
1、set的基本知识
1. set是按照一定次序存储元素的容器2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对 子集进行直接迭代。5. set在底层是用二叉搜索树(红黑树)实现的。
T: set中存放元素的类型，实际在底层存储的键值对。Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
注意：
set中只放 value，但在底层实际存放的是由构成的键值对。set中插入元素时，只需要插入value即可，不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素，可以得到有序序列。set中的元素默认按照小于来比较set中查找某个元素，时间复杂度为：log_2 n
2、set的使用
set的构造
函数声明功能介绍set (const Compare& comp = Compare(), const Allocator& = Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );用[first, last)区 间中的元素构造 setset ( const set
set的迭代器
set的容量
set修改操作
这些接口和前面的设计都非常类似，这里就不在一一分析了。
下面我们快速使用上面的接口，了解一下set
void test1()
{
set
s.insert(4);
s.insert(67);
s.insert(2);
s.insert(1);
s.insert(55);
s.insert(11);
s.insert(5);
for (auto v : s)
{
cout << v << " " ;
v++;
}
cout << endl;
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
/*auto pos = s.find(55);*/
auto pos = find(s.begin(), s.end(), 55);
if (pos != s.end())
{
s.erase(pos);
}
cout << s.erase(67) << endl;
cout << s.erase(11) << endl;
it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//s.count的功能和find类似
}
三、map
1、map的基本知识
1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的 素。2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair: typedef pair value_type;3. 在内部，map中的元素总是按照键值key进行比较排序的。4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
注意：
1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高O(log_2 N)
6. 支持[]操作符，operator[]中实际进行插入查找
2、map的使用
map的构造
函数声明功能介绍map()构造一个空的map
map的迭代器
函数声明功能介绍begin()和end()begin:首元素的位置，end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同，但cbegin和cend所指向的元素不 能修改rbegin()和rend()反向迭代器，rbegin在end位置，rend在begin位置，其 ++和--操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同，操作相同，但crbegin和crend所 指向的元素不能修改
map的容量与元素访问
函数声明功能介绍bool empty ( ) const检测map中的元素是否为空，是返回 true，否则返回falssize_type size() const返回map中有效元素的个数mapped_type& operator[] (const key_type& k)返回去key对应的value
这里我们要特别的注意：
重载的[]不仅仅能够插入和修改元素还能查找元素。
map中元素的修改
快速上手map
void test1()
{
map
dict.insert(pair
dict.insert(pair
dict.insert(make_pair("字符串", "string"));
dict["迭代器"] = "iterator";
for (auto kv : dict)
{
cout << kv.first << ": " << kv.second << endl;
}
string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map
for (auto& e : arr)
{
auto it = countMap.find(e);
if (it == countMap.end())
{
// 元素不存在，插入它并初始化计数为 1
countMap.insert(make_pair(e, 1));
}
else
{
//元素以及存在递增
it->second++;
}
}
for (const auto& kv : countMap)
{
cout << kv.first << " " << kv.second << endl;
}
}
这里我们用map就完美的实现了kv模型
这里我们特别注意map的插入和以前学习的数据结构不一样，不在是仅仅直接插入数据，这里插入的是一个pair<类型，类型>（"内容1","内容2"）
3、multiset和multimap
这二个容器的用法和前面一样，与set和map的区别是set和map里面的值都是不可重复的，而multiset和multimp里面是可以存放相同的值
4、oj的运用
为了加深对map和set的运用，为大家分享了二道oj题
题1：
代码实现：
class Solution {
public:
struct compare
{
bool operator()(const pair
{
return l.first > r.first;
}
};
vector
map
for (auto& str : words)
{
countMap[str]++;
}
vector
//将map去重后的元素入v
for (auto& kv : countMap)
{
v.push_back(make_pair(kv.second, kv.first));
}
//排序
stable_sort(v.begin(), v.end(), compare());
vector
for (int i = 0; i < k; i++)
{
vv.push_back(v[i].second);
}
return vv;
}
};
题2：
class Solution {
public:
vector
//用set排序+去重
set
set
auto it1 = s1.begin();
auto it2 = s2.begin();
vector
while(it1 != s1.end() && it2 != s2.end())
{
if(*it1 == *it2)
{
v.push_back(*it1);
it1++;
it2++;
}
else if(*it1 < *it2)
{
it1++;
}
else
{
it2++;
}
}
return v;
}
};
四、map和set的模拟实现
上面我们说了map和set的底层实现是红黑树，前面文章也模拟实现了红黑树，但是为了更加契合map和set的功能，我们还需要对红黑树进行改造。
1、红黑树迭代器
红黑树的迭代器基本框架：
template
struct _RBTreeIterator
{
typedef RBTreeNode
typedef _RBTreeIterator
typedef _RBTreeIterator
Node* _node;
};
这里大家可能会有疑惑的是为什么要重命名二个模板类型不一样的_RBTreeIterator，self 是表示迭代器自身的类型，而 iterator 是公开接口的迭代器类型。这样由利用不同编程场景的适应
*(解引用)和->(成员访问运算符)
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
对于 *我们应该返回的是当前节点中的数据，对于->返回的是存放当前节点数据的地址。
operator++()和 operator--()
对于红黑树的++操作，就是指向比当前节点更大的树，但是对于一课红黑树来说是存在二种情况的
如果右子树存在，就找右子树的最小如果右子树不存在，情况1： 如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点。情况2：如果当前节点是其父节点的左子树,那下一个节点就是其父节点，
代码实现：
Self& operator++()
{
//如果右子树存在，就找右子树的最小
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
//找到了右树的最小
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//找到一个节点是其父节点的左孩子，或者到达根节点
//如果当前节点是其父节点的左子树,那下一个节点就是其父节点
//如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
对于红黑树的--操作：情行可以对比++操作的分类完成
Self& operator--()
{
//左子树存在
if (_node->_left)
{
//找左子树中最大
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur在parent的左
while (parent && cur == cur->left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
}
其他细节的完善，逻辑都比较简单，可以参考下面代码自行完成：
//红黑树的迭代器
template
struct _RBTreeIterator
{
typedef RBTreeNode
typedef _RBTreeIterator
typedef _RBTreeIterator
Node* _node;
//构造函数
_RBTreeIterator(Node* node)
:_node(node)
{}
// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器
_RBTreeIterator(const iterator& s)
:_node(s._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
Self& operator++()
{
//如果右子树存在，就找右子树的最小
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
//找到了右树的最小
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//找到一个节点是其父节点的左孩子，或者到达根节点
//如果当前节点是其父节点的左子树,那下一个节点就是其父节点
//如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
//左子树存在
if (_node->_left)
{
//找左子树中最大
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur在parent的左
while (parent && cur == cur->left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
}
bool operator!=(const Self&s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
对于之前写的红黑树，我们还做一些变更比如insert的返回值不是简单判断是否插入成功，而是返回一个键值对，返回是当前插入节点的迭代器，并判断是否插入成功。
红黑树完整实现：
#pragma once
enum Colour
{
RED,
BLACK,
};
template
struct RBTreeNode
{
T _data;
RBTreeNode
RBTreeNode
RBTreeNode
Colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
//红黑树的迭代器
template
struct _RBTreeIterator
{
typedef RBTreeNode
typedef _RBTreeIterator
typedef _RBTreeIterator
Node* _node;
//构造函数
_RBTreeIterator(Node* node)
:_node(node)
{}
// const迭代器的时候，他是构造，支持用普通迭代器构造const迭代器
_RBTreeIterator(const iterator& s)
:_node(s._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
Self& operator++()
{
//如果右子树存在，就找右子树的最小
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
//找到了右树的最小
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//找到一个节点是其父节点的左孩子，或者到达根节点
//如果当前节点是其父节点的左子树,那下一个节点就是其父节点
//如果如果当前节点是其父节点的右子树，或者当前节点是树的根节点，其某个祖先节点
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
//左子树存在
if (_node->_left)
{
//找左子树中最大
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur在parent的左
while (parent && cur == cur->left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
}
bool operator!=(const Self&s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
// map->RBTree
// set->RBTree
template
class RBTree
{
typedef RBTreeNode
public:
typedef _RBTreeIterator
typedef _RBTreeIterator
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
const_iterator begin()const
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator end() const
{
return iterator(nullptr);
}
pair
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root),true);//返回根位置的迭代器，并且插入成功
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur),false);
}
}
cur = new Node(data);
Node* newnode = cur;//保存插入节点位置
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情况一 uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
// 情况二
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情况三
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else // (parent == grandfater->_right)
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
// g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode),true);
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//if (_root == parent)
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
bool Check(Node* root, int blackNum, const int ref)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (blackNum != ref)
{
cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "违反规则：出现连续红色节点" << endl;
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return Check(root->_left, blackNum, ref)
&& Check(root->_right, blackNum, ref);
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root, 0, ref);
}
private:
Node* _root = nullptr;
};
2、set.h模拟实现
#pragma once
#include"RBTree.h"
namespace pjb
{
template
class set
{
struct setKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//在C++中，typename 关键字通常用于表示一个依赖于模板参数的类型。在模板中，
// 有时候编译器无法确定某个名字到底是一个类型还是一个值，这时候就需要使用 typename
// 来明确告诉编译器某个名字是一个类型。
typedef typename RBTree
typedef typename RBTree
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
pair
{
pair
return pair
/*return _t.Insert(key);*/
}
private:
RBTree
};
void test_set()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
set
for (auto e : a)
{
s.insert(e);
}
set
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
}
测试：
3、map.h模拟实现
#pragma once
#include"RBTree.h"
namespace pjb
{
template
class map
{
struct MapKeyOfT
{
const K& operator()(const pair
{
return kv.first;
}
};
public:
typedef typename RBTree
typedef typename RBTree
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
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair
return ret.first->second;
}
private:
RBTree
};
void test_map()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map
for (auto e : a)
{
m.insert(make_pair(e, e));
}
map
while (it != m.end())
{
//it->first++;
it->second++;
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
map
string arr[] = {"西游记","红楼梦","水浒传","三国演义","三国演义" ,"三国演义","水浒传" };
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}
测试:
好文链接
发表评论