C++ Program to implement Map class
9 min readApr 12, 2022
Pre-requisite: Maps, AVL tree, method(when the function is a class member)/function overloading, operator[] overloading, overloading myth, return by reference, const qualifier.
Maps are associative containers that store elements in the form of key-value pairs. We are going to implement the Map class ourselves in C++ from scratch in which no duplicate keys are allowed.
It is going to contain the following functionalities -
- Insert in O ( log n )
- Update in O ( log n )
- Access in O ( log n )
It is impractical to have a delete operation on a Map(hope you have worked with C++ STL std::map). Maps are implemented in self-balancing search trees like the Red-Black tree, AVL tree, etc. We will implement it using the AVL tree.
There are three files -
- map. h — contains the Map class.
- test.cpp- demonstrates the use of a single object for read-write operation.
- test2.cpp — demonstrates the use of two objects, one for reading and another for a write operation(you may ignore this file).
Often we want to access elements that are present within the map(as in python dictionary). The only drawback in “test.CPP” is that it takes extra memory for a key iff a read operation is performed and the key is not found in the map. In this case, it creates the new key(even though it is a read operation) and returns 0. In all other cases, we are fine.
Nevertheless, this extra memory can be avoided on the user side as in “test2.cpp” by using a const reference to the object.
Note that “test.cpp” and “test2.cpp” have the same time complexity as well as space complexity for every operation.
Structure of Map class
Attributes -
- static class Map *root
- Map *left, *right, *par
- int first, second, depth
Implementation
// C++ Program to implement Map class(using AVL tree)
// This is a header file map.h and doesnot contain main()
#include <iostream>
using namespace std;
class Map {
// 1. this methods are not useful to users, therefore
// they are kept hidden
private:
// 2. the const property is used to keep the "search"
// method
// compatible with the method "const int&[]operator(int)
// const"
// 3. since we are not allowed to change the class
// attributes in the method "const int&[]operator(int)
// const" we have to assure the compiler that method
// called(i.e "search") inside it also doesn't change
// the attributes of the class
const int search(int first) const
{
// 4. a temporary variable created so that we do not
// loose the "root" of the tree
Map* temp = root;
// 5. stop only when either the key is found or we
// have gone further the leaf node
while (temp != nullptr && temp->first != first) {
// 6. go to left if key is less than the key of
// the traversed node
if (first < temp->first) {
temp = temp->left;
}
// 7. go to right if key is greater than the key
// of the traversed node
else {
temp = temp->right;
}
}
// 8. if key is found
if (temp != nullptr) {
// 9. if the key is found return the value
return temp->second;
}
// 10. if key is not found
return 0;
}
// 11. a utiliity function to return the Map* object
// with its members initilized to default values except
// the key
Map* create(int first)
{
Map* newnode = (Map*)malloc(sizeof(Map));
newnode->first = first;
newnode->second = 0;
newnode->left = nullptr;
newnode->right = nullptr;
newnode->par = nullptr;
// 12. depth of a newnode shall be 1 and not zero to
// differentiate between no child (which return
// nullptr) and having child(which return 1)
newnode->depth = 1;
return newnode;
}
// 13. all the rotation operation are performed about
// the node itself
// 14. performs all the linking done when there is
// clockwise rotation performed at node "x"
void right_rotation(Map* x)
{
Map* y = x->left;
x->left = y->right;
if (y->right != nullptr) {
y->right->par = x;
}
if (x->par != nullptr && x->par->right == x) {
x->par->right = y;
}
else if (x->par != nullptr && x->par->left == x) {
x->par->left = y;
}
y->par = x->par;
y->right = x;
x->par = y;
}
// 15. performs all the linking done when there is
// anti-clockwise rotation performed at node "x"
void left_rotation(Map* x)
{
Map* y = x->right;
x->right = y->left;
if (y->left != nullptr) {
y->left->par = x;
}
if (x->par != nullptr && x->par->left == x) {
x->par->left = y;
}
else if (x->par != nullptr && x->par->right == x) {
x->par->right = y;
}
y->par = x->par;
y->left = x;
x->par = y;
}
// 16. draw the initial and final graph of each
// case(take case where every node has two child) and
// update the nodes depth before any rotation
void helper(Map* node)
{
// 17. if left skewed
if (depthf(node->left) - depthf(node->right) > 1) {
// 18. if "depth" of left subtree of left child
// of "node" is greater than that of right
// subtree of left child of "node"
if (depthf(node->left->left)
> depthf(node->left->right)) {
node->depth = max(depthf(node->right) + 1,
depthf(node->left->right) + 1);
node->left->depth = max(depthf(node->left->left)
+ 1,depthf(node) + 1);
right_rotation(node);
}
// 19. if "depth" of right subtree of left child
// of "node" is greater than that of left
// subtree of left child of "node"
else {
node->left->depth = max(
depthf(node->left->left) + 1,
depthf(node->left->right->left) + 1);
node->depth = max(
depthf(node->right) + 1,
depthf(node->left->right->right) + 1);
node->left->right->depth
= max(depthf(node) + 1,
depthf(node->left) + 1);
left_rotation(node->left);
right_rotation(node);
}
}
// 20. if right skewed
else if (depthf(node->left) - depthf(node->right)
< -1) {
// 21. if "depth" of right subtree of right
// child of "node" is greater than that of left
// subtree of right child of "node"
if (depthf(node->right->right)
> depthf(node->right->left)) {
node->depth
= max(depthf(node->left) + 1,
depthf(node->right->left) + 1);
node->right->depth
= max(depthf(node->right->right) + 1,
depthf(node) + 1);
left_rotation(node);
}
// 22. if "depth" of left subtree of right child
// of "node" is greater than that of right
// subtree of right child of "node"
else {
node->right->depth = max(
depthf(node->right->right) + 1,
depthf(node->right->left->right) + 1);
node->depth = max(
depthf(node->left) + 1,
depthf(node->right->left->left) + 1);
node->right->left->depth
= max(depthf(node) + 1,
depthf(node->right) + 1);
right_rotation(node->right);
left_rotation(node);
}
}
}
// 23. balancing the tree about the "node"
void balance(Map* node)
{
while (node != root) {
int d = node->depth;
node = node->par;
if (node->depth < d + 1) {
node->depth = d + 1;
}
if (node == root
&& depthf(node->left) - depthf(node->right)
> 1) {
if (depthf(node->left->left)
> depthf(node->left->right)) {
root = node->left;
}
else {
root = node->left->right;
}
helper(node);
break;
}
else if (node == root
&& depthf(node->left)
- depthf(node->right)
< -1) {
if (depthf(node->right->right)
> depthf(node->right->left)) {
root = node->right;
}
else {
root = node->right->left;
}
helper(node);
break;
}
helper(node);
}
}
// 24. utility method to return the "depth" of the
// subtree at the "node"
int depthf(Map* node)
{
if (node == nullptr)
// 25. if it is null node
return 0;
return node->depth;
}
Map* insert(int first)
{
Map* newnode = create(first);
// 26. if empty tree simply create the "root"
if (root == nullptr) {
root = newnode;
return root;
}
Map *temp = root, *prev = nullptr;
while (temp != nullptr) {
prev = temp;
if (first < temp->first) {
temp = temp->left;
}
else if (first > temp->first) {
temp = temp->right;
}
else {
free(newnode);
// 27. if the key is found then it is
// returned by reference so that it is
// updatable
return temp;
}
}
if (first < prev->first) {
prev->left = newnode;
}
else {
prev->right = newnode;
}
newnode->par = prev;
// 28. once we have inserted we need to check and
// balance the tree at every node which is present
// in the path from "newnode" to "root"
balance(newnode);
// 29. new object is inserted and returned by
// reference to initialize in the main by
// assignment(hashing)
return newnode;
}
public:
// 30. "root" is kept static because it is a class
// property and not an instance property
// 31. if the "root" is not static we will take double
// memory for the programme than required
// static "root" is initialized to nullptr outside the
// class
static class Map* root;
// 32. "first" is key and "second" is value
Map *left, *right, *par;
int first, second, depth;
// 33. overloaded [] operator for assignment(hashing) or
// inserting a key-value pairs in the map since it might
// change the members of the class therefore this is
// invoked when any assignment is done
int& operator[](int key) { return insert(key)->second; }
// 34. Since we have two methods with the same name
// "[]operator(int)" and methods/functions cannot be
// distinguished by their return types it is mandatory
// to include a const qualifier at the end of any of the
// methods
// 35. compiler will call this by default when we are
// interested in only peeking the value
// 36. it will not be called for assignment because
// it doesn't allow change member variables
// 37. we cannot make it return by reference because the
// variable "temp" returned by the "search" method is
// statically allocated and therefore it's been
// destroyed when it is called out(stack frame is popped
// out)
const int operator[](int key) const
{
// 38. search method is also qualified with const
return search(key);
}
};
Map* Map::root = nullptr;Demonstration 1
// test.cpp
// without using constant reference
// to the object of class Map
#include "map.h"
#include <iostream>
using namespace std;
int main()
{
// here "map" is used for both
// read-write operation
Map map;
// insertion
map[132] = 3;
map[34] = 5;
map[42] = 7;
map[-83] = 4;
map[66] = 9;
map[197] = 8;
map[-2] = -88;
// updation
map[42] = 55;
int arr[] = { 132, -34, 34, 42,
-83, 60, 66, 197,
-2, 56, 1, -3442 };
cout << "key: value\n";
for (int i = 0; i < sizeof(arr) /
sizeof(int); i++) {
// accessing value from its
// respective key
// when we are searching for the
// key and if it is not found then
//a new key is created with value 0
// and then 0 is returned
// if its found then its value is
//simply returned
cout << '(' << arr[i] << ":"
<< map[arr[i]] << ") , ";
}
cout << endl;
return 0;
}Output -
key: value
(132:3) , (-34:0) , (34:5) , (42:55) , (-83:4) , (60:0) , (66:9) , (197:8) , (-2:-88) , (56:0) , (1:0) , (-3442:0) ,
For Demonstration 1, the AVL tree for keys looks like the one shown below -
Demonstration 2
// test2.cpp
// using constant reference to the object
//for searching
#include "map.h"
#include <iostream>
using namespace std;
int main()
{
// we will use "write" for write operation
Map write;
// creating a const reference to the object
// "write".
// "read" will be used for read-only operation.
const Map& read = write;
// insertion
write[132] = 3;
write[34] = 5;
write[42] = 7;
write[-83] = 4;
write[66] = 9;
write[197] = 8;
write[-2] = -88;
// updating
write[42] = 55;
int arr[] = { 132, -34, 34, 42, -83, 60,
66, 197, -2, 56, 1, -3442 };
cout << "key: value\n";
for (int i = 0; i < sizeof(arr) / sizeof(int);
i++) {
// accessing value from its respective key
// when we are searching for the key and if
//it is not found then a new key is not
//created instead 0 is returned without any
// affect on the map
// if its found then its value is simply
//returned
cout << '(' << arr[i] << ":" << read[arr[i]]
<< "), ";
}
cout << endl;
return 0;
}Output -
key: value
(132:3) , (-34:0) , (34:5) , (42:55) , (-83:4) , (60:0) , (66:9) , (197:8) , (-2:-88) , (56:0) , (1:0) , (-3442:0) ,
For Demonstration 2, the AVL tree for keys looks like the one shown below -
Note that both demonstrations behave same at user level.
