Posted Updated 4 minutes read (About 654 words)

Crafting a Singleton Class in C++: A Tale of Singular Elegance

Ahoy, fellow coders! Today, let’s embark on a thrilling journey into the realm of singleton classes in C++. If you’re not familiar with the term, fear not! A singleton class is like that one legendary sword in a game—you can only wield one of its kind at a time. In other words, it ensures there’s only ever one instance of a class floating around in your code.

The Singleton Quest Begins…

Picture this: you’re building a mighty castle of code, and you stumble upon a need for a class that must exist in a single, glorious instance. That’s where the singleton pattern comes into play!

Step 1: Raise the Drawbridge with a Private Constructor

In the land of singletons, the first rule is simple yet crucial: make the constructor private! This prevents any mischievous outsider from creating instances of your class willy-nilly.

1
2
3
4
5
class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
    // Additional implementation goes here...
};

Method 1: Meyers’ Singleton - The Heroic Approach

Now, let’s dive into the magical realm of static member functions. Behold, the power of static! With this enchanting keyword, we can summon a single instance of our class.

1
2
3
4
5
6
7
8
9
class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
public:
    static Singleton& getInstance() {
        static Singleton instance;
        return instance;
    }
};

Here’s how it works: whenever you call getInstance(), it conjures up a static instance if one doesn’t already exist. Otherwise, it simply returns the existing instance, ensuring there’s only one to rule them all! Meyers’ Singleton leverages the mystical properties of static local variables, ensuring that the instance is forged with utmost care and thread safety.

Method 2: The Static Pointer to Glory

But wait, our adventure isn’t over yet! There’s one more method to explore: the static pointer approach. Brace yourselves as we delve deeper into the arcane arts of C++!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
    static Singleton* instancePtr;  // Static pointer to the instance

public:
    static Singleton* getInstance() {
        if (!instancePtr) {
            instancePtr = new Singleton();
        }
        return instancePtr;
    }
};

Singleton* Singleton::instancePtr = nullptr;  // Initializing the static pointer

This method employs a static pointer to the singleton instance, ensuring lazy initialization and a journey free of unnecessary overhead.

Final Step : Complete Code

Copy the below code in a .cpp file and compile the code below using

g++ -s ./c++/cpp_codes/singleton.cpp -o singleton.out

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<bits/stdc++.h>

using namespace std;

class Singleton {
private:
    Singleton() {}  // Private constructor to prevent instantiation
public:
    static Singleton& getInstance() {
        static Singleton instance;
        return instance;
    }
    void print(){
        cout << "hello world" << endl;
    }
};



int main(){
    Singleton obj = Singleton::getInstance();
    obj.print();
    return 0;
}

Special Keyword and

In C++, the static keyword has special significance when applied to member variables and functions:

  • Static Member Variables: When a member variable is declared as static, it means there is only one instance of that variable shared among all instances of the class.
  • Static Member Functions: A static member function is a function that belongs to the class rather than instances of the class. It can be called without an object of the class.

Steps to Implement a Singleton Class:

  • Private Constructor: Ensure that the class has a private constructor to prevent external instantiation.
  • Static Member Function/Object: Provide a static member function or object that returns a reference to the singleton instance.
  • Lazy Initialization: The singleton instance should be created on-demand to conserve resources.
  • Thread Safety (Optional): If the singleton will be accessed by multiple threads, ensure thread safety during initialization. Meyers’ Singleton automatically handles thread safety.

Epilogue: The Singleton Legacy Lives On

And there you have it, intrepid adventurers! By mastering the arcane arts of singleton classes, you’ve unlocked the secrets of controlling class instantiation like a true coding wizard. Whether you choose the static sorcery, the mystical member object, Meyers’ elegance, or the static pointer to glory, remember to wield your singleton powers responsibly in your coding quests!

Posted Updated 4 minutes read (About 644 words)

Morris Traversal in C++

Morris Traversal is a method for traversing binary trees without using any extra space for storing information about nodes. It allows for the traversal of a binary tree in Inorder, Preorder, and Postorder without recursion or using a stack.

Introduction

Morris Traversal is an elegant and efficient algorithm for traversing binary trees. It was introduced by J. H. Morris in 1979. The key idea behind Morris Traversal is to modify the tree as we traverse it so that we can navigate through the nodes without using any additional space for a stack or recursion. This method helps to reduce the space complexity of tree traversal algorithms.

Pseudo Code

The general idea behind Morris Traversal is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. Initialize current as root
2. While current is not NULL
    a. If current does not have a left child
        i. Print current's data
        ii. Move to the right child (current = current->right)
    b. Else
        i. Find the inorder predecessor of current (say it's the rightmost node in current's left subtree, and cannot be current node)
        ii. If the right child of the predecessor is NULL
            1. Set the right child of the predecessor to current (Creating temp links)
            2. Move current to its left child (current = current->left)
        iii. Else
            1. Set the right child of the predecessor back to NULL (Removing temp links)
            2. Print current's data
            3. Move current to its right child (current = current->right)

Inorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void morrisInorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                std::cout << current->data << " ";
                current = current->right;
            }
        }
    }
}

Preorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void morrisPreorderTraversal(Node* root) {
    Node* current = root;
    while (current != nullptr) {
        if (current->left == nullptr) {
            std::cout << current->data << " ";
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                std::cout << current->data << " ";
                predecessor->right = current;
                current = current->left;
            } else {
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Postorder Traversal using Morris Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void reverseNodes(Node* start, Node* end) {
    if (start == end) return;
    Node* x = start;
    Node* y = start->right;
    Node* z;
    while (x != end) {
        z = y->right;
        y->right = x;
        x = y;
        y = z;
    }
}

void printReverse(Node* start, Node* end) {
    reverseNodes(start, end);
    Node* current = end;
    while (true) {
        std::cout << current->data << " ";
        if (current == start) break;
        current = current->right;
    }
    reverseNodes(end, start);
}

void morrisPostorderTraversal(Node* root) {
    Node dummy;
    dummy.left = root;
    dummy.right = nullptr;
    Node* current = &dummy;
    while (current != nullptr) {
        if (current->left == nullptr) {
            current = current->right;
        } else {
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == nullptr) {
                predecessor->right = current;
                current = current->left;
            } else {
                printReverse(current->left, predecessor);
                predecessor->right = nullptr;
                current = current->right;
            }
        }
    }
}

Main Driver Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Function prototypes
void morrisInorderTraversal(Node* root);
void morrisPreorderTraversal(Node* root);
void morrisPostorderTraversal(Node* root);

int main() {
    // Constructing a sample binary tree
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Inorder traversal: ";
    morrisInorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Preorder traversal: ";
    morrisPreorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Postorder traversal: ";
    morrisPostorderTraversal(root);
    std::cout << std::endl;

    // Deallocate memory
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

This main driver code constructs a binary tree, then applies each of the Morris Traversal methods (inorder, preorder, postorder) to print the traversals. Finally, it deallocates the memory allocated for the tree nodes.

Practice

Follow

Links

Categories

Recents

Archives

Tags

Bangalore1
C++2
CORE2
CSE1
Caffe21
ComputerScience2
Gradio1
HuggingFace1
IIT Bombay1
India1
Interview2
Machine Learning1
NLP1
ONNX4
Preparation2
PyTorch1
Qualcomm1
Research2
Senior Engineer1
Technical9
Tensorflow1
Uttarakhand1
×