Collections in C++

C++ offers a powerful and versatile set of collection classes through its Standard Template Library (STL). The STL mainly categorizes containers into three types:

1. Sequence Containers: These store elements in a linear order, where each element has a specific position.

• vector: Dynamic array, allows efficient access to elements by index and dynamic resizing.
• deque: Double-ended queue, supports efficient insertion and deletion at both ends.
• list: Doubly linked list, efficient for insertion and deletion at any position but slower for random access.
• array: Fixed-size array, provides compile-time size and bounds checking.
• forward_list: Singly linked list, optimized for forward traversal and insertion/deletion.

2. Associative Containers: These store elements in a way that allows efficient retrieval based on a key, with a specific order. They are typically implemented as balanced binary search trees.

• set: Stores unique elements in a sorted order.
• map: Stores key-value pairs, where each key is unique and associated with a value.
• multiset: Allows duplicate elements, still sorted.
• multimap: Allows duplicate keys, each with its own associated value.

3. Unordered Associative Containers: These store elements in a way that allows efficient retrieval based on a key, but without a specific order. They are typically implemented using hash tables.

• unordered_set: Stores unique elements, providing fast lookup using a hash function.
• unordered_map: Stores key-value pairs with fast lookup using a hash function.
• unordered_multiset: Allows duplicate elements with fast lookup.
• unordered_multimap: Allows duplicate keys with fast lookup.

Container Adapters

These are not full container classes but provide a specific interface to an underlying container.

• stack: Provides a LIFO (Last-In, First-Out) data structure.
• queue: Provides a FIFO (First-In, First-Out) data structure.
• priority_queue: Provides a queue where elements are prioritized based on a comparison criterion.

Vector

Key Features:

• Dynamic Size: Unlike fixed-size arrays, vectors can grow or shrink automatically as you add or remove elements. This eliminates the need to pre-allocate a fixed amount of memory.
• Contiguous Storage: Elements in a vector are stored in contiguous memory locations, just like arrays. This allows for fast random access to elements using their index.
• Memory Management: Vectors handle memory allocation and deallocation automatically. You don’t need to manually manage memory using new and delete.
• Versatility: Vectors can store any data type, including primitive types (int, float, char), user-defined classes, and even other containers.

Internal Implementation:

[ elem1 | elem2 | elem3 | ... | elemN | unused space... ]
 ^       ^       ^                                    ^
 begin   end     capacity        

std::vector is implemented as a dynamic array. Here's a simplified view:

1. Contiguous Memory: A vector manages a contiguous block of memory to store its elements. This means the elements are located next to each other in memory.
2. Three Pointers:

• begin: Points to the beginning of the allocated memory (the first element).
• end: Points to one past the last element currently in the vector.
• capacity: Points to the end of the allocated memory block.

Time Complexity:

Creating a vector:

std::vector<int> numbers; // An empty vector of integers
std::vector<std::string> names = {"Alice", "Bob", "Charlie"}; // Initialize with values

Adding elements:

numbers.push_back(10); // Add an element at the end
numbers.insert(numbers.begin() + 2, 5); // Insert at a specific position

Accessing elements:

int firstNumber = numbers[0]; // Access by index
int thirdNumber = numbers.at(2); // Access by index with bounds checking

Removing elements:

numbers.pop_back(); // Remove the last element
numbers.erase(numbers.begin() + 1); // Remove at a specific position

Resize vector

// vector<T>::resize(size_type new_size, const T& value = T());

vector<int> numbers;
// Increase the size to 5
numbers.resize(5, 0);

Replace values

The assign() function is used to replace the contents of a vector with new values.

int main() {
  std::vector<int> numbers;
  numbers.assign(5, 10); // Assigns five 10s to the vector

  // numbers now contains: {10, 10, 10, 10, 10}
}

on 2d

int main() {
   // direct initialization
  std::vector<std::vector<int>> matrix = {{1, 2}, {3, 4}};

  // Assign new values to the entire matrix
  matrix.assign({{5, 6, 7}, {8, 9, 10}}); 

  //  Initializing with a Specific Size
  int rows = 3, cols = 4;
  std::vector<std::vector<int>> matrix2(rows, std::vector<int>(cols));
  
  // Initializing with a Specific Value:
   int value = 10;
   std::vector<std::vector<int>> matrix3(rows, std::vector<int>(cols, value));
  
}

3d

#include <vector>

int main() {
    int rows = 2, cols = 3, depth = 4;
    std::vector<std::vector<std::vector<int>>> matrix(rows, std::vector<std::vector<int>>(cols, std::vector<int>(depth)));
}

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the vector is empty
numbers.clear(); // Remove all elements

Sort vector

Vector doesn’t have member method to sort it. Instead we will use std::sort from algorithm header as below.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> myVector = {5, 2, 9, 1, 5};

    // Sort the vector in ascending order
    std::sort(myVector.begin(), myVector.end());

    // Print the sorted vector
    for (int num : myVector) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Example

#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 5};

  std::cout << "Initial vector: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  numbers.push_back(6);
  numbers.erase(numbers.begin() + 2); // Remove the third element (value 3)

  std::cout << "Modified vector: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}

dqueue

Key Features:

• Double-ended access: You can efficiently add or remove elements from both the front and back of the deque.
• Dynamic size: Like std::vector, deques can grow or shrink as needed.
• Random access: You can access elements by their index using the [] operator, although it might be slightly less efficient than std::vector.
• No contiguous storage: Unlike std::vector, elements in a deque are not necessarily stored contiguously in memory. This allows for efficient insertion and deletion at both ends without the need to shift elements.

Internal Implementation:

  Map: [ptr1] [ptr2] [ptr3] ... 
        |     |     |
        v     v     v
   Block 1  Block 2  Block 3 ...
  [elem1][elem2][elem3]...[elemN]

std::deque is typically implemented as a dynamically allocated array of fixed-size blocks. Think of it like this:

1. Map (or index array): A deque maintains a dynamic array (often a std::vector) that acts as a map. Each element in this map is a pointer to a fixed-size block of memory.
2. Blocks: Each block stores a contiguous chunk of elements of the deque. The block size is usually chosen by the implementation (e.g., 512 bytes).
3. Dynamic Growth: When the deque needs more space (at either end), it allocates a new block and updates the map accordingly. This allows it to grow efficiently in both directions.

Time Complexity:

Creating a deque:

std::deque<int> numbers; // An empty deque of integers
std::deque<std::string> names = {"Alice", "Bob", "Charlie"}; // Initialize with values

Adding elements:

numbers.push_back(10); // Add at the back
numbers.push_front(5); // Add at the front

Accessing elements:

int firstNumber = numbers[0]; // Access by index
int lastNumber = numbers.back(); // Access the last element

Removing elements:

numbers.pop_back(); // Remove from the back
numbers.pop_front(); // Remove from the front

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the deque is empty
numbers.clear(); // Remove all elements

Example

#include <iostream>
#include <deque>

int main() {
  std::deque<int> numbers = {1, 2, 3};

  numbers.push_front(0);
  numbers.push_back(4);

  std::cout << "Deque: ";
  for (int num : numbers) {
    std::cout << num << " "; 
  }
  std::cout << std::endl; // Output: Deque: 0 1 2 3 4

  return 0;
}

List

std::list is a sequence container that provides a doubly linked list implementation.

Key Features:

• Efficient insertion and deletion: You can efficiently insert or remove elements at any position within the list in constant time (O(1)). This is a major advantage over std::vector and std::deque, where insertion or deletion in the middle can be expensive (O(N)).
• Bi-directional iteration: You can iterate through the list in both forward and backward directions.
• No random access: Unlike std::vector or std::deque, you cannot directly access elements by their index using the [] operator. You need to use iterators to traverse the list and access elements.

Creating a list:

std::list<int> numbers; // An empty list of integers
std::list<std::string> names = {"Alice", "Bob", "Charlie"}; // Initialize with values

Adding elements:

numbers.push_back(10); // Add at the back
numbers.push_front(5); // Add at the front
numbers.insert(numbers.begin(), 2); // Insert at a specific position

Accessing elements:

int firstNumber = numbers.front(); // Access the first element
int lastNumber = numbers.back(); // Access the last element
// To access other elements, you need to use iterators.

Removing elements:

numbers.pop_back(); // Remove from the back
numbers.pop_front(); // Remove from the front
numbers.erase(numbers.begin()); // Remove at a specific position

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the list is empty
numbers.clear(); // Remove all elements
numbers.sort(); // Sort the elements
numbers.reverse(); // Reverse the order of elements

Example

#include <iostream>
#include <list>

int main() {
  std::list<int> numbers = {1, 2, 4, 5};

  numbers.push_front(0);
  numbers.insert(++numbers.begin(), 3); // Insert 3 after 0

  std::cout << "List: ";
  for (int num : numbers) {
    std::cout << num << " "; 
  }
  std::cout << std::endl; // Output: List: 0 3 1 2 4 5

  return 0;
}

Time Complexity:

Array

An array is a fundamental data structure used to store a fixed-size sequential collection of elements of the same data type.

Key characteristics:

• Fixed size: The size of an array is determined at the time of declaration and cannot be changed during runtime.
• Contiguous memory: Array elements are stored in contiguous memory locations, allowing for efficient random access using their index.
• Zero-based indexing: The first element of an array has an index of 0, the second element has an index of 1, and so on.
• Homogeneous elements: All elements in an array must be of the same data type.

Declaration

data_type array_name[array_size];

Example

int numbers[5];  // An array named "numbers" that can hold 5 integers
double prices[10]; // An array named "prices" that can hold 10 doubles
char letters[26]; // An array named "letters" that can hold 26 characters

Size of array

Array variable points to the pointer to the first element. Therefore there are no api to get the size of array quickly. Instead we need to use sizeof as below.

int numbers[5];  // An array named "numbers" that can hold 5 integers
int size = sizeof(numbers)/sizeof(arr[0]);

Size of array when passed as parameter

When you pass an array to a function, it decays to a pointer. For example:

void myFunction(char state[]) {
    // Here, 'state' is treated as 'char*', not 'char[]'
}

sizeof Behavior:

1. Inside the function, sizeof(state) returns the size of the pointer (char*), which is typically 8 bytes on a 64-bit system or 4 bytes on a 32-bit system.
2. sizeof(state[0]) returns the size of a single char, which is 1 byte.
3. Therefore, sizeof(state) / sizeof(state[0]) gives the size of the pointer divided by 1, which is not the size of the array.

To get the size of the array, you need to pass the size explicitly as an additional parameter to the function.

#include <iostream>
using namespace std;

void printSize(char state[], int size) {
    cout << "Size of state: " << size << endl;
}

int main() {
    char myArray[] = "Hello";
    int size = sizeof(myArray) / sizeof(myArray[0]); // Calculate size of the array
    printSize(myArray, size); // Pass the array and its size to the function
    return 0;
}

Initialization

The = {} provides an initializer list. In C++, when you initialize an array with an initializer list that has fewer elements than the array size, the remaining elements are value-initialized.

int ages[5] = {1}; // First initialized by 1 and rest by 0
int numbers[5] = {1, 2, 3, 4, 5}; // Initialize with values
double prices[3] = {10.99, 5.50, 2.75}; 
char name[6] = {'J', 'o', 'h', 'n', '\0'}; // Null-terminated character array (string)

Value-initialization for pointers: For pointer types, value-initialization means setting them to nullptr. Following are few examples for pointers.

TrieNode* children[26] = {};
TrieNode* children[26] = {nullptr}; // Same as above

Dynamic Memory Allocation

Dynamic memory allocation allows you to allocate memory for an array (or any other data structure) at runtime. This is done using the new keyword. When you allocate memory dynamically, you are responsible for freeing it using the delete keyword to avoid memory leaks.

#include <iostream>
using namespace std;

int main() {
    int n;

    // Ask the user for the size of the array
    cout << "Enter the size of the array: ";
    cin >> n;

    // Dynamically allocate memory for the array
    int* arr = new int[n];

    // Check if memory allocation was successful
    if (arr == nullptr) {
        cout << "Memory allocation failed!" << endl;
        return 1; // Exit the program with an error code
    }

    // Input elements into the array
    cout << "Enter " << n << " integers:" << endl;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Display the elements of the array
    cout << "Array elements: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Free the dynamically allocated memory
    delete[] arr;

    return 0;
}

You can also dynamically allocate memory for multidimensional arrays. Here’s an example for a 2D array:

#include <iostream>
using namespace std;

int main() {
    int rows, cols;

    // Ask the user for the size of the 2D array
    cout << "Enter the number of rows: ";
    cin >> rows;
    cout << "Enter the number of columns: ";
    cin >> cols;

    // Dynamically allocate memory for the 2D array
    int** arr = new int*[rows];
    for (int i = 0; i < rows; i++) {
        arr[i] = new int[cols];
    }

    // Input elements into the 2D array
    cout << "Enter " << rows * cols << " integers:" << endl;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> arr[i][j];
        }
    }

    // Display the elements of the 2D array
    cout << "2D array elements:" << endl;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    // Free the dynamically allocated memory
    for (int i = 0; i < rows; i++) {
        delete[] arr[i];
    }
    delete[] arr;

    return 0;
}

Accessing Elements:

int thirdNumber = numbers[2]; // Access the third element (index 2)
prices[0] = 12.50; // Modify the first element

Iterating through an Array:

for (int i = 0; i < 5; i++) {
  std::cout << numbers[i] << " ";
}

Passing array as a parameter

When you pass an array as int[] to a function in C++, the array is not copied. Instead, the array decays to a pointer to its first element. This means that the function receives a pointer to the original array, and any modifications made to the array inside the function will affect the original array.

#include <iostream>
using namespace std;

// Function that takes an int array as a parameter
void modifyArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] *= 2; // Modify the array elements
    }
}

int main() {
    int myArray[] = {10, 20, 30, 40, 50};
    int size = sizeof(myArray) / sizeof(myArray[0]); // Calculate size of the array

    cout << "Original array: ";
    for (int i = 0; i < size; i++) {
        cout << myArray[i] << " ";
    }
    cout << endl;

    // Pass the array to the function
    modifyArray(myArray, size);

    cout << "Modified array: ";
    for (int i = 0; i < size; i++) {
        cout << myArray[i] << " ";
    }
    cout << endl;

    return 0;
}

If you want to pass a copy of the array (so that modifications inside the function do not affect the original array), you need to explicitly create a copy and pass it. For example:

#include <iostream>
#include <algorithm> // For std::copy
using namespace std;

// Function that takes a copy of the array
void modifyArrayCopy(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] *= 2; // Modify the copy of the array
    }
}

int main() {
    int myArray[] = {10, 20, 30, 40, 50};
    int size = sizeof(myArray) / sizeof(myArray[0]);

    // Create a copy of the array
    int* copyArray = new int[size];
    copy(myArray, myArray + size, copyArray); // Copy elements from myArray to copyArray

    cout << "Original array: ";
    for (int i = 0; i < size; i++) {
        cout << myArray[i] << " ";
    }
    cout << endl;

    // Pass the copy of the array to the function
    modifyArrayCopy(copyArray, size);

    cout << "Modified copy: ";
    for (int i = 0; i < size; i++) {
        cout << copyArray[i] << " ";
    }
    cout << endl;

    cout << "Original array after modification: ";
    for (int i = 0; i < size; i++) {
        cout << myArray[i] << " ";
    }
    cout << endl;

    // Free the dynamically allocated memory
    delete[] copyArray;

    return 0;
}

Pass as int* (Pointer)

Since an int[] decays to an int*, you can directly use an int* as the parameter type.

#include <iostream>
using namespace std;

// Function that takes an int pointer as a parameter
void printIntArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int myArray[] = {10, 20, 30, 40, 50};
    int size = sizeof(myArray) / sizeof(myArray[0]); // Calculate size of the array
    printIntArray(myArray, size); // Pass the int array and its size to the function
    return 0;
}

Sorting array

Array doesn’t have sort as a member function. We need to use the sort from algorithm header as below.

#include <iostream>
#include <algorithm>

int main() {
    int arr[] = {5, 2, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::sort(arr, arr + n);

    // Print the sorted array
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Time complexities

Hashability and comparator

Hashability: The unordered_map (or other collection using hash)container uses a hash table internally for efficient key-value lookups. To use a custom type as the key, such as pair<int, int>, it must be hashable. The hash function is responsible for mapping the key to a unique hash value, which determines the position in the hash table where the value will be stored.

By default, the standard library does not provide a hash function specialization for pair<int, int>. Therefore, attempting to use unordered_map<pair<int, int>, int> will result in a compilation error, indicating that there is no matching hash function for the key type.

Following code will throw compilation error.

unordered_map<pair<int, int>, int> myMap;  // Compilation error: no matching hash fun

Equality Operator: In addition to being hashable, the key type also requires a well-defined equality operator (operator==). This operator is used to compare keys for equality when resolving collisions in the hash table. Without a defined equality operator, the unordered_map cannot determine if two keys are equal or not.

For example, the pair<int, int> type has a default equality operator, but it performs element-wise comparison. It checks if the first elements are equal and then checks if the second elements are equal. This behavior may not be suitable for all use cases. For example, (1, 2) and (2, 1) would be considered equal with the default equality operator, which may not be desired.

Following is example code to show the problem with default equality operator.

unordered_map<pair<int, int>, int> myMap;
pair<int, int> key1 = {1, 2};
pair<int, int> key2 = {2, 1};

myMap[key1] = 42;
cout << myMap[key2] << endl;  // Unexpected behavior due to default equality operator

To resolve these issues, you need to provide custom implementations for the hash function and equality operator for the pair<int, int> type. By doing so, you can enable the use of pair<int, int> as the key type in an unordered_map and others.

Here’s an example of how you can define the necessary customizations:

struct PairHash {
  template <class T1, class T2>
  size_t operator() (const pair<T1, T2> & p) const {
    auto h1 = hash<T1>{}(p.first);
    auto h2 = hash<T2>{}(p.second);
    return h1^h2;
  }
};

struct PairEqual{
  template<class T1, class T2>
  bool operator()(const pair<T1,T2>& lhs, const pair<T1,T2>& rhs) const {
   return lhs.first == rhs.first && lhs.second == rhs.second;
  } 
};

unordered_map<pair<int, int>, int, PairHash, PairEqual> myMap;

struct as a key

Similarly, if we have to use struct as a key then we need to override == and < operator as below.

struct Node {
    string email;
    string name;
    bool operator==(const Node& n) const {
        return this->email == n.email && this->name == n.name;
    }
    bool operator < (const Node& n) const {
        return this->email < n.email && this->name < n.name;
    }
};
namespace std {
template <> struct hash<Node> {
    size_t operator()(const Node& n) const {
        return hash<string>()(n.name) ^ hash<string>()(n.email);
    }
};
}; // namespace std

Set

std::set is an associative container that stores unique elements in a specific order. This means no duplicate elements are allowed, and the elements are automatically sorted according to a strict weak ordering criterion (by default, it's less-than <).

Key Features:

• Unique elements: Only one instance of each element can exist in the set.
• Sorted order: Elements are always stored in a sorted order, which allows for efficient searching and retrieval.
• Implementation: Typically implemented as a balanced binary search tree (e.g., red-black tree). This ensures logarithmic time complexity for most operations.
• Dynamic size: The set can grow or shrink as you add or remove elements.

Creating a set:

std::set<int> numbers; // An empty set of integers
std::set<std::string> names = {"Alice", "Bob", "Charlie"}; // Initialize with values

Adding elements:

numbers.insert(10); // Add an element
numbers.insert(5); // Adding a duplicate has no effect

Checking for an element:

if (numbers.count(5) > 0) { 
    std::cout << "5 is in the set\n"; 
}
// Or
if (numbers.find(5) != numbers.end()) {
    std::cout << "5 is in the set\n";
}

Removing elements:

numbers.erase(10); // Remove an element by value
auto it = numbers.find(5);
if (it != numbers.end()) {
    numbers.erase(it); // Remove an element using an iterator
}

find element

The find method returns an iterator to the found element or the end() iterator if not found.

#include <iostream>
#include <set>

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

    // Find an element
    auto it = mySet.find(30);

    if (it != mySet.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the set is empty
numbers.clear(); // Remove all elements

Example

#include <iostream>
#include <set>

int main() {
  std::set<int> numbers = {5, 2, 8, 1, 9, 2}; // 2 is a duplicate, so it's ignored
  std::cout << "Set: ";
  for (int num : numbers) {
    std::cout << num << " "; 
  }
  std::cout << std::endl; // Output: Set: 1 2 5 8 9
  return 0;
}

Time Complexity:

unordered_set

std::unordered_set is an associative container that stores unique elements, just like std::set. However, unlike std::set, std::unordered_set does not store elements in a sorted order. Instead, it uses a hash table for internal implementation, which allows for very efficient average-case performance for operations like insertion, deletion, and search.

Key Features:

• Unique elements: Only one instance of each element can exist in the unordered set.
• Unordered: Elements are not stored in any particular order.
• Hash table implementation: Uses a hash table to store elements, which enables fast average-case lookup.
• Dynamic size: The unordered set can grow or shrink as you add or remove elements.

Creating an unordered set:

std::unordered_set<int> numbers; // An empty unordered set of integers
std::unordered_set<std::string> names = {"Alice", "Bob", "Charlie"}; // Initialize with values

Adding elements:

numbers.insert(10); // Add an element
numbers.insert(5); 
// Adding a duplicate has no effect

Checking for an element:

if (numbers.count(5) > 0) { 
    std::cout << "5 is in the set\n"; 
}
// Or
if (numbers.find(5) != numbers.end()) {
    std::cout << "5 is in the set\n";
}

Removing elements:

numbers.erase(10); // Remove an element by value
auto it = numbers.find(5);
if (it != numbers.end()) {
    numbers.erase(it); // Remove an element using an iterator
}

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the unordered set is empty
numbers.clear(); // Remove all elements

Example:

#include <iostream>
#include <unordered_set>

int main() {
  std::unordered_set<int> numbers = {5, 2, 8, 1, 9, 2}; // 2 is a duplicate, so it's ignored

  std::cout << "Unordered Set: ";
  for (int num : numbers) {
    std::cout << num << " "; 
  }
  std::cout << std::endl; // Output: Unordered Set: 9 1 8 2 5 (order may vary)

  return 0;
}

Time complexity

multiset

std::multiset is an associative container that is very similar to std::set, but with a key difference: it allows for multiple elements with the same value.

Think of it like a bag where you can have multiple items of the same kind, but still maintain a sorted order based on those items.

Key Features:

• Multiple elements with the same value: Unlike std::set, std::multiset allows duplicate elements.
• Sorted order: Elements are always stored in a sorted order based on their values (which act as keys). This allows for efficient searching and retrieval.
• Implementation: Typically implemented as a balanced binary search tree (e.g., red-black tree).
• Dynamic size: The multiset can grow or shrink as you add or remove elements.

Creating a multiset:

std::multiset<int> numbers; // An empty multiset of integers
std::multiset<std::string> names = {"Alice", "Bob", "Charlie", "Bob"}; // Initialize with values (duplicates allowed)

Adding elements:

numbers.insert(10); // Add an element
numbers.insert(5); 
numbers.insert(5); // Adding duplicates is allowed

Checking for an element:

if (numbers.count(5) > 0) { 
    std::cout << "5 is in the multiset\n"; 
}
// Or
if (numbers.find(5) != numbers.end()) {
    std::cout << "5 is in the multiset\n";
}

Removing elements:

numbers.erase(5); // Removes ALL instances of 5
auto it = numbers.find(5);
if (it != numbers.end()) {
    numbers.erase(it); // Removes a single instance of 5 (the one found by the iterator)
}

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the multiset is empty
numbers.clear(); // Remove all elements
int count = numbers.count(5); // Count occurrences of a specific value

Example:

#include <iostream>
#include <set>

int main() {
  std::multiset<int> numbers = {5, 2, 8, 1, 9, 2}; // Duplicates are allowed

  std::cout << "Multiset: ";
  for (int num : numbers) {
    std::cout << num << " "; 
  }
  std::cout << std::endl; // Output: Multiset: 1 2 2 5 8 9 

  return 0;
}

Time Complexity:

Map

std::map is an associative container that stores key-value pairs, where each key is unique and associated with a specific value. The keys are used to access the corresponding values. std::map keeps its elements sorted by key, which allows for efficient retrieval, insertion, and deletion of elements.

Key Features:

• Key-value pairs: Stores elements as key-value pairs, where keys are unique and used to access the associated values.
• Sorted order: Elements are always stored in a sorted order based on their keys. This allows for efficient searching and retrieval.
• Implementation: Typically implemented as a balanced binary search tree (e.g., red-black tree).
• Dynamic size: The map can grow or shrink as you add or remove elements.

Creating a map:

std::map<std::string, int> ages; // A map with string keys and integer values
std::map<char, std::string> grades = {{'A', "Excellent"}, {'B', "Good"}, {'C', "Average"}}; // Initialize with values

Adding elements:

ages["Alice"] = 30; // Add a key-value pair
ages.insert(std::make_pair("Bob", 25)); // Another way to insert

Accessing elements:

int aliceAge = ages["Alice"]; // Access the value associated with "Alice"
// If the key doesn't exist, it's added with a default value (0 for int)

Checking for a key:

if (ages.count("Bob") > 0) {
    std::cout << "Bob's age is found\n";
}
// Or
if (ages.find("Bob") != ages.end()) {
    std::cout << "Bob's age is found\n";
}

Removing elements:

ages.erase("Alice"); // Remove the key-value pair with key "Alice"

Other useful operations:

int size = ages.size(); // Get the number of elements
bool isEmpty = ages.empty(); // Check if the map is empty
ages.clear(); // Remove all elements

Example

#include <iostream>
#include <map>

int main() {
  std::map<std::string, int> ages;
  ages["Alice"] = 30;
  ages["Bob"] = 25;
  ages["Charlie"] = 35;

  std::cout << "Ages:   
 \n";
  for (const auto& pair : ages) {
    std::cout << pair.first << ": " << pair.second << std::endl;
  }
  // Output: 
  // Ages: 
  // Alice: 30
  // Bob: 25
  // Charlie: 35

  return 0;
}

Time Complexity:

Unordered map

std::unordered_map is an associative container that stores key-value pairs, similar to std::map. However, it uses a hash table for its underlying implementation instead of a binary search tree.

Key Features:

• Key-value pairs: Stores elements as key-value pairs, where each key is unique and associated with a specific value.
• Unordered: Elements are not stored in any particular order. The order depends on the hash function and can seem random.
• Hash table implementation: Uses a hash table to store elements, which allows for very fast average-case lookups, insertions, and deletions.
• Dynamic size: The unordered map can grow or shrink as you add or remove elements.

Creating an unordered map:

std::unordered_map<std::string, int> ages; // A map with string keys and integer values
std::unordered_map<char, std::string> grades = {{'A', "Excellent"}, {'B', "Good"}, {'C', "Average"}}; // Initialize with values

Adding elements:

ages["Alice"] = 30; // Add a key-value pair
ages.insert(std::make_pair("Bob", 25)); // Another way to insert

Accessing elements:

int aliceAge = ages["Alice"]; // Access the value associated with "Alice"
// If the key doesn't exist, it's added with a default value (0 for int)

Checking for a key:

if (ages.count("Bob") > 0) {
    std::cout << "Bob's age is found\n";
}
// Or
if (ages.find("Bob") != ages.end()) {
    std::cout << "Bob's age is found\n";
}

Removing elements:

ages.erase("Alice"); // Remove the key-value pair with key "Alice"

Other useful operations:

int size = ages.size(); // Get the number of elements
bool isEmpty = ages.empty(); // Check if the unordered map is empty
ages.clear(); // Remove all elements

Example:

#include <iostream>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, int> ages;
  ages["Alice"] = 30;
  ages["Bob"] = 25;
  ages["Charlie"] = 35;

  std::cout << "Ages: \n";
  for (const auto& pair : ages) {
    std::cout << pair.first << ": " << pair.second << std::endl;
  }
  // Output (order may vary):
  // Ages: 
  // Charlie: 35
  // Alice: 30
  // Bob: 25 

  return 0;
}

Time Complexity:

multimap

std::multimap is an associative container that's a step up in flexibility from std::map. Like std::map, it stores key-value pairs. The key difference is that std::multimap allows for multiple key-value pairs with the same key.

Think of it like an address book where multiple people might live at the same address (the key), and you want to keep track of all of them.

Key Features:

• Multiple key-value pairs with the same key: Unlike std::map, std::multimap allows duplicate keys. This means you can have multiple values associated with the same key.
• Sorted order: Elements are always stored in a sorted order based on their keys. This allows for efficient range-based searching and retrieval of elements with the same key.
• Implementation: Typically implemented as a balanced binary search tree (e.g., red-black tree).
• Dynamic size: The multimap can grow or shrink as you add or remove elements.

Creating a multimap:

std::multimap<std::string, std::string> addressBook; // A multimap with string keys (addresses) and string values (names)
std::multimap<int, char> grades = {{85, 'A'}, {85, 'B'}, {75, 'C'}}; // Initialize with values (duplicate keys allowed)

Adding elements:

addressBook.insert(std::make_pair("123 Main St", "Alice")); 
addressBook.insert(std::make_pair("123 Main St", "Bob")); // Same address, different person

Accessing elements:

auto range = addressBook.equal_range("123 Main St"); // Get the range of elements with the key "123 Main St"
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << std::endl; // Print the names associated with that address
}

Checking for a key

if (addressBook.count("123 Main St") > 0) {
    std::cout << "There are entries for 123 Main St\n";
}

Removing elements:

addressBook.erase("123 Main St"); // Removes ALL entries with the key "123 Main St"
auto it = addressBook.find("123 Main St");
if (it != addressBook.end()) {
    addressBook.erase(it); // Removes a single entry (the one found by the iterator)
}

Other useful operations:

int size = addressBook.size(); // Get the number of elements
bool isEmpty = addressBook.empty(); // Check if the multimap is empty
addressBook.clear(); // Remove all elements
int count = addressBook.count("123 Main St"); // Count occurrences of a specific key

Example

#include <iostream>
#include <map>

int main() {
  std::multimap<std::string, std::string> addressBook;
  addressBook.insert(std::make_pair("123 Main St", "Alice")); 
  addressBook.insert(std::make_pair("456 Oak Ave", "Bob")); 
  addressBook.insert(std::make_pair("123 Main St", "Charlie")); 

  std::cout << "Address Book: \n";
  for (const auto& entry : addressBook) {
    std::cout << entry.first << ": " << entry.second << std::endl;
  }
  // Output:
  // Address Book: 
  // 123 Main St: Alice
  // 123 Main St: Charlie
  // 456 Oak Ave: Bob

  return 0;
}

Time Complexity:

stack

std::stack is a container adapter that gives you the functionality of a LIFO (Last-In, First-Out) stack. This means that the last element added to the stack is the first one to be removed.

Key Features:

• LIFO (Last-In, First-Out): The last element pushed onto the stack is the first one to be popped off.
• Underlying container: std::stack is an adapter, which means it uses another container to store its elements. By default, it uses std::deque, but you can also use std::vector or std::list as the underlying container.
• Restricted access: It provides a limited set of operations to enforce the LIFO behavior. You can only add elements to the top, remove from the top, and access the top element.

Creating a stack:

std::stack<int> numbers; // A stack of integers
std::stack<std::string> names; // A stack of strings

Adding elements (push):

numbers.push(10); // Add 10 to the top of the stack
numbers.push(5); // Add 5 to the top (5 is now the top element)

Accessing the top element:

int topElement = numbers.top(); // Get the top element (5 in this case)

Removing the top element (pop):

numbers.pop(); // Removes the top element (5)

Remove all elements to make it empty

Stack doesn’t prove clear() method. Therefore we need to write our own code to clear all the contents of stack. Following are few approaches.

Method 1: Popping all elements

This is the most straightforward approach. While this works, it can be inefficient for very large stacks.

#include <stack>

void clearStackByPopping(std::stack<int>& s) {
  while (!s.empty()) {
    s.pop();
  }
}

Method 2: Swapping with an empty stack

This is generally the most efficient way to clear a stack in C++:

#include <stack>

void clearStackBySwapping(std::stack<int>& s) {
  std::stack<int>().swap(s); 
}

Iterating elements of stack

The std::stack interface only allows access to the top element (top()) and removal of the top element (pop()). It doesn't provide iterators or direct access to internal elements..

Therefore directly iterating through all elements of a std::stack without popping them is not possible. Following is code with popping element.

// Create a temporary stack to store elements
std::stack<int> tempStack;

// Iterate through the elements by popping and pushing to temporary stack
while (!myStack.empty()) {
    int top = myStack.top();
    myStack.pop();
    std::cout << top << " ";
    tempStack.push(top); // Store the popped element in temporary stack
}
std::cout << std::endl;

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the stack is empty

Example

#include <iostream>
#include <stack>

int main() {
  std::stack<char> letters;
  letters.push('a');
  letters.push('b');
  letters.push('c');

  std::cout << "Top element: " << letters.top() << std::endl; // Output: Top element: c

  letters.pop();
  std::cout << "Top element after pop: " << letters.top() << std::endl; // Output: Top element after pop: b

  return 0;
}

Time Complexity:

queue

std::queue is a container adapter that provides the functionality of a First-In, First-Out (FIFO) queue. This means that the elements are added to the back of the queue and removed from the front, much like a real-world queue or line.

Key Features:

• FIFO (First-In, First-Out): Elements are added to the back and removed from the front, maintaining the order of insertion.
• Underlying container: std::queue is an adapter, which means it uses another container (by default, std::deque) to store its elements. You can also use std::list as the underlying container.
• Restricted access: It provides a limited set of operations to enforce the FIFO behavior. You can only add elements to the back, remove from the front, and access the front and back elements.

Creating a queue:

std::queue<int> numbers; // A queue of integers
std::queue<std::string> names; // A queue of strings

Adding elements:

numbers.push(10); // Add 10 to the back of the queue
numbers.push(5); // Add 5 to the back (10 is now at the front)

Accessing the front element:

int frontElement = numbers.front(); // Get the front element (10 in this case)

Removing the front element:

numbers.pop(); // Removes the front element (10)

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the queue is empty

Example

#include <iostream>
#include <queue>

int main() {
  std::queue<std::string> tasks;
  tasks.push("Write code");
  tasks.push("Compile");
  tasks.push("Test");

  std::cout << "First task: " << tasks.front() << std::endl; // Output: First task: Write code

  tasks.pop();
  std::cout << "Next task: " << tasks.front() << std::endl; // Output: Next task: Compile

  return 0;
}

Time Complexity:

priority_queue

std::priority_queue is a container adapter that provides a way to store elements with an associated priority. It's designed so that the element with the highest priority is always at the top, allowing efficient access to the most important element.

Key Features:

• Priority-based ordering: Elements are ordered based on their priority. By default, the highest priority element is at the top.
• Underlying container: std::priority_queue is an adapter, which means it uses another container (by default, std::vector) to store its elements.
• Heap implementation: It typically uses a binary heap data structure to maintain the priority order efficiently.
• Access to the top element: You can easily access the highest priority element using top().

Creating a priority queue:

std::priority_queue<int> numbers; // A priority queue of integers (highest value has highest priority by default)
std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>> names; // A priority queue of strings with the lowest alphabetical order having the highest priority

Adding elements:

numbers.push(10);
numbers.push(5);
numbers.push(15); // 15 will be at the top

Accessing the top element:

int highestPriority = numbers.top(); // Get the highest priority element (15 in this case)

Removing the top element:

numbers.pop(); // Removes the top element (15)

Other useful operations:

int size = numbers.size(); // Get the number of elements
bool isEmpty = numbers.empty(); // Check if the priority queue is empty

Max priority queue example

By default priority queue is a max priority queue. But you can explicitly use less<int> to define it as well.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
   // priority_queue<int ,vector<int>, less<int>> pq;

    pq.push(5);
    pq.push(2);
    pq.push(8);
    pq.push(1);
    pq.push(4);

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}

Min priority queue example

#include <iostream>
#include <queue>

using namespace std;

int main() {
    // Create a min-heap priority queue
    priority_queue<int, vector<int>, greater<int>> pq;

    // Insert elements
    pq.push(5);
    pq.push(2);
    pq.push(8);
    pq.push(1);
    pq.push(4);

    // Print the elements in min-heap order
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}

With custom comparator

• We define a Compare structure with an operator() overload.
• This operator defines the comparison logic for two Node objects.
• In this case, we want a min-heap, so we compare the data members and return true if a.data is greater than b.data.

#include <iostream>
#include <queue>

using namespace std;

struct Node {
    int data;
    // ... other members
};

// Custom comparator for min-heap
struct Compare {
    bool operator()(const Node& a, const Node& b) {
        return a.data > b.data;
    }
};

int main() {
    priority_queue<Node, vector<Node>, Compare> pq;

    // ... (push nodes into the priority queue)

    // Now, the top element will be the node with the smallest 'data' value
}

Example:

#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int> numbers;
  numbers.push(10);
  numbers.push(5);
  numbers.push(15);

  std::cout << "Top element: " << numbers.top() << std::endl; // Output: Top element: 15

  numbers.pop();
  std::cout << "Top element after pop: " << numbers.top() << std::endl; // Output: Top element after pop: 10

  return 0;
}

Time Complexity:

Pair

std::pair is a template class that allows you to store two values of different data types within a single object

Following is sample use .

#include <iostream>
#include <utility>

int main() {
    // Creating a pair of int and string
    std::pair<int, std::string> p1(10, "Hello");

    // Accessing elements
    std::cout << "First element: " << p1.first << std::endl;
    std::cout << "Second element: " << p1.second << std::endl;

    return 0;
}

Making Pairs with make_pair:

The make_pair function is a convenient way to create pairs:

#include <iostream>
#include <utility>

int main() {
    std::pair<int, std::string> p2 = std::make_pair(20, "World");

    // Accessing elements
    std::cout << "First element: " << p2.first << std::endl;
    std::cout << "Second element: " << p2.second << std::endl;

    return 0;
}

Tuple

A tuple is a versatile data structure that allows you to group multiple values of different data types into a single entity. It’s similar to a std::pair, but it can hold more than two elements.

Following is sample example.

#include <iostream>
#include <tuple>

int main() {
    // Creating a tuple of int, string, and double
    std::tuple<int, std::string, double> t1(10, "Hello", 3.14);

    // Accessing elements using get<>()
    std::cout << "First element: " << std::get(t1) << std::endl;
    std::cout << "Second element: " << std::get(t1) << std::endl;
    std::cout << "Third element: " << std::get(t1) << std::endl;

    return 0;
}

tuple_size

const int numMembers = tuple_size<tupleType>::value;
cout << "Last element: " << get<numMembers - 1>(tup) << endl;

Operations on tuple :-
1. get() :- get() is used to access the tuple values and modify them, it accepts the index and tuple name as arguments to access a particular tuple element.

2. make_tuple() :- make_tuple() is used to assign tuple with values. The values passed should be in order with the values declared in tuple.

    // Declaring tuple
    tuple <char, int, float> geek;

    // Assigning values to tuple using make_tuple()
    geek = make_tuple('a', 10, 15.5);

Unpack tuple elements directly

For C++17 and later, you can use structured binding to unpack tuple elements directly:

tuple <char, int, float> myTuple;
auto [first, second, third] = myTuple;

Default sorting behavior

By default, when you sort a vector<tuple<int, int, int>>, it will be sorted lexicographically based on the first element of each tuple. If two tuples have the same first element, it will then compare the second elements, and so on.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

int main() {
    std::vector<std::tuple<int, int, int>> myVector = {
        {3, 2, 1},
        {1, 4, 3},
        {2, 3, 2}
    };

    // Default Sort based on lexicographical ordering
    std::sort(myVector.begin(), myVector.end());

    // Print the sorted vector
    for (const auto [first, second, third] : myVector) {
        std::cout << first << " " << second << " " << third << std::endl;
    }

    return 0;
}

Happy learning c++.