C++第三十八弹---一万六千字使用红黑树封装set和map

小林熬夜学编程 2024-08-28 17:05:07 阅读 65

 ✨个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】

目录

1、set/map基本结构

2、红黑树基本结构改造

 3、红黑树的迭代器

4、set的模拟实现

5、map的模拟实现

6、完整代码


1、set/map基本结构

在封装set/map之前,我们先看看stl源码大致是如何实现的。

set基本结构

map基本结构

 

从上面两张图我们可以看到,set和map的底层都是红黑树,红黑树的模板参数有5个,我们先知道前面两个即可,第一个key_type指的是key值,value_type指的是"value"值,我们知道set只有key值,而map有key和value,那这里是怎么通过一个模板参数实现两个容器的呢?

        答案是set传参时,第一个和第二个传的都是key值;map传参时,第一个传key值,第二个传pair<K,V>键值对。

为什么有了pair<K,V>键值对还需要key值呢?

因为查找的时候需要通过key值查找。

2、红黑树基本结构改造

红黑树结点结构

只需对有效数据进行修改,改为T类型的模板,根据需要实例化红黑树。

<code>enum Colour

{

RED,

BLACK

};

template<class T>

struct RBTreeNode

{

RBTreeNode<T>* _left;

RBTreeNode<T>* _right;

RBTreeNode<T>* _parent;

T _data;// set传key值,map传pair键值对

Colour _col;

RBTreeNode(const T& data)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_data(data)

,_col(RED)

{}

};

红黑树结构 

红黑树的基本结构只需对插入进行修改增加拷贝构造赋值操作符重载析构函数即可。

插入函数

插入时直接插入T类型的data值,但是在查找插入的位置时,有两种情况,如果插入的值是key值时,可以直接通过data比较大小,但是插入pair<K,V>值时,需要通过该值的first成员比较大小,那么如何能够让两者统一呢?

        此处的解决办法是使用仿函数,获取key值。

set仿函数

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;// 直接返回key值

}

};

map仿函数

struct MapKeyOfT

{

const K& operator()(const pair<K,V>& kv)

{

return kv.first;// 返回first成员

}

};

插入函数 

只需在比较时进行修改,使用仿函数,返回值为键值对,第一个成员为插入位置的迭代器,第二个成员为bool值,插入成功返回true,失败返回false。

pair<Iterator,bool> Insert(const T& data)

{

if (_root == nullptr)

{

_root = new Node(data);

_root->_col = BLACK;

// 插入新结点,返回插入位置迭代器+true

return make_pair(Iterator(_root),true);

}

KeyOfT kot;// 仿函数对象,获取key值

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

// kot对象取T类型中data对象的key

if (kot(cur->_data) < kot(data))

{

parent = cur;

cur = cur->_right;

}

else if (kot(cur->_data) > kot(data))

{

parent = cur;

cur = cur->_left;

}

// 二叉搜索树默认不能冗余,因此相等则返回false

else

{

// 冗余返回当前结点迭代器+false

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;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

// 叔叔存在且为红

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续向上处理

cur = grandfather;

parent = cur->_parent;

}

// 叔叔不存在或叔叔为黑

else

{

if (cur == parent->_left)

{

// g

// p u

//c

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

Node* uncle = grandfather->_left;

// 叔叔存在且为红,-》变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else // 叔叔不存在,或者存在且为黑

{

// 情况二:叔叔不存在或者存在且为黑

// 旋转+变色

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

//g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK;

// 返回插入节点位置迭代器+true

return make_pair(Iterator(newnode), true);

}

拷贝构造

拷贝构造需要拷贝原结点的有效数据结构的链接关系结点的颜色。此处还有一个问题,如果自己实现了构造函数,编译器就不会自动生成默认构造,当使用无参构造红黑树时会报错,因此此处需要实现默认构造。

拷贝函数

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

// 新创建结点,使用前序链接结点

Node* newroot = new Node(root->_data);

newroot->_col = root->_col;// 更新颜色

newroot->_left = Copy(root->_left);

// 左孩子不为空需要链接双亲结点

if (newroot->_left)

newroot->_left->_parent = newroot;

newroot->_right = Copy(root->_right);

// 右孩子不为空需要链接双亲结点

if (newroot->_right)

newroot->_right->_parent = newroot;

return newroot;

}

拷贝构造函数 

// 强制生成默认构造

RBTree() = default;

// 拷贝构造 解决深拷贝问题,写了拷贝构造则不自动生成默认构造

RBTree(const RBTree<K, T, KeyOfT>& t)

{

_root = Copy(t._root);

}

赋值操作符重载 

赋值操作符重载的实现与stl容器类似,可以直接使用现代写法,交换地址即可,但是形参不能加const。

RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)

{

swap(_root, t._root);// 使用现代写法,交换地址即可

return *this;

}

析构函数

析构函数将动态开辟的空间手动释放即可。

释放空间函数

void Destroy(Node* root)

{

if (root == nullptr)

return;

// 使用后序释放空间

Destroy(root->_left);

Destroy(root->_right);

delete root;

root = nullptr;// 手动置空

}

析构函数 

~RBTree()

{

Destroy(_root);

_root = nullptr;// 手动将_root置空

}

 3、红黑树的迭代器

迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器,需要考虑以前问题:

begin()与end()

STL明确规定,begin()与end()代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,可以得到一个有序的序列,因此:begin()可以放在红黑树中最小节点(即最左侧节点)的位置end()放在最大节点(最右侧节点)的下一个位置,关键是最大节点的下一个位置在哪块?能否给成nullptr呢?此处为了简单实现红黑树,我们将end()给nullptr

迭代器结点类

解引用,箭头,不等于这些函数重载与链表的迭代器实现类似,因此此处不做详细讲解,单独对前置++详细讲解,uu们可以自己分析实现后置++和--函数。

前置++的实现有两种情况:

1、当前结点的右子树不为空,下一个访问的结点为右子树的最左结点2、当前结点的右子树为空,下一个访问的结点为孩子是父亲的左祖先

右子树不为空

右子树为空 

前置++ 

<code>Self& operator++()

{

// 右子树不为空 访问右子树的最左结点

if (_node->_right)

{

Node* leftMin = _node->_right;

while (leftMin->_left)

{

leftMin = leftMin->_left;

}

_node = leftMin;

}

// 右子树为空,找孩子是父亲的左祖先

else

{

Node* cur = _node;

Node* parent = cur->_parent;

// 当前结点是最右结点时,parent为空

while (parent && cur != parent->_left)

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

迭代器完整代码 

template<class T,class Ref,class Ptr>

struct __RBTreeIterator

{

typedef RBTreeNode<T> Node;

Node* _node;

typedef __RBTreeIterator<T, Ref, Ptr> Self;

__RBTreeIterator(Node* node)

:_node(node)

{}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& s)

{

return _node != s._node;

}

Self& operator++();

};

begin()和end()函数的获取

begin()在红黑树中最小节点(即最左侧节点)的位置。end()放在最大节点(最右侧节点)的下一个位置,此处给为nullptr。

实现上面的函数之前需要在红黑树类中typedef该迭代器。

typedef __RBTreeIterator<T, T&, T*> Iterator;// 普通迭代器

typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;// const迭代器

begin()函数的获取

begin()在红黑树中最小节点(即最左侧节点)的位置。

// 普通迭代器

Iterator Begin()

{

Node* leftMin = _root;

// leftMin可能为空

while (leftMin && leftMin->_left)

{

leftMin = leftMin->_left;

}

// 返回最左侧结点

return Iterator(leftMin);

}

// const迭代器

ConstIterator Begin() const

{

Node* leftMin = _root;

// leftMin可能为空

while (leftMin && leftMin->_left)

{

leftMin = leftMin->_left;

}

return ConstIterator(leftMin);

}

end()函数的获取

end()放在最大节点(最右侧节点)的下一个位置,此处给为nullptr。

// 结尾为空,开始为空时则不进入不等于的循环

Iterator End()

{

return Iterator(nullptr);

}

ConstIterator End() const

{

return ConstIterator(nullptr);

}

4、set的模拟实现

template<class K>

class set

{

// set获取key值仿函数,传入红黑树第三个模板参数

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

// Iterator不知道是静态成员变量还是类型,使用typename

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

const_iterator begin() const

{

return _t.Begin();

}

const_iterator end() const

{

return _t.End();

}

iterator begin()

{

return _t.Begin();

}

iterator end()

{

return _t.End();

}

pair<iterator, bool> insert(const K& key)

{

return _t.Insert(key);

}

iterator find(const K& key)

{

return _t.Find(key);

}

private:

// 加const 时key不能修改

RBTree<K, const K, SetKeyOfT> _t;

};

set测试代码

void PrintSet(const set<int>& s)

{

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

}

void test_set()

{

set<int> s;

s.insert(4);

s.insert(2);

s.insert(5);

s.insert(15);

s.insert(7);

s.insert(1);

set<int>::iterator it = s.begin();

while (it != s.end())

{

//*it += 5;// 不能修改

cout << *it << " ";

++it;

}

cout << endl;

PrintSet(s);

// 浅拷贝问题

set<int> copy(s);// 拷贝构造

PrintSet(copy);

copy = s;// 赋值操作符重载

PrintSet(copy);

}

5、map的模拟实现

template<class K,class V>

class map

{

struct MapKeyOfT

{

const K& operator()(const pair<K,V>& kv)

{

return kv.first;

}

};

public:

// Iterator不知道是静态成员变量还是类型,使用typename

typedef typename RBTree<K, pair<const K,V>, MapKeyOfT>::Iterator iterator;

typedef typename RBTree<K, pair<const K,const V>, MapKeyOfT>::ConstIterator const_iterator;

const_iterator begin() const

{

return _t.Begin();

}

const_iterator end() const

{

return _t.End();

}

iterator begin()

{

return _t.Begin();

}

iterator end()

{

return _t.End();

}

pair<iterator, bool> insert(const pair<K,V>& kv)

{

return _t.Insert(kv);

}

iterator find(const K& key)

{

return _t.Find(key);

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));

return ret.first->second;

}

private:

// pair加const,key不能修改

RBTree<K, pair<const K, V>, MapKeyOfT> _t;

};

map测试代码

void test_map1()

{

map<string,int> m;

m.insert({ "苹果",1 });

m.insert({ "草莓",3 });

m.insert({ "香蕉",2 });

m.insert({ "苹果",4 });

map<string, int>::iterator it = m.begin();

while (it != m.end())

{

//it->first += 'x';

it->second += 'y';

//cout << it.operator->()->first << ":" << it->second << endl;

cout << it->first << ":" << it->second << endl;

++it;

}

cout << endl;

// const迭代器初始化时需要给模板参数加const

const map<string, const int> m1;

map<string, const int>::const_iterator it1 = m1.begin();

while (it1 != m1.end())

{

//it1->second += 'y';

cout << it1->first << ":" << it1->second << endl;

++it1;

}

cout << endl;

}

void test_map2()

{

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",

"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };

// 使用map计算水果的个数

map<string, int> countMap;

for (auto& str : arr)

{

// 水果存在则value值++,不存在则新增该水果并将value值++

countMap[str]++;

}

// 按照key值排序

for (auto& kv : countMap)

{

cout << kv.first << ":" << kv.second << endl;

}

cout << endl;

}

6、完整代码

RBTree.h

#pragma once

#include<vector>

enum Colour

{

RED,

BLACK

};

template<class T>

struct RBTreeNode

{

RBTreeNode<T>* _left;

RBTreeNode<T>* _right;

RBTreeNode<T>* _parent;

T _data;

Colour _col;

RBTreeNode(const T& data)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_data(data)

,_col(RED)

{}

};

template<class T,class Ref,class Ptr>

struct __RBTreeIterator

{

typedef RBTreeNode<T> Node;

Node* _node;

typedef __RBTreeIterator<T, Ref, Ptr> Self;

__RBTreeIterator(Node* node)

:_node(node)

{}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& s)

{

return _node != s._node;

}

Self& operator++()

{

// 右子树不为空 访问右子树的最左结点

if (_node->_right)

{

Node* leftMin = _node->_right;

while (leftMin->_left)

{

leftMin = leftMin->_left;

}

_node = leftMin;

}

// 右子树为空,找孩子是父亲的左祖先

else

{

Node* cur = _node;

Node* parent = cur->_parent;

// 当前结点是最右结点时,parent为空

while (parent && cur != parent->_left)

{

cur = parent;

parent = parent->_parent;

}

_node = parent;

}

return *this;

}

};

template<class K,class T,class KeyOfT>

class RBTree

{

typedef RBTreeNode<T> Node;

public:

typedef __RBTreeIterator<T, T&, T*> Iterator;

typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;

ConstIterator Begin() const

{

Node* leftMin = _root;

// leftMin可能为空

while (leftMin && leftMin->_left)

{

leftMin = leftMin->_left;

}

return ConstIterator(leftMin);

}

ConstIterator End() const

{

return ConstIterator(nullptr);

}

Iterator Begin()

{

Node* leftMin = _root;

// leftMin可能为空

while (leftMin && leftMin->_left)

{

leftMin = leftMin->_left;

}

return Iterator(leftMin);

}

// 结尾为空,开始为空时则不进入不等于的循环

Iterator End()

{

return Iterator(nullptr);

}

// 强制生成默认构造

RBTree() = default;

// 拷贝构造 解决深拷贝问题,写了拷贝构造则不自动生成默认构造

RBTree(const RBTree<K, T, KeyOfT>& t)

{

_root = Copy(t._root);

}

RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)

{

swap(_root, t._root);

return *this;

}

~RBTree()

{

Destroy(_root);

_root = nullptr;

}

Iterator Find(const K& key)

{

Node* cur = _root;

while (cur)

{

if (cur->_key < key)

{

cur = cur->_right;

}

else if (cur->_key > key)

{

cur = cur->_left;

}

else

{

// 找到返回当前结点迭代器

return Iterator(cur);

}

}

// 没找到返回End()

return End();

}

pair<Iterator,bool> Insert(const T& data)

{

if (_root == nullptr)

{

_root = new Node(data);

// 根节点为黑色

_root->_col = BLACK;

// 插入新结点,返回插入位置迭代器+true

return make_pair(Iterator(_root),true);

}

KeyOfT kot;

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

// 插入值更大则插入到右边

// kot对象取T类型中Data对象的key

if (kot(cur->_data) < kot(data))

{

parent = cur;

cur = cur->_right;

}

// 小则在左边

else if (kot(cur->_data) > kot(data))

{

parent = cur;

cur = cur->_left;

}

// 二叉搜索树默认不能冗余,因此相等则返回false

else

{

// 冗余返回当前结点迭代器+false

return make_pair(Iterator(cur),false);

}

}

// 为空则找到插入位置 需要先找到父亲的位置

// key值大于父亲的值则在右侧

cur = new Node(data);

Node* newnode = cur;//存新插入节点的地址

// 新增结点为红色

cur->_col = RED;

if (kot(parent->_data) < kot(data))

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

// 父亲为红色节点则需要调整颜色

while (parent && parent->_col == RED)

{

Node* grandfather = parent->_parent;

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

// 叔叔存在且为红

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续向上处理

cur = grandfather;

parent = cur->_parent;

}

// 叔叔不存在或叔叔为黑

else

{

if (cur == parent->_left)

{

// g

// p u

//c

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

Node* uncle = grandfather->_left;

// 叔叔存在且为红,-》变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

// 继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else // 叔叔不存在,或者存在且为黑

{

// 情况二:叔叔不存在或者存在且为黑

// 旋转+变色

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

//g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

_root->_col = BLACK;

// 返回插入节点位置迭代器+true

return make_pair(Iterator(newnode), true);

}

// 右单旋 左边较高

void RotateR(Node* parent)

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

// 更新parent

parent->_left = subLR;

// subLR不为空则更新父亲

if (subLR)

subLR->_parent = parent;

subL->_right = parent;//xxx

// 提前存parent的父亲

Node* ppNode = parent->_parent;

parent->_parent = subL;

// parent为根节点

if (parent == _root)

{

_root = subL;

_root->_parent = nullptr;

}

else

{

// parent为ppNode的左结点

if (parent == ppNode->_left)

{

ppNode->_left = subL;

}

else

{

ppNode->_right = subL;

}

subL->_parent = ppNode;

}

}

// 左单旋 右边较高

void RotateL(Node* parent)

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

// 更新parent

parent->_right = subRL;

// subRL不为空

if (subRL)

subRL->_parent = parent;

subR->_left = parent;

// 提前存parent的父结点

Node* ppNode = parent->_parent;

parent->_parent = subR;

// parent为根节点

if (parent == _root)

{

_root = subR;

_root->_parent = nullptr;

}

else

{

// 左

if (parent == ppNode->_right)

{

ppNode->_right = subR;

}

else

{

ppNode->_left = subR;

}

subR->_parent = ppNode;

}

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

bool IsBalance()

{

// 1、判断根节点是否为黑

if (_root->_col == RED)

{

return false;

}

int refNum = 0;// 最左路径的黑色结点个数,参考数量

Node* cur = _root;

while (cur)

{

if (cur->_col == BLACK)

{

refNum++;

}

cur = cur->_left;

}

return Check(_root,0,refNum);

}

private:

void Destroy(Node* root)

{

if (root == nullptr)

return;

Destroy(root->_left);

Destroy(root->_right);

delete root;

root = nullptr;

}

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

// 新创建结点

Node* newroot = new Node(root->_data);

newroot->_col = root->_col;// 更新颜色

newroot->_left = Copy(root->_left);

if (newroot->_left)

newroot->_left->_parent = newroot;

newroot->_right = Copy(root->_right);

if (newroot->_right)

newroot->_right->_parent = newroot;

return newroot;

}

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 refNum)

{

if (root == nullptr)

{

// 2、判断是否存在相同数量的黑色节点路径

if (blackNum != refNum)

{

cout << "存在黑色结点数量不相等的路径" << endl;

return false;

}

return true;

}

if (root->_col == RED && root->_parent->_col == RED)

{

// 3、判断是否存在连续的红色结点

cout << root->_kv.first << "存在连续的红色结点" << endl;

return false;

}

if (root->_col == BLACK)

blackNum++;

return Check(root->_left,blackNum,refNum)

&& Check(root->_right, blackNum, refNum);

}

private:

Node* _root = nullptr;

//size_t _size = 0;

};

Myset.h

#pragma once

#include "RBTree.h"

namespace lin

{

template<class K>

class set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

// Iterator不知道是静态成员变量还是类型,使用typename

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

const_iterator begin() const

{

return _t.Begin();

}

const_iterator end() const

{

return _t.End();

}

iterator begin()

{

return _t.Begin();

}

iterator end()

{

return _t.End();

}

pair<iterator, bool> insert(const K& key)

{

return _t.Insert(key);

}

iterator find(const K& key)

{

return _t.Find(key);

}

private:

// 加const 时key不能修改

RBTree<K, const K, SetKeyOfT> _t;

};

void PrintSet(const set<int>& s)

{

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

}

void test_set()

{

set<int> s;

s.insert(4);

s.insert(2);

s.insert(5);

s.insert(15);

s.insert(7);

s.insert(1);

s.insert(5);

s.insert(7);

set<int>::iterator it = s.begin();

while (it != s.end())

{

//*it += 5;

cout << *it << " ";

++it;

}

cout << endl;

//for (auto e : s)

//{

//cout << e << endl;

//}

PrintSet(s);

// 浅拷贝问题

set<int> copy(s);

PrintSet(copy);

copy = s;

PrintSet(copy);

}

}

Mymap.h

#pragma once

#include "RBTree.h"

namespace lin

{

template<class K,class V>

class map

{

struct MapKeyOfT

{

const K& operator()(const pair<K,V>& kv)

{

return kv.first;

}

};

public:

// Iterator不知道是静态成员变量还是类型,使用typename

typedef typename RBTree<K, pair<const K,V>, MapKeyOfT>::Iterator iterator;

typedef typename RBTree<K, pair<const K,const V>, MapKeyOfT>::ConstIterator const_iterator;

const_iterator begin() const

{

return _t.Begin();

}

const_iterator end() const

{

return _t.End();

}

iterator begin()

{

return _t.Begin();

}

iterator end()

{

return _t.End();

}

pair<iterator, bool> insert(const pair<K,V>& kv)

{

return _t.Insert(kv);

}

iterator find(const K& key)

{

return _t.Find(key);

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));

return ret.first->second;

}

private:

// pair加const,key不能修改

RBTree<K, pair<const K, V>, MapKeyOfT> _t;

};

void test_map1()

{

map<string,int> m;

m.insert({ "苹果",1 });

m.insert({ "草莓",3 });

m.insert({ "香蕉",2 });

m.insert({ "苹果",4 });

map<string, int>::iterator it = m.begin();

while (it != m.end())

{

//it->first += 'x';

it->second += 'y';

//cout << it.operator->()->first << ":" << it->second << endl;

cout << it->first << ":" << it->second << endl;

++it;

}

cout << endl;

// const迭代器初始哈时需要给模板参数加const

const map<string, const int> m1;

map<string, const int>::const_iterator it1 = m1.begin();

while (it1 != m1.end())

{

//it1->second += 'y';

cout << it1->first << ":" << it1->second << endl;

++it1;

}

cout << endl;

}

void test_map2()

{

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",

"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };

// 使用map计算水果的个数

map<string, int> countMap;

for (auto& str : arr)

{

// 水果存在则value值++,不存在则新增该水果并将value值++

countMap[str]++;

}

// 按照key值排序

for (auto& kv : countMap)

{

cout << kv.first << ":" << kv.second << endl;

}

cout << endl;

}

}

Test.cpp 

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

#include "RBTree.h"

#include "Myset.h"

#include "Mymap.h"

int main()

{

//lin::test_set();

lin::test_map2();

return 0;

}



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。