My Blog
Articles related to programming, computer science, technology and research.

07/12/2016 Categories: C++ Programming. No Comments on Standard Template Library

Introduction

 

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:

  1. Containers
  2. Algorithms
  3. Iterators

 

Containers

 

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:

  1. Sequence Containers
  2. Associative Containers
  3. 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 of 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 pair of key and value. Key is used for indexing and sorting the values. Values can be manipulated using keys. Map does not allows 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 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 highest priority.

 

Algorithms

 

The STL algorithms contains several functions that can be reused to perform several operations on the containers. Although each container provided basic functions to manipulate the data, STL provides around 60 algorithms (functions) which provided extended or complex functionality. These algorithms are categorized into five types as follows:

Retrieve or non-mutating algorithms

non-mutating-algorithms

 

Mutating Algorithms

mutating-algorithms

 

Sorting Algorithms

sorting-algorithms

 

Set Algorithms

set-algorithms

Relational Algorithms

relational-algorithms

 

 

Iterators

 

An iterator is an entity that allows programs to traverse the data in a container. Iterators are generally used to traverse the elements in a container. All containers except derived containers provides two types of containers:

 

container :: iterator (which provides a read/write iterator)

container :: const_iterator (which provides a read-only iterator)

 

STL provides five types of iterators as shown below for all containers except for derived containers.

types-of-iterators

 

All container classes provides four basic functions which can be used with the assignment operator. These functions are as follows:

begin() – Returns an iterator to the beginning of elements in the container.

cbegin() – Returns a read-only iterator to the beginning of elements in the container.

end() – Returns an iterator just past the end of the elements.

cend() – Returns a read-only iterator just past the end of the elements.

 

Vector

 

A vector is like a dynamic array where all the elements are stored contiguously. Elements can be added or removed at run-time as and when needed. Vector provides the following functions for working with the data stored in it:

vector-functions

 

Following program demonstrates working with a vector:

 

List

A list (linked list) is a container in which an element points to next element and previous element. Direct access is not possible in a list. To reach nth element, we have to traverse all n-1 elements. The list container provides the following functions:

list-functions

Following program demonstrates working with a list:

 

Maps

 

A map is like an associative array where each element is made of a pair. A pair contains a key and a value. Key serves as an index. The entries in a map are automatically sorted based on key when data is entered. Map container provides the following functions:

map-functions

 

Following program demonstrates working with a map:

 

Suryateja Pericherla

Suryateja Pericherla

Hello, I am Suryateja Pericherla working as an Asst. Professor in CSE department at Vishnu Institute of Technology. I write articles to share my knowledge and make people knowledgeable regarding certain topics.
Suryateja Pericherla

Latest posts by Suryateja Pericherla (see all)

Related Links:

Leave a Reply

Your email address will not be published. Required fields are marked *

Scroll Up