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.
What are the main items in STL?
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.
What is a Container?
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.
What is an Iterator?
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.
What are the Algorithms?
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.
What are the Function Objects?
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’.
What is 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:
The push_front(c) Function
This very method adds ‘c’, a new element at the start of the list. For Example
list<int> flist; flist.push_back (5); flist.push_front (11); // 11 5
The push_back(c) Function
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
list<int> flist; flist.push_back (6); flist.push_back (9); flist.push_front (11); // 11 6 9
The front() Function
This method returns the reference to the very 1st element present in the list. For example
list<int> flist; flist.push_front(55); flist.push_back(22); flist.push_back (33); flist.push_back(60); // the elements of list will be as follows: 55 22 33 60 cout << flist.front() << endl; // 55 is the first or front element Output: 55
The back() Function
This method returns the reference to the very last element present in the list. For Example
list<int> flist; flist.push_front(88); flist.push_back(90); flist.push_back (63); flist.push_back(70); // the elements of list will be as follows: 88 90 63 70 cout << flist.back() << endl; // 70 is the last or back element Output: 70
The pop_front() Function
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:
while (flist.size() > 0) // Let flist is your list
{
...
flist.pop_front(); // this will remove all the elements of list
// one by one starting from front
}
The pop_back() Function
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
while (flist.size() > 0) // Let flist is your list
{
...
flist.pop_back(); // this will remove all the elements of list
// one by one starting from back end
}
The begin() Function
This will return the pointer or iterator to the first element of the list. For Example
iterator begin();
The end() Function
This method will return the pointer or iterator to the last element of the respective list. For Example
iterator end();
The empty() Function
This function will return ‘1’ if the list is empty and ‘0’ if the list is not empty. For Example
if (list1.empty())
{
...
}
The insert() Function
This function adds a single or range of elements prior the element at a particular position in the specified list . Syntax:
iterator insert(iterator position, const T& x);
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
flist_iter = find (flist.begin(), flist.end(), 15);
if (flist_iter != flist.end())
{
flist_iter = flist.insert (flist_iter, 22);
cout << "Inserted element " << (*flist_iter) << endl;
}
Output:
Inserted element 22
The erase() Function
The erase() method will delete a single element or multiple elements from the list. Consider the following example:
flist.erase (flist.begin(), flist.end());//this will remove all elements
...
flist_iter = find(flist.begin(), flist.end(), 3); // Search list.
// If the element is found, erase it
if (flist_iter != flist.end())
{
flist.erase(flist_iter);
}
The assign() Function
This will remove the current elements of the list by assigning the new elements and resizes the list
The remove() Function
This function will remove all the elements of the list that are exactly equal to the given value. For example
flist.remove(15); // let flist is list whose elements is to be remove
The reverse() Function
This method will simply reverses the list. For Example
flist.reverse(); // let flist is the list you want to reverse the order
The size() Function
This function will return the size of list i.e. how many elements it contains. For example
// Loop until there are elements in the list.
while (flist.size() > 0) // Let flist is your list
{
...
}The sort() Function
This method will simply sorts the list in ascending order. Consider the example below:
flist.reverse(); // let flist is the list you want to sorting
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.
Example C++ Program – Standard Template Library – List
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:
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> list1;
int j;
//creating a list of 10 elements using random integers
for(j = 0; j < 10; j++)
{
list1.push_back(rand());
}
cout << "Originally created list: " << endl;
// first create an iterator obj
// and make it point to the
// first element of the list
list<int>::iterator p = list1.begin();
while(p != list1.end())
{
cout << *p << " ";
p++;
}
cout << endl;
// now let’s sort our list
list1.sort();
// Displaying sorted list
cout <<"Sorted list:\n";
p = list1.begin(); // pointing the iterator to the first element
while(p != list1.end()){
cout << *p << " " ;
p++;
}
cout << endl;
return (0);
}
Here is the possible output of above mentioned program:
Originally created list: 921 1846 1634 2600 9279 724 478 258 2662 2464 Sorted list: 258 478 724 921 1634 1846 2464 2600 2662 9279
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.