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:
- Containers
- Algorithms
- Iterators
Containers
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
Sequence 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>.
Associative Containers
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.
Derived Containers
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.
