Containers: The Building Blocks of STL

Containers in the STL are objects that store and organize data. They come in various forms, each tailored to different use cases and scenarios. Understanding the nuances of these containers is key to writing efficient and maintainable C++ code.

• Container is a holder object that stores other objects as elements. It is used to implement different data structures.
• They are implemented as class templates.
• The containers manage storage space for its elements and provide member functions to access them directly or through iterators.
• They replicate the most commonly used data structures like queues (queue), dynamic array (vector), stacks (stack), linked list (list), heaps (priority_queue), trees (set), associative arrays (map), and many others.

Types of Containers

There are three types of Containers.

1️⃣ Sequence Containers

Sequence containers maintain the order of elements based on the sequence in which they are inserted. These containers are ideal when you need to preserve the order of elements and access them sequentially.

• Sequence containers implement data structures that can be accessed sequentially via their position.
• It preserves the insertion order of elements.
• These are internally implemented as arrays or linked lists.

1. Vector

Vectors are dynamic arrays, allowing the insertion and deletion of data from the end. They can grow or shrink as required. Hence their size is not fixed, unlike arrays. It can resize itself automatically.

Characteristics:

• A dynamic array that automatically resizes itself.
• Provides constant-time random access to elements.
• Efficient for sequential access and appending elements.

Usage: Ideal when you need a resizable array, and random access is required.

Syntax:

vector<object_type> vector_name;

#include <vector>
std::vector<int> myVector = {1, 2, 3, 4, 5};

2. List (Doubly Linked List)

The list is a sequence container that allows insertions and deletions from anywhere. It is double linked list. They allow non-contiguous memory allocation for the elements.

Characteristics:

• Doubly-linked list for efficient insertion and deletion operations.
• Slower random access but faster insertions and removals.
• Does not support random access; elements must be accessed sequentially.

Usage: Suitable for scenarios where frequent insertion and deletion operations occur, especially in the middle of the sequence.

Syntax:

list<object_type> list_name;

#include <list>
std::list<int> myList = {10, 20, 30, 40, 50};

3. Deque (Double-Ended Queue)

Deque is double-ended queue that allows inserting and deleting from both ends. They are more efficient than vectors in case of insertion and deletion. Its size is also dynamic.

Characteristics:

• Double-ended queue that allows fast insertion and deletion at both ends.
• Similar to vectors but more efficient for frequent front and back operations.
• Slower than a vector for random access but still provides efficient index-based access.

Usage: Useful when you need fast access and modifications at both ends of the sequence.

Syntax:

deque<object_type> deque_name;

#include <deque>
std::deque<int> myDeque = {1, 2, 3, 4, 5};

4. Array

• Arrays are sequentially homogeneous containers of fixed size. The elements are stored in contiguous memory locations.
• A fixed-size array, providing a more controlled alternative to raw arrays.
• Size is determined at compile time.

Syntax:

array<object_type, size> array_name;

#include <array>
std::array<int, 5> myArray = {1, 2, 3, 4, 5};

5. Forward List

Forward Lists are introduced from C++11. They are implemented as singly linked list in STL in C++. It uses less memory than lists and allow iteration in only a single direction

Syntax:

forward_list<object_type> forward_list_name;

2️⃣ Container Adapters

• STL in C++ also consists of a special type of container that adapts other containers to give a different interface with restricted functionality. Hence the name Container Adapters.
• The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adapter independently of the underlying container class used.
• Unlike other containers, values are not directly initialized but with the help of other supported methods.

1. Queue

A queue is a container that provides First-In First-Out access. The insertion is done at the rear (back) position and deletion at the front. It is implemented on top of a deque by default.

• Adapts a container to provide a first-in, first-out (FIFO) queue.
• Typically implemented using deque or list.

Syntax:

queue<data_type> queue_name;

#include <queue>
std::queue<int> myQueue;

2. Stack

A Stack is a container that provides Last-In-First-Out (LIFO) access. All the operations occur at the same place called top of the stack. It is implemented on top of a deque by default.

• Adapts a container to provide a last-in, first-out (LIFO) stack.
• Typically implemented using deque or vector.

Syntax:

stack<data_type> stack_name;

#include <stack>
std::stack<int> myStack;

3. Priority Queue

A priority Queue is similar to a queue, but every element has a priority value. This value decides what element is present at the top, which is, by default, the greatest element in the case of STL in C++. This is similar to the max heap data structure. It is implemented on top of the vector by default.

Syntax:

priority_queue<object_type> priority_queue_name;

3️⃣ Associative Containers

Associative container is an ordered (sorted) container that provides a fast lookup of objects based on the keys, unlike a sequence container which used position. It automatically sort elements as they are inserted based on a key.

• A value is stored corresponding to each key.
• They are internally implemented as binary tree data structures. This results in logarithmic time operations – O(log n).

1. Set

They are used to store unique elements. The data is stored in a particular order (increasing order, by default).

Characteristics:

• Collection of unique, sorted elements.
• Implemented as a balanced binary search tree.

Usage: Useful when you need a collection of unique elements that are always sorted.

Syntax:

set<object_type> set_name;

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

2. Map

The map contains elements in the form of unique key-like pairs. Each key is associated with only one value. It establishes a one-to-one mapping. The key-value pairs are inserted in increasing order of the keys.

Characteristics:

• Key-value pairs where keys are unique.
• Implemented as a balanced search tree.

Usage: Ideal when you need to associate keys with values, and fast access to these pairs is required.

Syntax:

map<key_object_type, value_object_type> map_name;

#include <map>
std::map<std::string, int> myMap = {{"one", 1}, {"two", 2}, {"three", 3}};

3. Multiset

Multiset is similar to a set but also allows duplicate values.

Characteristics:

• Allow duplicate keys in the set and map, respectively.
• Implemented as a balanced search tree.
• Maintains order of elements.

Usage: Suitable when you need a sorted collection of elements that can have duplicates.

Syntax:

multiset<object_type> multiset_name;

#include <set>
#include <map>
std::multiset<int> myMultiset = {1, 2, 2, 3, 3, 3};
std::multimap<std::string, int> myMultimap = {{"one", 1}, {"one", 2}, {"two", 3}};

4. Multimap

Multimap is similar to a map but allows duplicate key-value pairs to be inserted. Ordering is again done based on keys.

Characteristics:

• Similar to std::map, but allows duplicate keys.
• Stores key-value pairs where multiple keys can map to different values.

Usage: Useful when you need to associate multiple values with the same key.

Syntax:

multimap<key_object_type, value_object_type> multimap_name;

4️⃣ Unordered Containers

Unordered Associative Container is an unsorted version of Associative Container. It is important to note that insertion order is not maintained. Elements are in random order. These are internally implemented as a hash table data structure. This results, on average, in constant time operations – O(1).

1. Unordered Set

It is used to store Unique elements.

Characteristics:

• Similar to set, but elements are unordered.
• Implemented as a hash table for fast access.
• Provides average O(1) time complexity for search, insertion, and deletion operations.

Usage: Best suited for scenarios where you need a collection of unique elements, and order does not matter.

Syntax:

unordered_set<object_type> unordered_set_name;

#include <unordered_set>
std::unordered_set<int> myUnorderedSet = {4, 2, 1, 3, 5};

2. Unordered Map

It is used to store unique key-value pairs.

• Similar to map, but elements are unordered.
• Implemented as a has table for fast access.
• Provids average O(1) time complexity for search, insertion, and deletion operations.

Usage: Ideal when you need to map keys to values without caring about the order.

Syntax:

unordered_map<key_object_type, value_object_type> unordered_map_name;

#include <unordered_map>
std::unordered_map<std::string, int> myUnorderedMap = {{"one", 1}, {"two", 2}, {"three", 3}};

3. Unordered Multiset

It is similar to an unordered set, but the elements need not to be unique.

• Allow duplicate keys in the set and map, respectively.
• Implemented as a hash table for fast access.

Syntax:

unordered_multiset<object_type> unordered_multiset_name;

#include <unordered_set>
std::unordered_multiset<int> myUnorderedMultiset = {1, 2, 2, 3, 3, 3};

4. Unordered Multimap

It is similar to an unordered map, but the duplicate key-value pairs can be inserted here.

Syntax:

unordered_map<key_object_type, value_object_type> unordered_map_name;

#include <unordered_map>
std::unordered_multimap<std::string, int> myUnorderedMultimap = {{"one", 1}, {"one", 2}, {"two", 3}};