C++——关联式容器（4）：set和map

        在接触了诸如二叉搜索树、AVL树、红黑树的树形结构之后，我们对树的结构有了大致的了解，现在引入真正的关联式容器。

        首先，先明确了关联式容器的概念。我们之前所接触到的如vector、list等容器，我们知道他们实际上都是线性的数据结构，因此也称之为序列式容器。而关联式容器也是存储数据用，只是其特别的<key,value>键值对的元素结构使得在数据检索方面的效率得到了很大的提升。

        STL中提供的关联式容器可以分为两类：树形结构和哈希结构。哈希结构我们会在后文再叙述。树形结构中关联式容器主要有：set、map、multiset、multimap四种，其底层都是红黑树。

4. set与multiset的用法

4.1 set的特征

        set实际上就是我们之前介绍的K模型，下面给出一些set特征的汇总：

①容器中存储的元素只有一个值，这个值既是其value又是标识它的key，不允许重复元素；

②set的元素只允许插入或删除操作，不允许修改（元素类型是const）；

③set的底层是红黑树，所以其底层实际存放的是<value,value>的键值对，但在插入删除时只需要给出value即可。其查找元素时间复杂度是logN。

4.2 set的接口

4.2.1 set的模板参数

        模板参数中包含：

key——set中存放的数据类型；

Compare——比较逻辑的仿函数，缺省值是less小于比较，形成左树小，右树大的结构。

4.2.2 set构造函数

（1）默认构造；

（2）迭代区间(first,last)构造；

（3）拷贝构造。

4.2.3 set迭代器

        multiset的接口使用方法和set完全一致，其唯一不同就是允许存储重复元素。

5. map的用法

5.1 map的特征

        map和set有一定的相似性，运用到的是KV模型，下面是mapt特征的汇总：

①容器中存储的元素有两个值，一个是标识它的key，一个是表示其值的value。不允许出现相同key的元素，而不同key允许value相同。

②map的元素key不可以被修改，但是其对应的value允许修改，可通过[]操作符进行新增或修改操作。

③map的底层是红黑树，其底层存放的是<key,value>的键值对。查找元素时间复杂度是logN。

5.2 map的接口

5.2.1 map的模板参数

        模板参数中包含：

key——map中存放的键值对的key的类型；

T——map中存放的键值对的value的类型；

Compare——比较逻辑的仿函数，缺省值是less小于比较，形成左树小，右树大的结构。

5.2.2 map构造函数

（1）默认构造；

（2）迭代区间(first,last)构造；

（3）拷贝构造。

5.2.3 map迭代器

        multimap的接口使用方法和map完全一致，其唯一不同也是允许存储重复元素。

6.set和map的模拟实现

6.1 红黑树的接口改造

        因为set和map的底层都是红黑树，所以我们首先需要对之前写过的红黑树进行改造。

6.1.1 红黑树的结点

        红黑树结点为了同时适用于set和map，因此模板参数使用一个T来表示。当set使用时，T就是一个规定的类型；当map使用时，T就是一个pair类型的键值对。

enum color {
RED,
BLACK
};

//红黑树的结点
//由于不确定所适配的是什么容器（set是K，map是KV），因此使用一个模板参数T进行代替
template<class T>
struct RBTreeNode {
T _val;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
color _color;

RBTreeNode(T val)
:_val(val)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _color(RED)
{}
};

6.1.2  红黑树的迭代器

        因为set和map均需要使用迭代器，因此红黑树也需要实现它的迭代器。我们首先给出其框架代码，然后再逐一补全。

        迭代器封装的是红黑树的结点，除此之外，为了满足自减操作的需要，需要额外需要一个说明树的根节点的成员（在库中使用了带头结点的树来满足这个需求）。迭代器的模板为了满足const的需求，依旧是经典的三个。

//对于红黑树，我们需要为它写一个迭代器类型
template<class T, class Ptr, class Ref>
class RBTreeIterator {
private:
typedef RBTreeNode<T> Node;
Node* _node;
Node* _root;
typedef RBTreeIterator<T, Ptr, Ref> self;

public:
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{}
};

6.1.2.1 前置++

        一般遍历红黑树的策略都是中序遍历，因为这样得到的是一个递增或递减的序列，具有实际意义。所以我们就要通过能够仅凭一个指定的点，找到其在红黑树中序遍历的下一个结点。

        中序遍历顺序是左→中→右，因此拿到一个节点，其突破点就在于有无右树。

①若其具有右树，则说明此时迭代器当前处于“中”，接下来就该中序访问右子树，即下一个结点是右子树的最左节点。

②若其没有右子树，则说明当前右子树遍历完了，现在就需要确定是哪棵树的右子树遍历完了，于是可以一直向父结点回溯寻找。如果是右孩子就说明它的右子树也遍历完了，所以继续向上找父结点；当发现是父结点的左孩子就说明它的左子树遍历完了，那么此时下一个节点即为这个父结点；也有可能父结点为空了，说明整棵树遍历完成，返回空指针作为遍历的end。

self& operator++()
{
//采取中序遍历（左根右）的策略，那么对于++而言，找到下一位置是谁即可
//分情况讨论：
//基本思路就是看当前子树是否遍历完成，有右树就代表没有完成，需要继续处理右树。如果完成就向上找，自己属于哪一棵左子树，从而继续遍历根节点和右树

//①如果发现当前结点有右孩子，那么说明下一个结点是右子树的最左孩子
if (_node->_right)
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;

//②如果发现当前结点是父结点的左孩子，那么下一个结点就是应该是该结点的父亲
//③如果发现当前结点没有右子树，那么说明下个结点就是向上找，直到找到是左孩子的父结点
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}

6.1.2.2 前置--

         --即为++的逆序，逻辑十分相似。首先因为end是由空指针替代，所以没有任何树的信息，于是才引入了一个成员记录树的根节点，以便在第一次--操作时可以通过一直找右的方法找到第一个遍历的结点。

        在之后，类似的，只需判断有无左孩子。有则说明下一个节点就是左子树的最右结点；没有则向上回溯直到找到是谁的右孩子。

self& operator--()
{
//相当于++操作的逆序，也就成了右根左的遍历顺序了
//基本思路：看当前子树是否遍历完成，有左树就代表没有完成，需要继续处理左树。如果完成就向上找，自己属于哪一棵右子树，从而继续遍历根节点和左树

//对于--操作而言，起点可以是end()，即一个空指针，当从空指针开始--时，需要找到中序遍历的最后一个节点，即最右节点,因此需要知道根节点，所以迭代器需要新增一个root成员
//但在实际的std库中，红黑树具有一个头结点，所以迭代器不会走到空，也就不需要这个root成员了
if (_node == nullptr)
{
Node* cur = _root;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
//①如果发现当前结点有左孩子，那么说明下一个结点是左子树的最右孩子
else if (_node->_left)
{
Node* cur = _node->left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;

//②如果发现当前结点是父结点的右孩子，那么下一个结点就是应该是该结点的父亲
//③如果发现当前结点没有左子树，那么说明下个结点就是向上找，直到找到是右孩子的父结点
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}

6.1.2.3 其他函数

         其他函数包括解引用、判断相等等函数。

Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
bool operator==(const self& it)
{
return it._node == _node;
}
bool operator!=(const self& it)
{
return it._node != _node;
}

6.1.3 红黑树

6.1.3.1 模板参数与默认成员函数

        为了同时兼容set和map，红黑树参数模板缩减至三个。、

K——key的类型；

T——value的类型，或者说是应该存储的元素的类型。对于set而言T与K是相同的，对于map而言T就是pair<key，value>；

KeyOfT——取得key值的仿函数。因为set的key可以直接取得，而map的key需要访问pair的first成员得到，因此给出仿函数来解决这个问题。

template<class K, class T, class KeyOfT>
//模板参数：
// K——key的类型
// T——value的类型，对于set而言T与K是相同的，对于map而言T就是pair<key，value>
// KeyOfT——取得key值的仿函数
class RBTree {
typedef RBTreeNode<T> RBNode;

public:
//无参构造
RBTree()
:_root(nullptr)
{}

//拷贝构造
RBTree(const RBTree& rb)
{
_root = copy(rb._root);
}
private:
RBNode* copy(RBNode* root)
{
if (root == nullptr) return nullptr;
RBNode* newnode = new RBNode(root->_val);
newnode->_left = copy(root->_left);
newnode->_right = copy(root->_right);
return newnode;
}

public:
//析构函数
~RBTree()
{
destroy(_root);
_root = nullptr;
}
private:
void destroy(RBNode* root)
{
if (root == nullptr) return;
destroy(root->_left);
destroy(root->_right);
delete root;
}

public:
//赋值重载操作符
RBTree& operator=(const RBTree rb)
{
swap(_root, rb->_root);
return *this;
}

private:
RBNode* _root;
};

6.1.3.2 迭代器

        实现了const和非const两种迭代器。begin函数即为开始点，找到最左结点即可；end函数则是空指针构造迭代器。

//迭代器
public:
typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> constiterator;
iterator begin()
{
RBNode* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur, _root);
}
iterator end()
{
return iterator(nullptr, _root);
}
constiterator cbegin()
{
RBNode* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return constiterator(cur, _root);
}
constiterator cend()
{
return { nullptr,_root };
}

6.1.2.3 其他函数

        注意修改insert和find返回值。insert返回迭代器和bool的pair，使用make_pair来构造。find返回迭代器。

//插入
//在标准库中，insert返回的实际上是pair<iterator,bool>,可以通过库函数make_pair(T1 x,T2 y)来创建pair
pair<iterator, bool> insert(const T& data)
{
//第一个结点特殊处理
if (_root == nullptr)
{
_root = new RBNode(data);
_root->_color = BLACK;
return make_pair(iterator(_root, _root), true);
}

RBNode* cur = _root;
RBNode* parent = nullptr;
//对于set和map，它们取出key值的方法是不同的
//set的key和value相同，就是传入的参数data，因此直接使用data既可以拿到key值
//而map的key值不同，它传入的data是一个结构体pair，需要通过pair.first的形式来拿到key值
//可见面对这样同种目的但操作不同的情况，就需要通过仿函数来解决了
//
//以红黑树为底层的容器，需要提供对应的仿函数来完成取得key值的功能，而在红黑树中，只需要使用即可
KeyOfT Getkey;

while (cur)
{

if (Getkey(cur->_val) > Getkey(data))
{
parent = cur;
cur = cur->_left;
}
else if (Getkey(cur->_val) < Getkey(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur,_root),false);
}
}
cur = new RBNode(data);
if (Getkey(parent->_val) > Getkey(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
RBNode* ret = cur;
//调整红黑树颜色
//红黑树规则：
// ①根结点颜色一定是黑色
// ②不能出现连续的红结点，即红结点的孩子一定是黑色
// ③各条路径（根结点->叶子结点）上的黑色节点数目相同
// ④叶子结点（此处认为是空结点）颜色为黑色
            //在这样的规则限制下，不难发现红黑树最长路径一定小于最短路径的二倍这个特征

//当违反了红黑树规则才需要调整红黑树颜色
//插入新的结点时，选择插入红色节点可能违反不能有连续的红色节点的规则；选择插入黑色节点则必然会违反黑色节点数目相同的规则
//因此两害相权取其轻，选择插入红色节点，因此我们主要处理的就是连续红结点的问题
//于是连续的两个节点：cur和p都是红色的，而u作为p的兄弟节点决定了调整方式，而在调整中受影响的则是p和u的父结点g
while (parent && parent->_color == RED)
{
//根据形式的不同，一般分为三类处理
//在解决连续红色的问题时，也要兼顾到褐色节点数目相同这一规则
RBNode* grandparent = parent->_parent;
RBNode* uncle = parent == grandparent->_left ? grandparent->_right : grandparent->_left;
//①u为红色（p、u均为红）
//p、u同时变为黑色，g变为红色，因为g是红色，因此需要继续向上检查
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
grandparent->_color = RED;
parent = grandparent->_parent;
cur = grandparent;
}
//②u为黑色或不存在，而g、p和cur是顺位（左左或右右）
//此时单纯的变色会使得p子树和u子树路径黑色节点数目不同（因为在修改p为黑，u本就为黑，u相较p黑色节点少一个）
//为了可以顺利变色，我们首先要旋转，红色的p成为了子树的根，黑色的g成为了u这棵树的父结点，此时可以证明只需要p变为黑，g变为红即可
//旋转操作就是AVL树中的左右单旋

//③u为黑色或不存在，而g、p和cur是逆位（左右或右左）
//此时只需要将p结点左旋或右旋一次即可形成如②的情况，因此这种情况使用双旋即可
else
{
if (parent == grandparent->_left)
{
//左左顺位——右旋，p变黑，g变红
if (cur == parent->_left)
{
RotateR(grandparent);
}
//左右逆位——左右双旋，p变黑，g变红
else
{
RotateLR(grandparent);
}
}
else
{
//右右顺位——左旋，p变黑，g变红
if (cur == parent->_right)
{
RotateL(grandparent);
}
//右左逆位——右左双旋，p变黑，g变红
else
{
RotateRL(grandparent);
}
}
//由于②③结果的子树根结点都是黑色因此不会影响上一层，无需向上检查
break;
}
}
//根结点有可能变色，需要修改
_root->_color = BLACK;
return make_pair(iterator(ret, _root), true);
}

iterator find(const K& key)
{
RBNode* cur = _root;
KeyOfT Getkey;

while (cur)
{
if (key > Getkey(cur->_val))
{
cur = cur->_right;
}
else if (key < Getkey(cur->_val))
{
cur = cur->_left;
}
else
{
return iterator(cur, _root);
}
}
return iterator(nullptr, _root);
}

private:
void RotateL(RBNode* grandparent)
{
RBNode* subR = grandparent->_right;
RBNode* subRL = subR->_left;

//结点链接三组：subR和grandparent、grandparent和sunRL、grandparent->_parent和subR
subR->_left = grandparent;
grandparent->_right = subRL;
if (grandparent->_parent == nullptr)
{
_root = subR;
}
else if (grandparent->_parent->_left == grandparent)
{
grandparent->_parent->_left = subR;
}
else
{
grandparent->_parent->_right = subR;
}

subR->_parent = grandparent->_parent;
grandparent->_parent = subR;
if (subRL)//右左子树为空树
subRL->_parent = grandparent;

//修改颜色：p变黑，g变红
subR->_color = BLACK;
grandparent->_color = RED;
}

void RotateR(RBNode* grandparent)
{
RBNode* subL = grandparent->_left;
RBNode* subLR = subL->_right;

//结点链接三组：subL和grandparent、grandparent和sunLR、grandparent->_parent和subL
subL->_right = grandparent;
grandparent->_left = subLR;
if (grandparent->_parent == nullptr)
{
_root = subL;
}
else if (grandparent->_parent->_left == grandparent)
{
grandparent->_parent->_left = subL;
}
else
{
grandparent->_parent->_right = subL;
}

subL->_parent = grandparent->_parent;
grandparent->_parent = subL;
if (subLR)//左右子树为空树
subLR->_parent = grandparent;

//修改颜色：p变黑，g变红
subL->_color = BLACK;
grandparent->_color = RED;
}

//左右双旋
void RotateLR(RBNode* grandparent)
{
RBNode* subL = grandparent->_left;
RBNode* subLR = grandparent->_left->_right;

//只需要旋转，颜色最后指定
RotateL(subL);
RotateR(grandparent);

//修改颜色：cur变黑，g变红
subLR->_color = BLACK;
grandparent->_color = RED;
}

//右左双旋
void RotateRL(RBNode* grandparent)
{
RBNode* subR = grandparent->_right;
RBNode* subRL = grandparent->_right->_left;

//只需要旋转，颜色最后指定
RotateR(subR);
RotateL(grandparent);

//修改颜色：cur变黑，g变红
subRL->_color = BLACK;
grandparent->_color = RED;
}

6.2 set的封装

        封装set只需要调用对应红黑树的接口就好。

        注意两处：①提供红黑树使用的仿函数：set的key和value相同，传入key，返回key即可。②typedef迭代器时，由于定义的是模板类的中的类型，因为模板没有实例化，所以编译器不知道iterator是什么，需要给出关键字typename说明这是一个类型名。

template <class K>
class set {
//取出Key的仿函数
struct Set_KeyOfT
{
//传入一个value，是T类型，要求返回value的key
//set的value和key相同
const K& operator()(const K& key)
{
return key;
}
};
public:
//由于是对模板类中的类型进行重命名，模板类没有实例化，编译器并不知道iterator是什么，因此需要加上typename来告诉编译器这是一个类型名
typedef typename RBTree::RBTree<K, K, Set_KeyOfT>::iterator iterator;
typedef typename RBTree::RBTree<K, K, Set_KeyOfT>::constiterator constiterator;
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
constiterator cbegin()
{
return _tree.cbegin();
}
constiterator cend()
{
return _tree.cend();
}

pair<iterator,bool> insert(const K& key)
{
return _tree.insert(key);
}
iterator find(const K& key)
{
return _tree.find(key);
}

private:
RBTree::RBTree<K, K, Set_KeyOfT> _tree;
};

6.3 map的封装

        同样的，封装map也只需要调用对应红黑树的接口就好。

        注意三处：①提供红黑树使用的仿函数：传入value值，即一个pair，返回pair的first成员就是key。②typedef迭代器需要给出关键字typename。③注意[]函数的实现。

template <class K, class V>
class map {
//取出Key的仿函数
struct Map_KeyOfT
{
//传入一个value，是T类型，要求返回value的key
//map的value是一个pair，key是pair的first
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//由于是对模板类中的类型进行重命名，模板类没有实例化，编译器并不知道iterator是什么，因此需要加上typename来告诉编译器这是一个类型名
typedef typename RBTree::RBTree<K, pair<const K, V>, Map_KeyOfT>::iterator iterator;
typedef typename RBTree::RBTree<K, pair<const K, V>, Map_KeyOfT>::constiterator constiterator;
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
constiterator cbegin()
{
return _tree.cbegin();
}
constiterator cend()
{
return _tree.cend();
}

pair<iterator, bool> insert(const pair<K,V>& kv)
{
return _tree.insert(kv);
}
iterator find(const K& key)
{
return _tree.find(key);
}
V& operator[](const K& key)
{
return find(key)->second;
}

private:
RBTree::RBTree<K, pair<const K, V>, Map_KeyOfT> _tree;
};

原文地址：https://blog.csdn.net/XLZ_44847/article/details/142361479

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！