The Standard Template Library (STL) is one of the most essential features of C++. It has very much grown in recent years. Basically, the Standard Template Library provides templatized, general-purpose classes as well as methods. These classes and functions/methods implement several popular and most commonly used algorithms as well as data structures. For example, it includes support for lists, vectors, stacks and queues. Furthermore, it also describes several routines, which access them. As the STL is built with template classes, so the data structures and algorithms can be applied to almost any data type.

There are 4 fundamental items at the core of Standard Template Library (STL):

  • Iterators
  • Containers
  • Function Objects
  • Algorithms

The above-mentioned elements work with each other and offer appreciable solutions to many complex programming problems. Read on below for the description of these items:

Container is an object, which holds data of same type. While, there are multiple kinds of containers present. Some of them are general purpose, while others adapt some other containers to match an ADT. Following are the example of a few STL containers:

  • Deque: deque is the abbreviation of double ended queue. Hence, it provides a double ended queue. The following 2 containers by default adapt deque:
    • stack is a simple LIFO (Last in First Out) stack
    • queue is a simple FIFO (First in First Out) queue
  • vector is a dynamic array
  • list is an unsorted doubly-linked list

Each container class defines its own set of methods/functions, which are applicable to the container. Such as, a list container includes the methods delete, insert, and merge for elements. Similarly, each container defines its own set of functions separately.

Iterators, in simple words are ‘pointers’. Iterators allows you to traverse through the elements of a container in almost the same way you use a pointer to traverse through the elements of an array.

Algorithms acts upon the elements of the containers. They have the ability to initialize, sort, search, and transform the contents of the containers. It is important to note that the algorithms never change the size of a container. Moreover, some of the algorithms depends on external functions. While the algorithms are included with the header ‘algorithm’ header.

Functions are objects that includes an overloaded operator ’()’. These objects, or the classes of such objects, are usually used to modify the behavior of a container or as arguments to STL algos. You might have used a function object to alter the hashing function of a hash table based container. The function objects of a STL are included in the header ‘functional’.

An STL List

Lists are sequence containers. List allows constant time insert as well as delete operations at any point within the sequence. Moreover, it allows iteration in both directions.

The STL’s (Standard Template Library’s) list container is implemented as doubly linked list. While these lists are able to store every element contained in diverse and distinct storage locations. The elements of the list can be dispersed in multiple chunks of memory. Whereas, the container stores essential information to let the sequential access to the data it contains. Lists can expand as well as shrink dynamically as needed from both ends. Furthermore, the storage requirement is automatically fulfilled by the internal allocator.

The order as well is maintained internally where each element of a link is connected to the element preceding it and to the element following it.

Let me summarize some points about the list container before proceeding toward the example and member functions of the list. An STL list container:

  • supports a dynamic bidirectionallinear list
  • does not allow the direct access to the elements it contains just like a C++ array
  • implements a listDS (data structure)
  • can hold data of any type i.e. can be defined as a template class
  • behaves like an unsorted list, which means by default, the order of the list is not maintained. Although, there are methods available for sorting.

Container properties

Sequence

Elements present in the list are ordered in a strict linear sequence. Hence, each element is accessed by their respective location in the given sequence.

Doubly-linked list

In doubly-linked list, each and every element contains the information on how to trace the previous as well as the next elements. It also allows constant time erase and insert functions prior or after a single or range of specific elements, but it does not allow direct random access.

Allocator-aware

An Allocator-aware container employs an allocator object to dynamically cater its storage requirements.

Template parameters

Alloc

It is a type of allocator object, which is used to describe the storage allocation model. Normally, the allocator class template is used that describes the most simple memory allocation model as well as it is value-independent.

T

It depicts the type of the elements.

Member Functions

Following are the member functions you will use with the List:

push_front(c) – This very method adds ‘c’, a new element at the start of the list. For Example

push_back(c) – This method is used to add a new element at the last of the list. In this case ‘c’ will be added at the end of list. For Example

front() – This method returns the reference to the very 1st element present in the list. For example

back() – This method returns the reference to the very last element present in the list. For Example

pop_front() – This method will remove the element from the start of the list, as well as will reduce the size of list by one. You can do it as follows:

pop_back() – This method will removes the element  from the end of the list, as well as will reduce the size of list by one. Consider following example

begin() – This will return the pointer or iterator to the first element of the list. For Example

end() –This method will return the pointer or iterator to the last element of the respective list. For Example

empty() – This function will return ‘1’ if the list is empty and ‘0’ if the list is not empty. For Example

insert() – This function adds a single or range of elements prior the element at a particular position in the specified list . Syntax:

Here,   x is the element to be inserted

T is the type of a list element into the list

iterator is the position specified for the insertion of elements

And the return value is an iterator, which tells the location of the element which is inserted.

Consider the example below

erase() – The erase() method will delete a single element or multiple elements from the list. Consider the following example:

assign() – This will remove the current elements of the list by assigning the  new  elements and resizes the list

remove() – This function will remove all the elements of the list that are exactly equal to the given value. For example

reverse() – This method will simply reverses the list. For Example

size() – This function will return the size of list i.e. how many elements it contains. For example

sort() – This method will simply sorts the list in ascending order. Consider the example below:

Note that, in comparison with other sequence containers, lists usually perform better in extracting, inserting, as well as moving elements at any location within the list for which the pointer has already been attained. Therefore, also in algorithms, which makes an intensive use of such methods or techniques, such as sorting algorithms, a list can perform better.

Consider the example below:

In the given example, I will demonstrate the use of some of the member functions of STL list mentioned above.  In the following program, I will create a list of random integers and after that I will put the list into sorted order. I will show you the output of both sorted and unsorted list:

Here is the possible output of above mentioned program:

I hope you have enjoyed today’s post. I have mentioned the above example with only few member functions included. I have mentioned the small snippets of code with every member function so I am leaving here a task for you to implement all those member functions in your code yourself.

I will be back with some new and exciting posts soon.

Share
Tweet
Share
Pin