Associative Containers std::set in C++

Associative Containers

Associative Containers are a category of STL containers that organize elements based on some sort of key rather than their position in the container. The key-value pair structure allows for fast and efficient retrieval elements. In C++ STL, the key can be of any comparable type, and the elements are usually sorted based on this key.

Common Types of Associative Containers:

std::set:

Implements a sorted set of unique keys.
Elements are stored in sorted order.
Supports fast search, insertion, and deletion operations.

#include <set>
std::set<int> mySet = {3, 1, 4, 1, 5, 9, 2};

std::map

Represents a sorted collection of key-value pairs.
Each key is unique, and the elements are sorted based on the keys.
Ideal for scenarios where a mapping between keys and values is required.

#include <map>
std::map<std::string, int> myMap = {{"apple", 5}, {"banana", 3}, {"orange", 7}};

std::multiset and std::multimap

Similar to std::set and std::map, respectively, but allows duplicate keys.
Elements are sorted based on keys.

#include <set>
#include <map>
std::multiset<int> myMultiSet = {3, 1, 4, 1, 5, 9, 2};
std::multimap<std::string, int> myMultiMap = {{"apple", 5}, {"banana", 3}, {"apple", 7}};

Advantages

Efficient search operations: Associative containers provide search operations with logarithmic complexity, making them ideal for scenarios where frequent data retrieval is required.
Ordered Storage: For ordered sets and maps, elements are automatically based on their keys. This feature is beneficial when iteration in a specific order is necessary.
Key-Value Mapping: The key-value pair structure in associative containers is particularly useful when establishing relationship between different types of data.
Custom Key Comparisons: Users can provide custom comparison functions or use the default comparison operators for sorting elements based on keys.

Anatomy of std::set Associative Container

It is designed to store unique elements in sorted order, offering fast, and efficient operations for search, insertion, and deletion.

Sets are the containers for storing elements in a given order. The elements of a set must be unique. The value can identify each element in a set, i.e., they act as a keys themselves. We can insert elements in or remove elements from a set in C++ but cannot modify them since the values become constant once stored in the set.

The operations allowed to be performed on sets are insertion and deletion.

The internal implementation of sets is done with the use of Binary Search Tree (BST).

Basics of std::set

Declaration and Initializations:

#include <set>
std::set<int> mySet; // Declare an empty set of integers, mySet = {}

std::set<int, greater<int>> mySet2; // Empty Set - Decreasing order, mySet2 = {}

std::set<int> mySet3 = {10, 6, 5, 9, 11}; // Defining a set with values, mySet3 = {5, 6, 9, 10, 11}

std::set<int> mySet4(mySet3); // Initializing set using other set, mySet4 = {5, 6, 9, 10, 11}

int arr[] = {10, 4, 6, 5, 11};
std::set<int> mySet5(arr, arr+5); // since the array has five elements, thus arr+5

Inserting Elements:

mySet.insert(42);    // Insert a single element
mySet.insert({1, 2, 3}); // Insert multiple elements

Iterating through elements:

for (const auto& element : mySet) {
    // Access each element
}

By default, the set stores the elements in ascending order, but if you want the elements to be sorted in descending order, you will need to write greater<datatype> along with the data type:

set<data-type, greater<data-type>> name_of_set;

Underlying Mechanisms

Uniqueness:

std::set only stores unique elements. Duplicate elements are automatically rejected during insertion.

Sorting:

Elements are stored in sorted order based on their values, allowing for efficient search operations.

Immutable:

You cannot change the values once they are stored in a set. Hence, insertion and deletion are allowed, but you cannot update or modify the existing elements of the set.

Red-Black Tree Implementation:

Internally, std::set is typically implemented as a Red-Black Tree.
This balanced binary search tree ensures that the height of the tree remains logarithmic, leading to efficient search, insertion, and deletion operations with a time complexity of O(log n).

Functions

1. Insertion and Initialization:

insert():

The insert() function is used to insert elements into the set. It ensures uniqueness and maintains the sorted order of the set.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // Inserting single elements
    mySet.insert(42);
    mySet.insert(21);

    // Inserting multiple elements using an initializer list
    mySet.insert({10, 30, 50, 10});

    // Displaying elements
    for (const auto& element : mySet) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
10 21 30 42 50

2. Search and Retrieval:

find():

The find() function is used to search for a specific element in the set. It returns an iterator pointing to the element if found; otherwise, it returns end().

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};

    auto it = mySet.find(30);

    if (it != mySet.end()) {
        std::cout << "Element found: " << *it << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }
    
    
auto it2 = mySet.find(7);
    
if (it2 != mySet.end()) {
    
	std::cout << "Element found: " << *it
 << std::endl;
    
} else {
    
	std::cout << "Element not found" << std::endl;
    
}

    return 0;
}

// Output
Element found: 30
Element not found

count():

The count() function returns the number of elements with a specific value, which is either 0 or 1 for std::set since it only allows unique elements.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};

    int count = mySet.count(30);

    std::cout << "Number of occurrences of 30: " << count << std::endl;

    return 0;
}

// Output
Number of occurrences of 30: 1

3. Deletion and Clearing:

erase():

The erase() function removes elements from the set, either a specific element or a range specified by iterators.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};

    // Erase a specific element
    mySet.erase(30);

    // Displaying elements
    for (const auto& element : mySet) {
        std::cout << element << " ";
    }

    return 0;
}

// Output
10 20 40 50

clear():

The clear() function removes all elements from the set, leaving it empty.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};

    // Clear all elements
    mySet.clear();

    // Check if the set is empty
    if (mySet.empty()) {
        std::cout << "Set is empty." << std::endl;
    }

    return 0;
}

// Output
Set is empty.

4. Iterators:

begin() and end():

Returns iterators pointing to the first and one past the last elements in the set, respectively.

Example:

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};

    // Using iterators to display elements
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

// Output
10 20 30 40 50

Complexity of Operations

Insertion

Best Case: O(log n) - Occurs when the tree is perfectly balanced, and the new element can be inserted with minimal comparisons.
Average Case: O(log n) - The self-balancing property ensures logarithmic height, maintaining efficient insertion.
Worst Case: O(log n) - Event in the worst case, where the tree needs to be rebalanced, the time complexity remains logarithmic.

Deletion (erase):

Best Case: O(log n) - Similar to insertion, the best case occurs when the tree is balanced, and the deletion operation is straightforward.
Average Case: O(log n) - The average time complexity is logarithmic due to the balanced nature of the binary search tree.
Worst Case: O(log n) - The worst case is also logarithmic, as the tree remains balanced through the deletion process.

Search (find):

Best Case: O(1) - The best case, the element being searched for is at the root of the tree.
Average Case: o(log n) - The binary search nature of the tree leads to logarithmic time complexity on average.
Worst Case: O(log n) - Even in the worst case, the binary search ensures logarithmic time complexity.

Iteration (forward and reverse):

Best case: O(1) - The best case for iteration is when there's only one element in the set.
Average Case: O(n) - Both forward and reverse iterations have a linear time complexity, as each element needs to be visited.
Worst Case: O(n) - In the worst case, the time complexity of iteration remains linear.

Associative Containers std::set in C++

Associative Containers std::set in C++