Transforming Red and Black Trees
catalogs
-
Transforming Red and Black Trees
-
Adapting Red-Black Trees for STL Iterators
- fabric
- RBTreeNode
- __RBTree_iterator
- RBTree
- Full Code
- Encapsulated set
- Encapsulated map
-
Adapting Red-Black Trees for STL Iterators
In the first look at the STL in the implementation of the red-black tree source code some do not understand, and then try to set to RBTree<K,K> way to encapsulate the red-black tree iterator; implementation process found that the degree of reuse of this package is particularly low, but also particularly redundant, so to understand the STL source code to achieve the essence of the reuse of red-black tree. The following section will simulate the implementation of STL to transform the red-black tree and encapsulate the map and set.
The referenced STL version is SGI30
Adapting Red-Black Trees for STL Iterators
The code implementation of red-black tree data manipulation is the old version, the new version is analyzed in detail in the previous blog.
The main feature of this post is on iterator adaptation
fabric
#pragma once
#include<>
#include<iostream>
using std::cout;
using std::endl;
using std::cin;
using std::pair;
using std::make_pair;
using std::string;
namespace test
{
enum Colour { RED, BLACK };
template<class T> struct RBTreeNode;
template<class T, class Ref, typename Ptr> struct __RBTree_iterator;
template<class K, class T, class keyOfT> class RBTree;
}
RBTreeNode
template<class T> // Tbecause ofkeymaybepair,Tbekeymaybe者key-valuetypology
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
T _data; //databekeymaybepair
Colour _col;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
__RBTree_iterator
template<class T, class Ref, typename Ptr>
struct __RBTree_iterator
{
typedef RBTreeNode<T> node.
node* _node;
__RBTree_iterator(node* node)
:_node(node)
{}
// First of all, <class T, class Ref, class Ptr> this way of writing can improve the reusability and flexibility (to realize different types of iterators), etc., library iterators are written this way.
// Secondly, in the template parameters, T is used to get the type, Ref is used to return a reference, and Ptr is used to return a pointer.
using Self = __RBTree_iterator<T,Ref,Ptr>; //Self - instantiated the following two iterators
using iterator = __RBTree_iterator<T,T&,T*>; //ordinary iterator
using const_iterator = __RBTree_iterator<T,const T&,const T*>; //const iterator
__RBTree_iterator(const iterator& it)
:_node(it._node)
{}
// What this constructor does, //a.
//a. When an iterator is instantiated as an iterator, it is a copy constructor. __RBTree_iterator<T,T&,T*>.
//b. When an iterator is instantiated as const_iterator, it is a parametric constructor with implicit type conversion. __RBTree_iterator<T,const T&,const T*>.
// The purpose of this implementation is
// To reuse normal iterators, which can be implemented as const iterators with type conversion.
// Ref is T& or const T&, Ptr is T* or const T*.
//typedef __RBTree_iterator<T, Ref, Ptr> Self.
Ref operator*()
{
return _node->_data.
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& x)
{
return _node ! = x._node; }
}
//prior++
Self& operator++() {
//This version of the iterator implementation does not need to be null, null means that the traversal is over, or the user has made a mistake.
Node* cur = _node; //1.
//1. has right subtree
if (cur->_right) {
// Find the minimum node of the right subtree.
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMin = rightMin->_left;
}
_node = rightMin;
}
/2. no right subtree
else {
////1. no father, indicating root
//Node* parent = cur->_parent;
//if (parent == nullptr) {
// _node == nullptr.
//}
////2. and I am the left subtree of the parent, which means that the father is the next positive-order value
//else if (parent->_left == cur) {
// _node = parent.
//}
////3. Or I'm the right subtree of the parent, which means I've finished the current least-branched ancestor tree. Iterating up
//else if (parent->_right == cur) {
// while (parent && cur ! = parent->_left) {
// cur = parent; // parent = parent->_left
// parent = parent->_parent;
// }
// _node = parent; // cur = parent; // parent = parent->_parent; // }
//}
//else {
// asssert(false);
//}
// The above 3 cases can be combined into one case: find the nearest grandfather that is not a right child
Node* parent = cur->_parent;
while (parent && cur ! = parent->_left) {
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this; }
}
// Posterior ++
Self operator++(int) {
Self tmp(_node).
operator++().
operator++(); return tmp.
}
Self& operator--() {
// Reverse ++ to get --.
Node* cur = _node.
// If the left subtree exists, find the largest.
if (cur->_left) {
Node* leftMax = cur->_left;
while (leftMax->_right) {
leftMax = leftMax->_right;
}
_node = leftMax;
}
/2. no left subtree
else {
Node* parent = cur->_parent;
while (parent && cur ! = parent->_right) {
cur = parent; cur = parent->_parent; while (parent && cur !
parent = parent->_parent;
}
_node = parent; }
}
return *this; }
}
Self operator--(int) {
Self tmp(_node); operator--(int); return *this; }
operator--().
operator--(); return tmp; }
}
}
RBTree
//parametersKspend onfind,eraseet al. (and other authors),even thoughKIt can also beTsupersedes,But it's not necessary.,Kfaster
template<class K, class T, class keyOfT> //Also in the library1classifier for individual things or people, general, catch-all classifiercompare，Let's leave it at that.
class RBTree
{
public:
typedef RBTreeNode<T> node; //Tbekeymaybepair
public:
typedef __RBTree_iterator<T, T&, T*> iterator;
typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
node* cur = _root;
while (cur && cur->_left)//Can't walk to empty
{
cur = cur->_left;
}
return iterator(cur);//返回中序的第一classifier for individual things or people, general, catch-all classifier结点,leftmost node
}
iterator end() //endbe最一classifier for individual things or people, general, catch-all classifier位置的下一classifier for individual things or people, general, catch-all classifier
{
return iterator(nullptr);//For the time being, you can write it like this
}
const_iterator begin()const
{
node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
const_iterator end() const
{
return iterator(nullptr);
}
private:
node* _root = nullptr;
public:
node* find(const K& key)
{
keyOfT kot;//kotbeclassifier for individual things or people, general, catch-all classifier仿函数,根据不同parameters返回不同的parameters对象
node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
cur = cur->_left;
}
else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<iterator, bool> insert(const T& data)
{
if (!_root)
{
_root = new node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root), true);
}
keyOfT kot;
node* cur = _root;
node* parent = nullptr;
while (cur)
{
if (kot(cur->_data) < kot(data) ) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
parent = cur;
cur = cur->_left;
}
else
{
return std::make_pair(iterator(cur), false);
}
}
cur = new node(data);
if ( kot(parent->_data) < kot(data)) // --------------------------------------------
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//align/revolve
node* newnode = cur;//align过程curround,commander-in-chief (military)curNode Remember -- Remember the originalkeylocation
while (parent && parent->_col == RED)
{
node* g = parent->_parent;
if (parent == g->_right)
{
node* u = g->_left;
if (u && u->_col == RED)
{
g->_col = RED;
parent->_col = BLACK;
u->_col = BLACK;
cur = g;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(g);
parent->_col = BLACK;
g->_col = RED;
}
else
{
RotateR(parent);
RotateL(g);
g->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else
{
node* u = g->_right;
if (u && u->_col == RED)
{
g->_col = RED;
parent->_col = BLACK;
u->_col = BLACK;
cur = g;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(g);
parent->_col = BLACK;
g->_col = RED;
}
else
{
RotateL(parent);
RotateR(g);
g->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return std::make_pair(iterator(newnode), true);
}
public:
void InOrderTraversal()
{
_InOrderTraversal(_root);
}
bool isBalanceTree()
{
//judgement required3classifier for individual things or people, general, catch-all classifier规则
//1.Roots are black
if (_root && _root->_col == RED)
{
cout << "incorrect:根be红色" << endl;
return false;
}
//2.You can't have continuous red.
//3.accomplice (in crime)
int benchmark = 0;
node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return _check(_root, 0, benchmark);
}
int Height()
{
return _Height(_root);
}
~RBTree()
{
Destroy(_root);
}
private:
void Destroy(node*& root)
{
if (!root)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
bool _check(node* root, int blackNum, int benchmark)
{
keyOfT kot;
if (!root) //
{
if (blackNum != benchmark)
{
cout << "incorrect:There exists a different number of black nodes for different paths" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << kot(root->_data) << " incorrect,Red at the same time as the parent node"; // --------------------------------------------
return false;
}
return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
}
int _Height(node* root)
{
if (!root)
{
return 0;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
void _InOrderTraversal(node* root)
{
keyOfT kot;
if (root == nullptr)
{
return;
}
_InOrderTraversal(root->_left);
cout << kot(root->_data) << " "; // --------------------------------------------
_InOrderTraversal(root->_right);
}
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
node* pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (!pparent)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
};
Full Code
#pragma once
#include<>
#include<iostream>
using std::cout;
using std::endl;
using std::cin;
using std::pair;
using std::make_pair;
using std::string;
namespace test
{
//with the library'sRBTdiscrepancy
/**
*
* Number of nodes left in the library count
*
* libraryRBTIt's the Sentinel Guard who led the node.,The left of the head node is the first in the middle order(minimum node),The right node is the last in the middle order(largest node),
* sentinelparentpoint to the root node,rootparentpoint to the sentry-guard
*
* library(used form a nominal expression)begindirect accesshead(used form a nominal expression)left -- function (math.):leftmost() //leftmost node
* library(used form a nominal expression)end behead(used form a nominal expression)right -- 不berightmost,rightmostbe最右结点,endbe最右结点(used form a nominal expression)下一classifier for individual things or people, general, catch-all classifier
* library(used form a nominal expression)end There's a judgment call to be made.,防止只有左子树(used form a nominal expression)歪脖子树hour,end == head->right,dead cycle
*
* 和库(used form a nominal expression)区别就beend,库(used form a nominal expression)endTo be able to walk back tohead,我(used form a nominal expression)不能,You can only go so far before you run out of air.d
*
*/
enum Colour { RED, BLACK };
template<class T> //Tbe什么,Why only passT? Tbecause ofkeymaybepair,Tbekeymaybe者key-valuetypology
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
T _data; //databekeymaybepair
Colour _col;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
//const_iterator<T,const T&,const T*>
//iterator<T, T&, T*>
template<class T, class Ref, typename Ptr>
struct __RBTree_iterator
{
typedef RBTreeNode<T> node;
node* _node;
__RBTree_iterator(node* node)
:_node(node)
{}
//in the first place,<class T, class Ref, class Ptr>This writing style improves reusability and flexibility(实现不同typology(used form a nominal expression)iterator (math.))et al. (and other authors),,This is how iterators are written in the library
//secondly,In the template parameters,T用于获取typology,RefUsed to return references,PtrUsed to return pointers
using Self = __RBTree_iterator<T,Ref,Ptr>; //oneself--Instantiate the following two iterators
using iterator = __RBTree_iterator<T,T&,T*>; //ordinary iterator (math.)
using const_iterator = __RBTree_iterator<T,const T&,const T*>; //constiterator (math.)
__RBTree_iterator(const iterator& it)
:_node(it._node)
{}
//这classifier for individual things or people, general, catch-all classifier构造function (math.)(used form a nominal expression)作用,
//a.当iterator (math.)被实例化成iteratorhour,他就be拷贝构造function (math.). __RBTree_iterator<T,T&,T*>
//b.当iterator (math.)被实例化成const_iteratorhour,他be支持隐式typology转换(used form a nominal expression)带参构造function (math.). __RBTree_iterator<T,const T&,const T*>
//这样实现(used form a nominal expression)目(used form a nominal expression)
// 能够复用ordinary iterator (math.),可以通过typology转换后直接实现出constiterator (math.)
//Refbecause of T& maybe const T&, Ptrbecause of T* maybe const T*
//typedef __RBTree_iterator<T, Ref, Ptr> Self;
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& x)
{
return _node != x._node;
}
//preamplifier++
Self& operator++() {
//此版本实现iterator (math.)不需要判空,because of空说明遍历结束,要么be用户incorrect使用
Node* cur = _node;
//1. right subtree (math.)
if (cur->_right) {
//找右子树(used form a nominal expression)minimum node
Node* rightMin = cur->_right;
while (rightMin->_left) {
rightMin = rightMin->_left;
}
_node = rightMin;
}
//2. 没right subtree (math.)
else {
////1.No father.,说明be根
//Node* parent = cur->_parent;
//if (parent == nullptr) {
// _node == nullptr;
//}
////2.且我be父(used form a nominal expression)左子树,说明父亲be下一classifier for individual things or people, general, catch-all classifier正序值
//else if (parent->_left == cur) {
// _node = parent;
//}
////3.maybe我be父亲(used form a nominal expression)右子树,This means that the current minimum branch ancestor tree has been completed..Iterate upwards
//else if (parent->_right == cur) {
// while (parent && cur != parent->_left) {
// cur = parent;
// parent = parent->_parent;
// }
// _node = parent;
//}
//else {
// asssert(false);
//}
//on top of3The cases can be combined into a single case:找最近(used form a nominal expression)不be右孩子(used form a nominal expression)祖父
Node* parent = cur->_parent;
while (parent && cur != parent->_left) {
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//place after (e.g. in grammar)++
Self operator++(int) {
Self tmp(_node);
operator++();
return tmp;
}
Self& operator--() {
//commander-in-chief (military)++反过来就be--
Node* cur = _node;
//Left subtree exists,Just look for the biggest.
if (cur->_left) {
Node* leftMax = cur->_left;
while (leftMax->_right) {
leftMax = leftMax->_right;
}
_node = leftMax;
}
//2. No left subtree
else {
Node* parent = cur->_parent;
while (parent && cur != parent->_right) {
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self operator--(int) {
Self tmp(_node);
operator--();
return tmp;
}
};
//parametersKspend onfind,eraseet al. (and other authors),even thoughKIt can also beTsupersedes,But it's not necessary.,Kfaster
template<class K, class T, class keyOfT> //library还有1classifier for individual things or people, general, catch-all classifiercompare，Let's leave it at that.
class RBTree
{
public:
typedef RBTreeNode<T> node; //Tbekeymaybepair
public:
typedef __RBTree_iterator<T, T&, T*> iterator;
typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
node* cur = _root;
while (cur && cur->_left)//Can't walk to empty
{
cur = cur->_left;
}
return iterator(cur);//返回中序(used form a nominal expression)第一classifier for individual things or people, general, catch-all classifier结点,leftmost node
}
iterator end() //endbe最一classifier for individual things or people, general, catch-all classifier位置(used form a nominal expression)下一classifier for individual things or people, general, catch-all classifier
{
return iterator(nullptr);//暂hour可以这么写
}
const_iterator begin()const
{
node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
const_iterator end() const
{
return iterator(nullptr);
}
private:
node* _root = nullptr;
public:
node* find(const K& key)
{
keyOfT kot;//kotbeclassifier for individual things or people, general, catch-all classifier仿function (math.),根据不同parameters返回不同(used form a nominal expression)parameters对象
node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
cur = cur->_left;
}
else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<iterator, bool> insert(const T& data)
{
if (!_root)
{
_root = new node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root), true);
}
keyOfT kot;
node* cur = _root;
node* parent = nullptr;
while (cur)
{
if (kot(cur->_data) < kot(data) ) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一classifier for individual things or people, general, catch-all classifier '<' maybe '>' Then you can compare the sizes
{
parent = cur;
cur = cur->_left;
}
else
{
return std::make_pair(iterator(cur), false);
}
}
cur = new node(data);
if ( kot(parent->_data) < kot(data)) // --------------------------------------------
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//align/revolve
node* newnode = cur;//align过程curround,commander-in-chief (military)curNode Remember -- Remember the originalkey(used form a nominal expression)位置
while (parent && parent->_col == RED)
{
node* g = parent->_parent;
if (parent == g->_right)
{
node* u = g->_left;
if (u && u->_col == RED)
{
g->_col = RED;
parent->_col = BLACK;
u->_col = BLACK;
cur = g;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(g);
parent->_col = BLACK;
g->_col = RED;
}
else
{
RotateR(parent);
RotateL(g);
g->_col = RED;
cur->_col = BLACK;
}
break;
}
}
else
{
node* u = g->_right;
if (u && u->_col == RED)
{
g->_col = RED;
parent->_col = BLACK;
u->_col = BLACK;
cur = g;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(g);
parent->_col = BLACK;
g->_col = RED;
}
else
{
RotateL(parent);
RotateR(g);
g->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
_root->_col = BLACK;
return std::make_pair(iterator(newnode), true);
}
public:
void InOrderTraversal()
{
_InOrderTraversal(_root);
}
bool isBalanceTree()
{
//judgement required3classifier for individual things or people, general, catch-all classifier规则
//1.根because of黑
if (_root && _root->_col == RED)
{
cout << "incorrect:根be红色" << endl;
return false;
}
//2.You can't have continuous red.
//3.accomplice (in crime)
int benchmark = 0;
node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return _check(_root, 0, benchmark);
}
int Height()
{
return _Height(_root);
}
~RBTree()
{
Destroy(_root);
}
private:
void Destroy(node*& root)
{
if (!root)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
bool _check(node* root, int blackNum, int benchmark)
{
keyOfT kot;
if (!root) //
{
if (blackNum != benchmark)
{
cout << "incorrect:存在不同路径(used form a nominal expression)黑色结点数量不相同" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << kot(root->_data) << " incorrect,与父节点同hourbecause of红色"; // --------------------------------------------
return false;
}
return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
}
int _Height(node* root)
{
if (!root)
{
return 0;
}
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
void _InOrderTraversal(node* root)
{
keyOfT kot;
if (root == nullptr)
{
return;
}
_InOrderTraversal(root->_left);
cout << kot(root->_data) << " "; // --------------------------------------------
_InOrderTraversal(root->_right);
}
void RotateL(node* parent)
{
node* subR = parent->_right;
node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
node* pparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (!pparent)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
subR->_parent = pparent;
}
}
void RotateR(node* parent)
{
node* subL = parent->_left;
node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
node* pparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
subL->_parent = pparent;
}
}
};
}
Encapsulated set
After the completion of the red-black tree transformation, encapsulation of set and map is relatively simple, basically are applied to the function of the red-black tree, especially convenient, which also realized the realization of the STL of the big brother's awesome.
#pragma once
#include""
namespace test
{
template<class K>.
class set
{
private.
struct setKeyOfT // retrieve the key of type T of RBT.
{
const K& operator()(const K& key)
{
return key; }
}
}
private.
RBTree< K, K, setKeyOfT>_t;
public.
// Add typename to class fields to prevent conflicts with static variables.
typedef typename RBTree<K, K, setKeyOfT>::const_iterator iterator; // Common iterator
typedef typename RBTree<K, K, setKeyOfT>::const_iterator const_iterator; //const iterator
iterator begin()
{
return _t.begin(); //begin is a normal iterator, return value is const, implicit type conversion occurs (single argument)
//If there is a corresponding constructor, implicit type conversion is supported, but the iterator does not have a constructor whose arguments are iterators, so you need to add it.
}
iterator end()
return _t.end(); } iterator end()
return _t.end(); }
}
const_iterator begin()const
return _t.begin(); } const_iterator begin() const
return _t.begin(); }
}
const_iterator end()const
return _t.end(); } const_iterator end() const {
return _t.end(); }
}
public.
pair<iterator, bool> insert(const K& key)
{
return _t.insert(key);
}
}; }
void test_mySet1()
{
test::set<int> s.
(2);
(1);
(3);
set<int>::iterator it = ();
//while (it!=())
//{
// cout << *it << " ";
// ++it;
//}
for (auto& e : s)
{
cout << e << " ";
}
cout << *++it << " ";
cout << *--it << " ";
cout << endl;
//*it = 1;//// Assignment is not allowed, expression must be left-valued that can be modified . Constants cannot be assigned values.
}
}
Encapsulated map
#pragma once
#include""
namespace test
{
template<class K,class V>
class map
{
private:
struct mapKeyOfT
{
const K& operator()(const pair<const K,V>& kv)
{
return ;
}
};
private:
RBTree<K, pair<const K, V>, mapKeyOfT> _t;
public:
typedef typename RBTree<K, pair<const K,V>, mapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
public:
pair<iterator,bool> insert(const pair<const K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pair<iterator,bool> ret = insert(make_pair(key, V()));
return ->second;
}
};
void test_myMap1()
{
test::map<int, int> m;
(std::make_pair(1, 1));
(std::make_pair(3, 3));
(std::make_pair(2, 2));
test::map<int,int>::iterator it = ();
//while (it != ())
//{
// cout << it->first << " ";
// ++it;
//}
for (auto e : m)
{
cout << << " ";
}
cout << (++it)->first << " ";
cout << (--it)->first << " ";
cout << endl;
//it->second = 1; //assignable
//it->first = 1;//Assignment is not allowed,Expressions must be modifiable left values .Constants cannot be assigned values
}
void test_myMap2()
{
//maputilization
map<std::string, std::string> dict;
(std::pair<std::string, std::string>("sort", "arrange in order")); //Anonymous object insertion
(std::make_pair("string", "string (computer science)")); //pairCapsule insertion
(std::make_pair("count", "reckoning"));
(std::make_pair("count", "(reckoning)")); //stuck
auto it = ();
while (it != ())
{
cout << it->first << ":" << it->second << endl;
++it;
}
}
void test_myMap3()
{
std::string arr[] = { "pomegranate", "cantaloupe", "pomegranate", "cantaloupe", "pomegranate", "pomegranate", "cantaloupe","pomegranate", "bananas", "pomegranate", "bananas" };
map<std::string, int> countMap;
/*for (auto e : arr)
{
auto ret = (x);
if (ret==())
{
(std::pair<string, int>(x, 1));
}
else
{
++ret->second;
}
}*/
for (auto& e : arr)
{
++countMap[e];
}
for (auto& s : countMap)
{
cout << << ":" << << endl;
}
}
}