C++: Encapsulation principle of map and set

Article directory

• Red-black tree packaging
• Encapsulation of map and set
• Implementation of red-black tree iterator
• • Implementation of operator + + and —
  • • ++ implementation process
  • Other modules for iterators
• For implementing const
• • solution to set
  • map solution
• overall implementation

This article was written after the red-black tree simulation was implemented, and map and set were encapsulated to simulate the internal principles of map and set.

First of all, the underlying logic of map and set is a red-black tree, which means that there is no need to re-write like vector/list, but can be appropriately encapsulated directly on the basis of the red-black tree.

However, the red-black tree implemented previously cannot perfectly adapt to the required functions. Therefore, the red-black tree must be modified to a certain extent before it can be used well. Then the red-black tree must first be modified to a certain extent. transformation

This article will analyze the encapsulation principle of red-black trees in the STL library, build a basic framework, and conduct analysis

Red-black tree encapsulation

Take out a copy of the source code in STL and analyze how the tree is encapsulated in the source code.

The definition of the red-black tree is different. In the previous implementation process, the pair key-value pairs were directly used as parameters in the template, resulting in only two types, one is the Key/Key model and the other is the Key /Value model, and in the implementation of source code, the type is directly put into the template to implement, and programming is done with the idea of generics.

In map and set, the parameters that need to be passed are directly passed to Value:

Therefore, when encapsulating, we can encapsulate like this, first make some improvements to the red-black tree we completed ourselves.

First, improve the nodes

template<class T>
structRBTreeNode
{<!-- -->
RBTreeNode(const T & data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
,_col(RED)
{<!-- -->}

RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T_data;
Color_col;
};

Encapsulation of map and set

Now you can make preliminary encapsulation of map and set.

namespace mymap
{<!-- -->
template<class K, class V>
class set
{<!-- -->
private:
RBTree<K, pair<K, V>> _t;
};
}


namespace myset
{<!-- -->
template<class K>
class set
{<!-- -->
private:
RBTree<K, K> _t;
};
}

The next problem encountered is, how to compare the size when inserting data? For example, the following scenario

The above is the logic implemented in the process of simulating the implementation of a red-black tree. The question now is, how to compare key-value pairs?

Find countermeasures in library functions:

The comparison rule is to compare the first element of the key-value pair, so what you need to do now is to find a way to take out the first element of the key-value pair for comparison. Therefore, you can adopt this idea and do it in both map and set. A functor that can take out data can just return the Key when comparing. Therefore, you need to modify the template parameters of the red-black tree, receive the value of a functor, and use it to participate in the comparison when inserting data.

namespace mymap
{<!-- -->
template<class K, class V>
class map
{<!-- -->
private:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const V & amp; data)
{<!-- -->
// For map, Key is the first element in the passed data key-value pair
return data.first;
}
};
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}

namespace myset
{<!-- -->
template<class K>
class set
{<!-- -->
public:
struct SetKeyOfT
{<!-- -->
const K & amp; operator()(const K & amp; data)
{<!-- -->
// For set, K is the data itself
return data.first;
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};
}

At this point, the basic logic has been set up. Inserting elements into map/set is actually inserting them into the tree, and the insertion process is encapsulated externally.

pair<iterator,bool> insert(const V & amp; val)
{<!-- -->
return _t.insert(val);
}

Implementation of red-black tree iterator

Therefore, to implement a red-black tree iterator, the red-black tree iterator is similar to the linked list iterator, and it must be constructed with the help of a class.

template<class T,class Ptr,class Ref>
struct _TreeIterator
{<!-- -->
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, T*, T &> Self;

// Constructor: The essence of an iterator is to encapsulate a layer of pointers
_TreeIterator(Node* node)
:_node(node)
{<!-- -->}

// Implementation of functions in iterator
//Dereference to retrieve data
Ref operator*()
{<!-- -->
return _node->_data;
}

//Get the address of the data
Ptr operator->()
{<!-- -->
return &(_node->_data);
}

// Implementation + +



//The essence of the iterator is the pointer of the node
Node* _node;
};

Implementation of operator + + and –

Implementation process of + +

Take the above figure as an example. At this time, it points to 17. Normally, the traversal order is to traverse in mid-order, so the next number larger than 17 is 22. The conclusion is, + + What we are looking for is the right child’s maximum number. Left subtree, what to do if there is no right subtree?

If there is no right subtree, it means that the traversal has ended and the left subtree has been reached. As shown in the figure above, what we are looking for at this time is that the child is the ancestor of the node on the left of the father.

Based on the above logic, improve the iterator code

 // Implementation + +
Self & operator + + ()
{<!-- -->
// If the right subtree exists, find the leftmost node in the right subtree
if (_node->_right)
{<!-- -->
//The next one is the leftmost node of the right subtree
Node* cur = _node->_right;
while (cur->_left)
{<!-- -->
cur = cur->_left;
}

_node = cur;
}
// If the right subtree does not exist, go to the ancestor whose child is the father's left
else
{<!-- -->
// left subtree root right subtree
Node* cur = _node;
Node* parent = cur->_parent;
// As long as the child is on the right side of the father, continue to loop upward until we find the node where the child is on the left side of the father.
while (parent & amp; & amp; cur == parent->_right)
{<!-- -->
cur = parent;
parent = parent->_parent;
}

_node = parent;
}

return *this;
}

\t// accomplish--
Self & operator--()
{<!-- -->
// If the left subtree exists, find the rightmost node in the left subtree
if (_node->_left)
{<!-- -->
//The next one is the leftmost node of the right subtree
Node* cur = _node->_left;
while (cur->_right)
{<!-- -->
cur = cur->_right;
}

_node = cur;
}
// If the left subtree does not exist, go to the ancestor whose child is the father's right
else
{<!-- -->
// left subtree root right subtree
Node* cur = _node;
Node* parent = cur->_parent;
// As long as the child is on the left of the father, continue to loop upward until we find the node where the child is on the right of the father.
while (parent & amp; & amp; cur == parent->_left)
{<!-- -->
cur = parent;
parent = parent->_parent;
}

_node = parent;
}

return *this;
}

Other modules for iterators

 // To determine equality and inequality, it actually depends on whether the nodes encapsulated inside the iterator are the same node.
bool operator==(const Self & amp; it)
{<!-- -->
return _node == it._node;
}

bool operator!=(const Self & amp; it)
{<!-- -->
return _node != it._node;
}

For implementing const

At present, the implemented content is ready for use, but there are still some problems, such as:

#include <iostream>
#include "MyMap.h"
#include "MySet.h"
using namespace std;

void testMap1()
{<!-- -->
mymap::map<int, int> dict;
dict.insert(make_pair(1, 1));
dict.insert(make_pair(2, 1));
dict.insert(make_pair(3, 1));
dict.insert(make_pair(4,1));
\t
for (auto & e : dict)
{<!-- -->
e.first + + ;
cout << e.first << " ";
}
cout << endl;
}

void testSet1()
{<!-- -->
myset::set<int> st;
st.insert(1);
st.insert(3);
st.insert(2);
auto it = st.begin();
while (it != st.end())
{<!-- -->
(*it) + + ;
cout << *it << " ";
+ + it;
}
cout << endl;
}

int main()
{<!-- -->
testSet1();
testMap1();
return 0;
}

The problem here is that the contents in map and set can be modified, which will cause the entire binary tree to no longer be a binary search tree.

The solution in the map and set library functions is:

set solution

Therefore, you only need to follow the methods in the library to solve this problem

However, you will encounter the next problem at this time:

The reason for the problem is that the type of the end iterator returned here is a non-const version, and converting it to a const version of the iterator will cause problems, so how to deal with this?

A solution is used here, which takes advantage of one of the better features of pair: the construction method is very flexible:

The above is about the constructor of pair. The most flexible thing about pair is that it can be constructed with two unequal template parameters. Its internal constructor is essentially written like this:

template <class T1, class T2>
struct pair
{<!-- -->
template <class U,class V>
pair(const pair<U, V> & amp; pr)
:first(pr.first)
,second(pr.second)
{<!-- -->}
T1 first;
T2 second;
};

In other words, T1, T2, U, and V can all be unequal, as long as there is a suitable constructor between them for construction. Therefore, using this, the return value of insert in the red-black tree is returned to a The pointer of the node, just use the pointer of the node to construct the value returned in the set.

pair<iterator, bool> insert(const K & amp; val)
{<!-- -->
return _t.insert(val);
}

map solution

The solution for map is to fix it directly at the source of the map and set the first element of the pair to const.

Overall implementation

The red-black tree after renovation

#pragma once
#include 
using namespace std;

enum Color
{
RED,
BLACK
};

template<class T>
structRBTreeNode
{<!-- -->
RBTreeNode(const T & data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
,_col(RED)
{<!-- -->}

RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T_data;
Color_col;
};

template
struct _TreeIterator
{
typedef RBTreeNode Node;
typedef _TreeIterator Self;

// Constructor: The essence of an iterator is to encapsulate a layer of pointers
_TreeIterator(Node* node)
:_node(node)
{}

// Implementation of functions in iterator
//Dereference to retrieve data
Ref operator*()
{
return _node->_data;
}

//Get the address of the data
Ptr operator->()
{
return &(_node->_data);
}

// Implementation + +
Self & operator + + ()
{
// If the right subtree exists, find the leftmost node in the right subtree
if (_node->_right)
{
//The next one is the leftmost node of the right subtree
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}

_node = cur;
}
// If the right subtree does not exist, go to the ancestor whose child is the father's left
else
{
// left subtree root right subtree
Node* cur = _node;
Node* parent = cur->_parent;
// As long as the child is on the right side of the father, continue to loop upward until we find the node where the child is on the left side of the father.
while (parent & amp; & amp; cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}

_node = parent;
}

return *this;
}

\t// accomplish--
Self & operator--()
{
// If the left subtree exists, find the rightmost node in the left subtree
if (_node->_left)
{
//The next one is the leftmost node of the right subtree
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}

_node = cur;
}
// If the left subtree does not exist, go to the ancestor whose child is the father's right
else
{
// left subtree root right subtree
Node* cur = _node;
Node* parent = cur->_parent;
// As long as the child is on the left of the father, continue to loop upward until we find the node where the child is on the right of the father.
while (parent & amp; & amp; cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}

_node = parent;
}

return *this;
}

// To determine equality and inequality, it actually depends on whether the nodes encapsulated inside the iterator are the same node.
bool operator==(const Self & amp; it)
{
return _node == it._node;
}

bool operator!=(const Self & amp; it)
{
return _node != it._node;
}

//The essence of the iterator is the pointer of the node
Node* _node;
};

template
classRBTree
{
public:
typedef RBTreeNode Node;
typedef _TreeIterator iterator;
typedef _TreeIterator const_iterator;
//Constructor of red-black tree
RBTree()
:_root(nullptr)
{}

// Destructor of red-black tree
~RBTree()
{
DelNode(_root);
}

// Red-black tree iterator part
iterator begin()
{
Node* cur = _root;
while (cur & amp; & amp; cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}

iterator end()
{
return iterator(nullptr);
}

const_iterator begin() const
{
Node* cur = _root;
while (cur & amp; & amp; cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}

const_iterator end() const
{
return const_iterator(nullptr);
}

// Insertion of elements
pair insert(const T & amp; data)
{
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
// Completed according to the basic logic of searching the binary tree
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);
}
else
{
//Insert data
while (cur)
{
if (kot(cur->_data) > kot(data))
{
//If the inserted element is smaller than the current node element, insert it to the left
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
//The inserted element is larger than the current node element and inserted to the right
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
// At this time, parent points to the last node and cur is empty.
cur = new Node(data);
if (kot(parent->_data) > kot(cur->_data))
{
// If the inserted node is smaller than its parent, insert it to the left
parent->_left = cur;
cur->_parent = parent;
}
else
{
// If the inserted node is larger than its parent, insert it to the right
parent->_right = cur;
cur->_parent = parent;
}
}

// At this point, the insertion of the ordinary binary search tree has been completed, and it is time to adjust the height of the red-black tree.
// The termination condition is that parent is empty, or parent is already black, which means no adjustment is needed.
// parent is red, which means grandparent must exist
while (parent & amp; & amp; parent->_col == RED)
{
// The core of the change is the uncle, so we must first find the uncle
// Generally speaking, there are two situations. The parent may be the left or right side of the grandparent, and the uncle may be the other side.
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
// 1. Uncle exists and is red
if (uncle & amp; & amp; uncle->_col == RED)
{
//g
//p u
//c

// change color
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;

// Process upward
cur = grandparent;
parent = cur->_parent;
}

// 2. Uncle does not exist
else
{
// If cur is the left child
if (cur == parent->_left)
{
//g
// p
// c

// Right-rotate the grandparent
RotateR(grandparent);
// change color
cur->_col = grandparent->_col = RED;
parent->_col = BLACK;
}
// If cur is the right child
else
{
// g g
// p --> c --> c
// c p p g

// Rotate left to parent, rotate right to grandparent
RotateL(parent);
RotateR(grandparent);
// change color
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}

// After the update, the order of parent and grandparent is messed up, and there is no need to continue adjusting, just break
break;
}
}

// parent is the right child of grandparent, the same logic is repeated again
else
{
Node* uncle = grandparent->_left;
if (uncle & amp; & amp; uncle->_col == RED)
{
// change color
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;

// Continue processing
cur = grandparent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
//g
// p
//c
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
//g
//p
//c

RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}

break;
}
}
}
// It doesn't matter how the above changes, just make sure the root node is black.
_root->_col = BLACK;

return make_pair(cur, true);
}

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

parent->_right = subRL;
subR->_left = parent;

Node* parentParent = parent->_parent;

parent->_parent = subR;
if(subRL)
subRL->_parent = parent;

if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}

subR->_parent = parentParent;
}
}

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if(subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}

subL->_parent = parentParent;
}
}

void DelNode(Node* root)
{
if (root == nullptr)
{
return;
}

DelNode(root->_left);
DelNode(root->_right);
delete(root);
}

Node* _root = nullptr;
};

Set encapsulated based on red-black tree

#pragma once

#include "RBTree.h"

namespace myset
{
template
class set
{
public:
struct SetKeyOfT
{
const K & amp; operator()(const K & amp; data)
{
// For set, K is the data itself
return data;
}
};
typedef typename RBTree::const_iterator iterator;
typedef typename RBTree::const_iterator const_iterator;

pair<iterator, bool> insert(const K & amp; val)
{<!-- -->
return _t.insert(val);
}

iterator begin() const
{
return _t.begin();
}

iterator end() const
{
return _t.end();
}
private:
RBTree _t;
};
}

Map constructed based on red-black tree

#pragma once

#include "RBTree.h"


namespace mymap
{<!-- -->
template<class K, class V>
class map
{<!-- -->
public:
struct MapKeyOfT
{<!-- -->
const K & amp; operator()(const pair<K, V> & amp; data)
{<!-- -->
// For map, key is the first element of the key-value pair
return data.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;
pair<iterator, bool> insert(const pair<K, V> & amp; val)
{<!-- -->
return _t.insert(val);
}

iterator begin()
{<!-- -->
return _t.begin();
}

iterator end()
{<!-- -->
return _t.end();
}

const_iterator begin() const
{<!-- -->
return _t.begin();
}

const_iterator end() const
{<!-- -->
return _t.end();
}
private:

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