C++ STL - Containers : One Shot

Welcome to our deep dive into the world of C++ Standard Template Library (STL) containers where we’ll explore the various types of STL containers, their unique features

Now we have already gotten basic ideas about STL and it’s components in C++ STL : one shot

So let’s start with this blog which will help us choose our containers wisely

What is a Container ?

• holder object that stores other objects as elements. It is used to implement different data structures
• implemented as class templates (templates use data types as parameters), allowing greater flexibility in the types supported as elements
• manage storage space for its elements and provide member functions to access them directly or through iterators

Types of Containers

1. Sequence Containers

• Accessed sequentially via their position.
• It preserves the insertion order of elements.
• Internally implemented as arrays or linked lists.

Types of sequence containers :

a. Array

• Sequential homogeneous containers of fixed size.
• The elements are stored in contiguous memory locations.

Syntax:

array<object_type, size> array_name;

b. Vector

• Dynamic arrays, allow the insertion and deletion of data from the end. They can grow or shrink as required.
• Their size is not fixed, unlike arrays.

Syntax:

vector<object_type> vector_name;

c. Deque (double-ended queue)

• Allows inserting and deleting from both ends.
• They are more efficient than vectors in case of insertion and deletion.
• Its size is also dynamic.

Syntax:

deque<object_type> deque_name;

d. List

• Allows insertions and deletions from anywhere.
• It is a doubly linked list.
• They allow non-contiguous memory allocation for the elements.

Syntax:

list<object_type> list_name;

e. Forward List

• Allows iteration in only a single direction
• They are implemented as singly linked list in STL in C++.
• It uses less memory than lists.

Syntax:

forward_list<object_type> forward_list_name;

2. Associative Containers

• Ordered (sorted) container that provides a fast lookup of objects based on the keys, unlike a sequence container which uses position.
• A value is stored corresponding to each key.
• Internally implemented as binary tree data structures. This results in logarithmic time operations — 𝑂(log⁡𝑛).

Types of associative containers :

a. Set

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

Syntax:

set<object_type> set_name;

b. Map

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

Syntax:

map<key_object_type, value_object_type> map_name;

c. Multiset

• It is similar to a set but also allows duplicate values.

Syntax:

multiset<object_type> multiset_name;

d. Multimap

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

Syntax:

multimap<key_object_type, value_object_type> multimap_name;

3. Unordered Associative Containers

• Unsorted version of Associative Container.
• Insertion order is not maintained. Elements are in random order.
• Internally implemented as a hash table data structure. This results, on average, in constant time operations — 𝑂(1)

Types of Unordered Associative Containers :

a. Unordered Set

• It is used to store unique elements.

Syntax:

unordered_set<object_type> unordered_set_name;

b. Unordered Map

• It is used to store unique key-value pairs.

Syntax:

unordered_map<key_object_type, value_object_type> unordered_map_name;

c. Unordered Multiset

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

Syntax:

unordered_multiset<object_type> unordered_multiset_name;

d. 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;

4. Container Adapters

• 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 adaptor independently of the underlying container class used.
• Values are not directly initialized but with the help of other supported methods.

Types of Container Adapters :

a. Stack

• 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.

Syntax:

stack<data_type> stack_name;

b. Queue

• 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.

Syntax:

queue<data_type> queue_name;

c. Priority Queue

• It is similar to a queue, but every element has a priority value.
• This value decides what element is present at the top, which is the greatest element.
• 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;

Operations on containers

For understanding of the time and space complexities of the operations of these containers check out these resources :

https://leetcode.com/discuss/interview-question/1328286/C%2B%2B-STL-Guide-or-STL-in-one-shot-Operations-and-Time-Complexities

https://www.hackerearth.com/practice/notes/standard-template-library/