The Code

Pair.h
template <class T1, class T2> struct pair { T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b) {} }; template <class T1, class T2> inline pair<T1, T2> make_pair(const T1& k, const T2& t) { return pair<T1, T2>(k, t); }


Set.h
#include "Pair.h" template<typename T> class Set { public: class iterator; using Comparator = bool(*)(T*, T*); Set(); Set(Comparator c); ~Set(); pair<iterator, bool> insert(T); void clear(); iterator find(T); size_t size(); bool empty(); iterator begin(); iterator end(); iterator rbegin(); iterator rend(); void erase(T); void erase(iterator); private: struct btNode { T data; btNode* left; btNode* right; btNode* parent; }; btNode* root = NULL; size_t sSize, nSize; Comparator comp; bool insertOK; btNode* rightRotate(btNode**); btNode* leftRotate(btNode**); btNode* getMinimum(btNode*); btNode* getMaximum(btNode*); btNode* itemInsert(T, btNode*, btNode**); btNode* postInsert(T, btNode*); btNode* findNode(T, btNode*); btNode* deleteNode(btNode*); void deleteTree(btNode*); static bool defComp(T*, T*); // static so a pointer to it matches Comparator spec size_t btMax(size_t, size_t); int16_t btHeight(btNode*); }; template<typename T> class Set<T>::iterator { public: iterator(typename Set<T>::btNode* pos, bool forward) { this->pos = pos; this->forward = forward; } typename Set<T>::btNode* getPos() { return pos; } T operator*() const { return pos->data; } iterator &operator++() { if (forward) { increment(); } else { decrement(); } return *this; } iterator &operator++(int) { if (forward) { increment(); } else { decrement(); } return *this; } iterator &operator--() { if (forward) { decrement; } else { increment; } return *this; } iterator &operator--(int) { if (forward) { decrement; } else { increment; } return *this; } bool operator!=(const iterator a) { return (this->pos != (a.pos)); }; typename Set<T>::btNode* pos; private: bool forward; void increment(); void decrement(); }; template<typename T> Set<T>::Set() { sSize = 0; nSize = sizeof(btNode); comp = &Set<T>::defComp; // T has a < operator } template<typename T> Set<T>::Set(Comparator c) { sSize = 0; nSize = sizeof(btNode); comp = c; // use the supplied < comparitor } template<typename T> Set<T>::~Set() { deleteTree(root); } //public methods template<typename T> void Set<T>::clear() { deleteTree(root); root = NULL; } template<typename T> size_t Set<T>::size() { return sSize; } template<typename T> bool Set<T>::empty() { return (sSize == 0); } template<typename T> pair<typename Set<T>::iterator, bool> Set<T>::insert(T t) { insertOK = false; btNode *n = NULL; root = itemInsert(t, root, &n); if (insertOK) { sSize++; } iterator it(n, true); pair<typename Set<T>::iterator, bool> p(it, insertOK); return p; // build a pair out of iterator and insertOK } template<typename T> typename Set<T>::iterator Set<T>::find(T value) { btNode* n = findNode(value, root); iterator it(n, true); return it; } template<typename T> typename Set<T>::iterator Set<T>::begin() { btNode* is = NULL; if (root) { is = getMinimum(root); } iterator it(is, true); return it; } template<typename T> typename Set<T>::iterator Set<T>::end() { iterator it(NULL, true); return it; } template<typename T> typename Set<T>::iterator Set<T>::rbegin() { btNode* is = NULL; if (root) { is = getMaximum(root); } iterator it(is, false); return it; } template<typename T> typename Set<T>::iterator Set<T>::rend() { iterator it(NULL, false); return it; } template<typename T> void Set<T>::erase(T data) { btNode* f = findNode(data, root); if (f) { deleteNode(f); int a = 1; } } template<typename T> void Set<T>::erase(typename Set<T>::iterator it) { btNode* pos = it.getPos(); if (pos) { deleteNode(pos); } } //private methods template<typename T> typename Set<T>::btNode* Set<T>::itemInsert(T data, btNode* leaf, btNode** node) { if (leaf == NULL) { leaf = (btNode*)malloc(nSize); if (leaf == NULL) { return NULL; } leaf->data = data; leaf->parent = leaf->left = leaf->right = NULL; insertOK = true; // but we might yet need to balance the tree *node = leaf; return postInsert(data, leaf); } else { if (!comp(&data, &(leaf)->data) && !comp(&(leaf)->data, &data)) { // but we do not insert duplicates *node = leaf; // for the iterator return leaf; } if (comp(&data, &(leaf)->data)) { leaf->left = itemInsert(data, leaf->left, node); leaf->left->parent = leaf; return leaf; } else { leaf->right = itemInsert(data, leaf->right, node); leaf->right->parent = leaf; return leaf; } } } template<typename T> typename Set<T>::btNode* Set<T>::postInsert(T data, btNode* leaf) { int16_t diff = btHeight((leaf)->left) - btHeight((leaf)->right); if (diff > 1) { //left branch is too hight compared to right branch if(comp(&data, &leaf->left->data)) { return rightRotate(&leaf); } else if (comp(&leaf->left->data, &data)) { leaf->left = leftRotate(&((leaf)->left)); return rightRotate(&leaf); } } if (diff < -1) { //right branch is too high compared to left branch if (comp(&leaf->right->data, &data)) { return leftRotate(&leaf); } else if (comp(&data, &leaf->right->data)) { (leaf)->right = rightRotate(&(leaf)->right); return leftRotate(&leaf); } } return leaf; } template<typename T> typename Set<T>::btNode* Set<T>::rightRotate(btNode** root) { btNode *oldRight, *oldRightLeft; oldRight = (*root)->right; oldRightLeft = oldRight->left; oldRight->left = *root; oldRight->left->right = oldRightLeft; // testing (*root)->parent = oldRight; oldRight->left->right->parent = oldRight->left; return oldRight; } template<typename T> typename Set<T>::btNode* Set<T>::leftRotate(btNode** root) { btNode *oldLeft, *oldLeftRight; oldLeft = (*root)->left; oldLeftRight = oldLeft->right; oldLeft->right = *root; (*root)->left = oldLeftRight; // testing (*root)->parent = oldLeft; (*root)->left->parent = *root; return oldLeft; } template<typename T> void Set<T>::deleteTree(btNode* leaf) { if (leaf) { deleteTree(leaf->left); deleteTree(leaf->right); free(leaf); } } template<typename T> bool Set<T>::defComp(T* a, T* b) { return *a < *b; } template<typename T> typename Set<T>::btNode* Set<T>::getMinimum(btNode* leaf) { btNode* temp = leaf; while (temp->left != NULL) { temp = temp->left; } return temp; } template<typename T> typename Set<T>::btNode* Set<T>::getMaximum(btNode* leaf) { btNode* temp = leaf; while (temp->right != NULL) { temp = temp->right; } return temp; } template<typename T> typename Set<T>::btNode* Set<T>::findNode(T data, btNode* leaf) { if (leaf) { if (!comp(&data, &(leaf)->data) && !comp(&(leaf)->data, &data)) { // remember only comparison operator we are certain to have is < return leaf; } if (comp(&data, &(leaf)->data)) { return findNode(data, leaf->left); } return findNode(data, leaf->right); } else { return NULL; } } template<typename T> size_t Set<T>::btMax(size_t a, size_t b) { return (a <= b) ? b : a; } template<typename T> int16_t Set<T>::btHeight(btNode* leaf) { if (leaf) { return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right)); } return 0; } template<typename T> typename Set<T>::btNode* Set<T>::deleteNode(btNode* leaf) { btNode* temp; if (leaf->left == NULL || leaf->right == NULL) { // one or both child nodes might be NULL temp = leaf->left ? leaf->left : leaf->right; if (temp == NULL) { // no children temp = leaf; if (leaf->parent) { if (leaf == leaf->parent->left) { leaf->parent->left = NULL; } else { leaf->parent->right = NULL; } } leaf = NULL; } else { // one child so copy child to this node leaf->data = temp->data; leaf->left = temp->left; leaf->right = temp->right; //leaf = *temp; } // free the node (or copied child) memory allocations free(temp); sSize--; } else { temp = getMinimum(leaf->right); // copy the lowest node on the right path to this node //leaf)->key = temp->key; leaf->data = temp->data; //leaf->left = temp->left; // NULL of course // and then zap that node instead deleteNode(temp); // leaf->right); } if (leaf == NULL) { return leaf; } int16_t diff = btHeight(leaf->left) - btHeight(leaf->right); if (diff > 1) { // get the height difference on the left path diff = btHeight(leaf->left->left) - btHeight(leaf->left->right); if (diff < 0) { leaf->left = leftRotate(&leaf->left); return rightRotate(&leaf); } else { return rightRotate(&leaf); } } if (diff < -1) { // calc the height difference on the right path diff = btHeight(leaf->right->left) - btHeight(leaf->right->right); if (diff <= 0) { return leftRotate(&leaf); } else { leaf->right = rightRotate(&leaf->right); return leftRotate(&leaf); } } return leaf; } // iterator increment and decrement template<typename T> void Set<T>::iterator::increment() { if (pos->right) { pos = pos->right; while (pos->left) { pos = pos->left; } } else { if (pos->parent) { btNode* parent = pos->parent; while (parent && (pos == parent->right)) { pos = parent; parent = pos->parent; } if (pos->right != parent) { pos = parent; } } else { pos = pos->right; // if no right branch } } } template<typename T> void Set<T>::iterator::decrement() { if (pos->left) { btNode* child = pos->left; while (child->right) { child = child->right; } pos = child; } else { if (pos->parent) { btNode* parent = pos->parent; while (parent && (pos == parent->left)) { pos = parent; parent = parent->parent; } pos = parent; } else { pos = pos->left; } } }


Set.cpp
#include "stdafx.h" #include <stdint.h> #include <stdlib.h> #include "Set.h" #include <iostream> //using namespace std; struct MyData { int valueC; int valueD; }; void test1(); void test2(); bool compMyData(MyData*, MyData*); int main() { test1(); //test2(); std::cin.get();     return 0; } void test1() { Set<int> set; int ints[] = { 2, 7, 4, 9, 5, 1, 8 }; for (int i = 0; i < 7; i++) { set.insert(ints[i]); // ignoring the return value } for (Set<int>::iterator it = set.begin(); it != set.end(); it++) { std::cout << *it << '\n'; } // pair<Set<int>::iterator, bool> p = set.insert(21); if (p.second) { std::cout << "Value 21 inserted\n"; // reading returned Pair } std::cout << "List in reverse\n"; for (Set<int>::iterator it = set.rbegin(); it != set.rend(); it++) { std::cout << *it << '\n'; } // trying find() Set<int>::iterator is = set.find(7); if (is != set.end()) { std::cout << "Found " << *is << '\n'; } // erase() by value std::cout << "Erasing 7\n"; set.erase(7); std::cout << "Now using the iterator to erase 4\n"; for (Set<int>::iterator it = set.begin(); it != set.end(); it++) { if (*it == 4) { set.erase(it); break; } } // list of final state for (Set<int>::iterator it = set.begin(); it != set.end(); it++) { std::cout << *it << '\n'; } } void test2() { Set<MyData> set(compMyData); MyData myData; for (int i = 0; i < 20; i++) { myData.valueC = rand() % 49; myData.valueD = rand() % 11; set.insert(myData); } for (Set<MyData>::iterator it = set.begin(); it != set.end(); it++) { std::cout << "valueC: " << (*it).valueC << " ValueD: " << (*it).valueD << '\n'; } } bool compMyData(MyData* a, MyData* b) { if (a->valueC < b->valueC) { return true; } if (b->valueC < a->valueC) { return false; } if (a->valueD < b->valueD) { return true; } return false; }


Set.ino
#include "Set.h" template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; } struct MyData { int valueC; int valueD; }; void setup() { Serial.begin(115200); test1(); } void test1(){ Set<int> set; int ints[] = { 2, 7, 4, 9, 5, 1, 8 }; for (int i = 0; i < 7; i++) {     set.insert(ints[i]); // ignoring the return value } Serial << "Size: " << set.size() << '\n'; for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {     Serial << *it << '\n'; } // pair<Set<int>::iterator, bool> p = set.insert(21); if (p.second) {     Serial << "Value 21 inserted\n"; // reading returned Pair } Serial << "List in reverse\n"; for (Set<int>::iterator it = set.rbegin(); it != set.rend(); it++) {     Serial << *it << '\n'; } // trying find() Set<int>::iterator is = set.find(7); if (is != set.end()) {     Serial << "Found " << *is << '\n'; } // erase() by value Serial << "Erasing 7\n"; set.erase(7); Serial << "Now using the iterator to erase 4\n"; for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {     if (*it == 4) {      set.erase(it);      break;     } } // list of final state for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {     Serial << *it << '\n'; } } void test2() { Set<MyData> set(compMyData); MyData myData; for (int i = 0; i < 20; i++) {     myData.valueC = rand() % 49;     myData.valueD = rand() % 11;     set.insert(myData); } for (Set<MyData>::iterator it = set.begin(); it != set.end(); it++) {     Serial << "valueC: " << (*it).valueC << " ValueD: " << (*it).valueD << '\n'; } } bool compMyData(struct MyData* a, struct MyData* b) { if (a->valueC < b->valueC) { return true; } if (b->valueC < a->valueC) { return false; } if (a->valueD < b->valueD) { return true; } return false; }


Read the chapter in my book C++ Data Structures with immediate download from Amazon