The Standard Template Library (STL) is a collection of components to implement data structures and frequently used operations on data. Three major components in STL are:
A container is an object that can:
- Store data.
- Define how the data can be stored and manipulated using operations.
Containers are similar to data structures and are implemented using templates. So, a container can store data of different types. Examples of containers are Vector, List, Dequeue, Set, MultiSet, Map, MultiMap, Stack, Queue, PriorityQueue etc.
Containers are of three types:
- Sequence Containers
- Associative Containers
- Derived Containers
Data is stored in a linear fashion. Each element is related to other elements by its position. Elements can be accessed using an iterator. Examples of sequence containers are Vector, List, and Dequeue.
Vector: Dynamic array that allows insertion and deletion of elements at any position. Elements in a vector are contiguous. Allows direct access of an element. Defined in header file <vector>.
List: A bi-directional list that allows insertion and deletion of elements at any position. Elements in a list are not contiguous. Defined in header file <list>.
Dequeue: A double-ended queue which allows insertion and deletion at both ends. Allows direct access to any element. Defined in header file <deque>.
There is no sequential ordering of elements. Data is sorted while giving input. Supports direct access of elements using keys. Data is stored as a tree. They facilitate fast searching, insertion, and deletion. Not efficient for sorting and random access. Examples of associative containers are Set, multiset, Map, and multimap.
Set and multiset: Store multiple elements and provide functions to manipulate them using their keys. A set does not allow duplicate elements. But a multiset allows duplicate elements. They are defined in the header file <set>.
Map and multimap: Stores the elements as a pair of key and value. The key is used for indexing and sorting the values. Values can be manipulated using keys. The map does not allow multiple values for a key. But a multimap allows multiple values for a key. They are defined in the header file <map>. An example for multimap is a dictionary.
These containers are created from sequence containers. They don’t support iterators. As there are no iterators, data cannot be manipulated. Examples of derived containers are Stack, Queue, and PriorityQueue.
Stack: Data is stored in Last In First Out (LIFO) order. Insertion and deletion of elements can be done only at one end.
Queue: Data is stored in First In First Out (FIFO) order. Insertion is done at one end and deletion is done at the other end.
PriorityQueue: The first element to be taken out is the element with the highest priority.
Take your time to comment on this article.