Cover Image for Implementing the sets without C++ STL containers
80 views

Implementing the sets without C++ STL containers

If you want to implement sets (collections of unique elements) without using C++ STL containers like std::set or std::unordered_set, you can create your own set data structure from scratch. Here, I’ll provide a simple example of how to implement a basic set using an array in C++. Keep in mind that this is a simplified implementation and doesn’t have the same level of functionality and performance as the STL containers.

C++
#include <iostream>

class CustomSet {
private:
    int* elements; // Dynamic array to store elements
    int capacity;  // Maximum capacity of the set
    int size;      // Current size of the set

public:
    CustomSet(int capacity) {
        this->capacity = capacity;
        this->size = 0;
        this->elements = new int[capacity];
    }

    ~CustomSet() {
        delete[] elements;
    }

    bool contains(int element) {
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) {
                return true;
            }
        }
        return false;
    }

    bool insert(int element) {
        if (contains(element)) {
            return false; // Element already exists in the set
        }

        if (size >= capacity) {
            // Resize the array (this is a simplified approach)
            int newCapacity = capacity * 2;
            int* newElements = new int[newCapacity];
            for (int i = 0; i < size; i++) {
                newElements[i] = elements[i];
            }
            delete[] elements;
            elements = newElements;
            capacity = newCapacity;
        }

        elements[size++] = element;
        return true;
    }

    bool remove(int element) {
        int index = -1;
        for (int i = 0; i < size; i++) {
            if (elements[i] == element) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            return false; // Element not found in the set
        }

        // Replace the element to remove with the last element
        elements[index] = elements[size - 1];
        size--;
        return true;
    }

    void print() {
        std::cout << "CustomSet: ";
        for (int i = 0; i < size; i++) {
            std::cout << elements[i] << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    CustomSet set(5);

    set.insert(3);
    set.insert(1);
    set.insert(5);
    set.insert(3); // This won't be inserted again since it's a set
    set.insert(2);

    set.print(); // Print the set

    set.remove(1);
    set.remove(4); // Element not found, nothing happens

    set.print(); // Print the modified set

    return 0;
}

In this code, we define a CustomSet class that uses a dynamic array to store elements. The contains, insert, and remove methods provide basic set operations. The insert method also resizes the array if the capacity is exceeded. This is a very simplified example, and a production-ready set implementation would need to handle more edge cases and provide better performance.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS