C++ STL Containers

---

Introduction

The Standard Template Library (STL) in C++ provides a set of generic containers that allow you to store and manipulate collections of data. These containers are highly optimized and can be used to implement many common data structures such as arrays, lists, maps, and queues.

STL containers can be divided into several categories:

• Sequence Containers: Store elements in a linear sequence.
• Associative Containers: Store elements in a way that allows fast searching.
• Unordered Containers: Store elements based on hash functions.
• Container Adapters: Provide different interfaces for standard containers like stacks, queues, etc.

Let’s explore each of these container types in more detail.

---

1. Sequence Containers

Sequence containers store data in a linear sequence. They maintain the order of the elements and allow you to access them by index or position. Common sequence containers are:

• vector
• deque
• list
• array

vector

A vector is a dynamic array that allows fast random access to elements and can resize automatically when elements are added or removed.

Features:

• Dynamic resizing.
• Elements are stored contiguously.
• Allows fast access using indices.

Example of Using vector:

#include <iostream>
#include <vector>
using namespace std;

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

    // Adding elements to the vector
    v.push_back(6);

    // Displaying elements using index-based access
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• push_back() is used to add elements to the end of the vector.
• Elements are accessed by index using v[i].

deque

A deque (double-ended queue) allows fast insertion and deletion at both ends (front and back) of the container.

Features:

• Allows insertion and deletion at both ends.
• Random access is slower compared to vector.

Example of Using deque:

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq = {1, 2, 3, 4, 5};

    // Inserting elements at the front and back
    dq.push_front(0);
    dq.push_back(6);

    // Displaying elements using a range-based for loop
    for (int i : dq) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• push_front() adds elements to the front of the deque.
• push_back() adds elements to the back.
• A range-based for loop is used to iterate through the deque.

list

A list is a doubly linked list. It allows fast insertions and deletions from both ends but does not provide random access to elements.

Features:

• Fast insertions and deletions at both ends.
• Slower access compared to vector and deque.

Example of Using list:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3, 4, 5};

    // Adding elements to the list
    l.push_back(6);
    l.push_front(0);

    // Displaying elements using an iterator
    for (auto it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• push_back() adds an element to the back of the list.
• push_front() adds an element to the front.
• An iterator is used to traverse through the list.

array

An array is a fixed-size container that holds a collection of elements of the same type. It is part of C++11 and beyond.

Features:

• Fixed size (size must be known at compile-time).
• Provides fast random access.

Example of Using array:

#include <iostream>
#include <array>
using namespace std;

int main() {
    array<int, 5> arr = {1, 2, 3, 4, 5};

    // Accessing elements using index
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• array<int, 5> defines an array of 5 integers.
• You can access elements using an index just like a regular array.

---

2. Associative Containers

Associative containers store elements in a way that allows fast searching and retrieval based on keys. These containers use trees or balanced trees under the hood to allow for efficient searching. Common associative containers are:

• set
• map
• multiset
• multimap

set

A set stores unique elements in a sorted order. It automatically eliminates duplicates.

Features:

• Elements are sorted based on a comparison function (default is operator<).
• Each element must be unique.

Example of Using set:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {4, 1, 3, 2, 5};

    // Inserting an element (duplicates will not be inserted)
    s.insert(6);
    s.insert(4);  // This will be ignored since 4 is already in the set

    // Displaying elements using an iterator
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• insert() adds an element to the set. If the element already exists, it will not be added.
• Elements are printed in sorted order.

map

A map is a collection of key-value pairs where each key is unique. It stores elements in sorted order based on the key.

Features:

• Keys must be unique.
• Elements are stored in sorted order by the key.

Example of Using map:

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

    // Inserting key-value pairs
    m[4] = "four";

    // Accessing elements using keys
    for (const auto& pair : m) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Explanation:

• The map<int, string> stores key-value pairs, where the key is of type int and the value is of type string.
• You can access elements using keys, and they are automatically sorted by the key.

---

3. Unordered Containers

Unordered containers store elements using hash functions. The key benefit is faster access times for finding elements, though the elements are not stored in any particular order.

Common unordered containers are:

• unordered_set
• unordered_map
• unordered_multiset
• unordered_multimap

unordered_set

An unordered_set is similar to a set but uses a hash table for storing elements.

Features:

• Elements are stored in an unordered fashion.
• Provides fast access based on hash functions.

Example of Using unordered_set:

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> us = {5, 3, 2, 1, 4};

    // Adding elements to the unordered set
    us.insert(6);
    us.insert(2);  // This will be ignored since 2 is already in the set

    // Displaying elements
    for (int elem : us) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

• The unordered_set stores elements without sorting them.
• Duplicate elements are not added to the set.

---

4. Container Adapters

Container adapters provide a different interface to existing containers. These are typically used to implement specific data structures like stacks, queues, and priority queues.

Common container adapters:

• stack
• queue
• priority_queue

stack

A stack follows the Last In, First Out (LIFO) principle, where the last element added is the first to be removed.

Example of Using stack:

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // Adding elements to the stack
    s.push(10);
    s.push(20);
    s.push(30);

    // Displaying and removing elements
    while (!s.empty()) {
        cout << s.top() << " ";  // Accessing top element
        s.pop();  // Removing top element
    }
    cout << endl;

    return 0;
}

Explanation:

• push() adds an element to the stack.
• top() accesses the top element, and pop() removes it.

---

---