Functions/Operations To Be Implemented Using Custom Map

Structure of Map class:

Creation of Custom Map Header

We will cover the following functionalities and methods in our map:

insert()

find()

update()

accessing any key

erase()

count()

size()

empty()

clear()

iterate the map

The methods and functionalities are discussed below:

1. insert():

This method is used to insert a key-value pair in the map. There are two insert() methods used here.

One is made public and it takes two parameters:

first – It is the key
second – It is the respective value of the key

Syntax:

map.insert(first, second);

Below is the implementation of this method

C++

void insert(int first, int second)
{
    Map* temp = iterator(first);
 
    // If element doesnot exist already
    if (temp == nullptr)
        insert(first)->second = second;
     
    // If element exists already update it
    else
        temp->second = second;
}

Time Complexity: O(logN) where N is the size of map

The other one is made private. This method is called inside the operator overloading function of [].

It takes only one parameter: first (It is the key).
Creates the new node with “first” as the key and returns the instance of the node.

Syntax:

map[first] = second;

Below is the implementation of this method:

C++

Map* insert(int first)
{
    // Increase the number of elements
    cnt++;
    Map* newnode = create(first);
 
    // 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);
 
            // If element already exists
            // decrease the count
            cnt--;
 
            // 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;
 
    // Once inserted Check and balance the tree
    // at every node in path from "newnode" to "root"
    balance(newnode);
 
    // New object is inserted and returned to
    // initialize in the main during assignment
    return newnode;
}
 
int& operator[](int key) {
    return insert(key)->second;
}

Time Complexity: O(logN) where N is the size of the map

2. find():

It is used to find an element. This is a public method. It takes one parameter: first (which is the key) and returns the reference associated with the key. Internally it calls the private method iterator() to find the key

Syntax:

map.find(first);

Below is the implementation of the method

C++

Map* iterator(int first)
{
    Map* temp = root;
    while (temp != nullptr && temp->first != first) {
        if (first < temp->first) {
            temp = temp->left;
        }
        else {
            temp = temp->right;
        }
    }
    return temp;
}
 
Map* find(int first) { 
    return iterator(first); 
}

Time Complexity: O(logN) where N is the size of the map.

3. update():

This value is used to update the value associated with a key. This is a public method. It takes two parameters:

first: It is the key to be found.
second: It is the new value of the key.

The function calls the iterator() function to get the instance of the key and updates the value associated to that key. If no such key exists then no operation is performed.

Syntax:

map.update(first, second);

Below is the implementation of the method.

C++

void update(int first, int second)
{
    Map* temp = iterator(first);
    if (temp != nullptr) {
        temp->second = second;
    }
}

Time Complexity: O(logN) where N is the size of the map

4. Accessing any key:

Any value can be accessed using the subscript operator[]. The concept of method overloading is used to implement the functionality. It is a public method and the search() function is called inside the overloading function. It takes one parameter: first (it is the value of the key)

Syntax:

map[first];

Below is the implementation of the method.

C++

const Map* iterator(int first) const
{
    Map* temp = root;
    while (temp != nullptr 
           && temp->first != first) {
        if (first < temp->first) 
            temp = temp->left;
        else
            temp = temp->right;
    }
    return temp;
}
 
const int search(int first) const
{
    const Map* temp = iterator(first);
 
    // If element exists with the given key
    // return its value
    if (temp != nullptr)
        return temp->second;
 
    // If element doesn't exist
    // return default value of 0
    return 0;
}
 
const int operator[](int key) const
{
    // Search method is also qualified with const
    return search(key);
}

Time Complexity: O(logN) where N is the size of the map.

5. erase():

It deletes the node with the given key and replaces it with either its in-order predecessor or in-order successor. It is a public method. It takes one parameter: first (it is the key whose value needs to be deleted). At the end of the function, it calls balance() method on the parent of that node which replaced the deleted node to balance the AVL tree.

Syntax:

map.erase(first);

Below is the implementation of the method.

C++

void erase(int first, Map* temp = root)
{
    Map* prev = 0;
    cnt--;
    while (temp != 0 && temp->first != first) {
        prev = temp;
        if (first < temp->first) {
            temp = temp->left;
        }
        else if (first > temp->first) {
            temp = temp->right;
        }
    }
    if (temp == nullptr) {
        cnt++;
        return;
    }
    if (cnt == 0 && temp == root) {
        free(temp);
        root = nullptr;
        return;
    }
    Map* l = inorderPredecessor(temp->left);
    Map* r = inorderSuccessor(temp->right);
    if (l == 0 && r == 0) {
        if (prev == 0) {
            root = 0;
        }
        else {
            if (prev->left == temp) {
                prev->left = 0;
            }
            else {
                prev->right = 0;
            }
            free(temp);
            balance(prev);
        }
        return;
    }
 
    Map* start;
    if (l != 0) {
        if (l == temp->left) {
            l->right = temp->right;
            if (l->right != 0) {
                l->right->par = l;
            }
            start = l;
        }
        else {
            if (l->left != 0) {
                l->left->par = l->par;
            }
            start = l->par;
            l->par->right = l->left;
            l->right = temp->right;
            l->par = 0;
            if (l->right != 0) {
                l->right->par = l;
            }
            l->left = temp->left;
            temp->left->par = l;
        }
        if (prev == 0) {
            root = l;
        }
        else {
            if (prev->left == temp) {
                prev->left = l;
                l->par = prev;
            }
            else {
                prev->right = l;
                l->par = prev;
            }
            free(temp);
        }
        balance(start);
        return;
    }
    else {
        if (r == temp->right) {
            r->left = temp->left;
            if (r->left != 0) {
                r->left->par = r;
            }
            start = r;
        }
        else {
            if (r->right != 0) {
                r->right->par = r->par;
            }
            start = r->par;
            r->par->left = r->right;
            r->left = temp->left;
            r->par = 0;
            if (r->left != 0) {
                r->left->par = r;
            }
            r->right = temp->right;
            temp->right->par = r;
        }
        if (prev == 0) {
            root = r;
        }
        else {
            if (prev->right == temp) {
                prev->right = r;
                r->par = prev;
            }
            else {
                prev->left = r;
                r->par = prev;
            }
            free(temp);
        }
        balance(start);
        return;
    }
}

Time Complexity: O(logN) where N is the size of the map.

6. count():

This method returns the count of a key in the map. This is a public method. It takes one parameter: first(which is the key of value whose count should be found). This method calls the iterator() method internally and if no node is found then count is 0. Otherwise, count returns 1.

Syntax:

map.count(first);

Below is the implementation of the method.

C++

int count(int first)
{
    Map* temp = iterator(first);
 
    // If key is found
    if (temp != nullptr)
        return 1;
 
    // If key is not found
    return 0;
}

Time Complexity: O(logN) where N is the size of the map.

7. size():

This method returns the size of the map. This is a public method. This method does not take any parameter.

Syntax:

map.size();

Below is the implementation of the method.

C++

int size(void) { 
    return cnt; 
}

Time Complexity: O(1)

8. empty():

This method checks if the map is empty or not. This is a public method. It returns true if the map is empty, else false. This method does not take any parameter.

Syntax:

map.empty();

Below is the implementation of the method.

C++

bool empty(void)
{
    if (root == 0)
        return true;
    return false;
}

Time Complexity: O(1)

9. clear():

This method is used to delete the whole map in. This is a public method. It does not take any parameter. It takes the erase() method internally.

Syntax:

map.clear();

Below is the implementation of the method.

C++

void clear(void)
{
    while (root != nullptr) {
        erase(root->first);
    }
}

Time Complexity: O(N * logN) where N is the size of the map

10. iterate():

This method is used to traverse the whole map. This is a public method. It also does not take any parameter. The nodes are printed in the sorted manner of key.

Syntax:

map.iterate();

Below is the implementation of the method.

C++

void iterate(Map* head = root)
{
    if (root == 0)
        return;
    if (head->left != 0) {
        iterate(head->left);
    }
   
    cout << head->first << ' ';
   
    if (head->right != 0) {
        iterate(head->right);
    }
}

Time Complexity: O(N) where N is the size of the map

Build a custom Map using Header file in C++

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values. Maps are implemented by self-balancing search trees. In C++ STL it uses Red-Black Tree.

Here we are going to implement a custom Map class which has an integer value as the key and the value stored corresponding to any key is also of integer type.

We will implement it using the AVL tree. To implement the map, we will first create a header file which will incorporate the functionalities of a map class. Below is the basic structure of the Map class:

Tags:

#Data Structures #DSA #Data Structures

Structure of Map class:

Creation of Custom Map Header

Functions/Operations To Be Implemented Using Custom Map

1. insert():

C++

C++

2. find():

C++

3. update():

C++

4. Accessing any key:

C++

5. erase():

C++

6. count():

C++

7. size():

C++

8. empty():

C++

9. clear():

C++

10. iterate():

C++

Build a custom Map using Header file in C++

Similar Reads

Contact Us