STL Containers and iterators


In this post we will see the well known topics of C++ featuring STL containers and iterators.We will also see the types of STL containers and the types of iterator that is used for performing operations on the containers.

STL container and iterator

STL stands for “Standard Template Library“.It is the heart of Standard C++ which is built using templates.There sole purpose is to provide an environment for efficient management of resources.In C++ programming all the libraries categorized as STL has one basic common purpose: memory management.

Frankly speaking,by STL container we simply mean a bunch of libraries consisting of template classes with constructors,destructors and member functions.So like any other classes we will implement them in our program using their objects.Since the containers are template it provide certain flexibility in the type they can be used for ranging from built-in type to template class object.Not only that,besides taking advantage of their member functions to manipulate the data they store we can also use the functions provided in the header’s <algorithm> to carry out more task vividly.

There are many STL containers in C++.There difference lies in their nature to handle the data they store differently.No doubt their distinct nature origin from the varying algorithm they employ to handle the data.If we want to classify the various STL depending on the algorithm or their basic properties they exhibit then we can do so in three types.The three types of STL container is mentioned below.


i::Sequence containers

The way sequence containers handle the data is same as how data are handled by an array.This means when we insert data into the sequence containers they are store in consecutive to one another and in the order they are inserted.For instance if we insert four elements:element1 , element2 ,element3 , element4 ,one after the other the order in which they are inserted is the order in which they will found in the memory.

sequence container

The STL containers which exhibit this behavior are:

i)array (added in C++11)
ii)vector
iii)deque
iv)list and
v)forward_list (added in C++11)

The STL <array> and <forward_list> are added in C++11.Here the <array> header’s is not referring to the normal array type.They are completely different:one is a class template and the other is just a built-in type.

An example is shown below describing the nature of sequence container.We will use the container vector to perform a simple input and output of data.

#include <vector>
#include <iostream>

using namespace std;

int main( )
{
vector<int> vecStorage ; //a vector container to store int data

vecStorage.push_back( 23 ) ; ///inserting integer into the container
vecStorage.push_back( 389 ); ///inserting integer into the container
vecStorage.push_back( 13 ); ///inserting integer into the container
vecStorage.push_back( 200 ); ///inserting integer into the container

//outputting the data from the containers
for ( int i=0; i<4 ; ++i )
{
cout<< vecStorage[i] << endl ; ///accessing the element
}

return 0;
}

The output is,

23
389
13
200

The order of the value outputted is in the exact same order as it was inserted into the container.

Note:The sequence containers implement either array or linked lists method to store the data in the container.


 


Stop wasting time,earn money($$$) from your website-Join Now!

ii:: Associative container

Associative containers unlike the sequence container store data using some sorting algorithm.Since they implement a sorting algorithm the position of the data is not in the order as it was inserted into the container.To sort the data they depend on a factor known as key.The key can be any built-in type and the magnitude of the key will determine the position of the data associated with it.

In some of the associative containers when inserting element they accept two values also known as first value and second value.For such containers the first value is the key factor in sorting the elements of that container.If the container accept only one element then the value inserted itself is the key factor in sorting the elements of the container.

The associative containers are usually implemented as binary trees which involve arranging the elements in a tree structure.

associative containers

The containers that is categorized under this type are:

i)set
ii)multiset
iii)map and
iv)multimap

In the code example shown below the containers set and map are utilized.We will also use the function ‘insert( )‘ to insert elements into the container.

#include <set>
#include <map>
#include <iostream>

using namespace std ;

int main( )
{
set<int> st ;

///inserting elements into the set container
st.insert( 78 ) ;
st.insert(19) ;
st.insert( 0) ;
st.insert( 56 ) ;

//outputting the elements
for(auto elem :st )
{
cout<< elem << ” ” ;
}

map<int , string > mp ;

///inserting elements into the set container
mp.insert({ 4 , “new” }) ;
mp.insert({ 2 , “Happy” }) ;
mp.insert({ 12 , “???” }) ;
mp.insert({ 7 , “year” }) ;

//outputting the elements
for(auto elem : mp )
{
cout<< elem.first << ” ” << elem.second << endl ;
}

return 0 ;
}

Let us examine the output of the <set> container first.The output you will get is

0 19 56 78

This is not the actual order in which we have inserted the elements and the output is also sorted in ascending order of the value.

The second output which is the elements store in <map> is,

2 Happy
4 new
7 year
12 ???

It is also sorted in ascending order of the first value.So you can see in associative containers the output is not in the order of the insertion but rather it is sorted depending on the key value.





iii::Unordered associative containers

This type of containers does not store the data either sequentially or in binary tree format.It store the data randomly without implementation of any specific algorithm or pattern.For instance if you insert five elements into such container the output you will get is the elements arranged in some random manner.

Unordered containers are implemented as hash tables.And the data they store are randomly distributed in the containers as shown below.

unordered associative container

The STL containers included under unordered associative containers are:

i)unordered_set
ii)unordered_multiset
iii)unordered_map and
iv)unordered_multimap

A program using the unordered_set is shown below.

#include <unordered_set>
#include <iostream>

using namespace std;

int main( )
{
unordered_set<int> unset;

unset.insert( 100 ); //insert first element
unset.insert( 20 ); //insert first element
unset.insert( 0 ); //insert first element
unset.insert( 90 ); //insert first element
unset.insert( 9 ); //insert first element

///outputting the elements in the container
for(auto elem:unset )
{
cout<<elem << endl ;
}

return 0 ;
}

The output is,

9
100
0
20
90

Note the random output generated will vary from compiler to compiler and from time to time.




Iterators

The role of iterators in the application of STL containers is similar to the role of pointers while using the normal variables.This basically means by declaring an iterator for a container we can navigate the elements in the container using the iterator.So it ultimately follows that using iterator we can modify or operate on a specific element in the container if the need arises.Not only that you will see that iterator has a bigger role to play as we use STL container for our varying needs.Needless to say that iterator make the STL container more dynamic and also the code utilizing the STL container more robust.

Considering that iterator is a pointer for the STL containers,we can perform the fundamental operations on them like:

*incrementing the iterator using ‘++‘ operator
*decrementing the iterator using ‘‘ operator

Other relational operators like ‘==’ or ‘!=’ or the assignment operator can be also operated on it.

An example is given below which utilizes iterator to access the value in the container <set>.The function begin( ) denotes the beginning of the container and the function end() denotes the position in the container next to the last element.So end() does not actually point to any valid storage of the container.

#include <set>
#include <iostream>

int main( )
{
set<int>st ;
set<int>::iterator stIt ; ///declaring an iterator for set class

st.insert( 12 ) ;
st.insert( 10 ) ;
st.insert( 99 ) ;
st.insert( 45 ) ;
st.insert( 67 ) ;

for( stIt=st.begin( ) ; stIt!=st.end() ; ++stIt )
{
cout<< *stIt << endl ;
}

///Accessing the specific element in container
stIt=st.begin( ) ; //iterator should point to the beginning of the container first

advance( stIt , 2 ) ; ///Make stIt iterator point to third element

cout<< *stIt << endl ;

return 0;
}

To access the third element in the container we use the advance() function and make the iterator point to the desired position-in this case third position- in the container.Note here the second argument provided is ‘3-1’ to access the element in 3rd position.

There are many more functions like the advance() in C++ to help carry out various operation using iterator.We will have detail discussion on each of these functions when we discuss the headers file <iterator> and <algorithm>.


Types of iterator

There are two types of iterator which help manipulate the STL container.

i)container::iterator -: Such iterator allow reading and writing of data to the container.It is helpful if you want to not only read data from the value but also change it according to your needs.

ii)container::const_iterator -: Such iterator is meant only for reading data from the container.You are not allow to change the value of the container using this type of iterator.

The difference between these two iterator types is shown below.

#include <deque>
#include <include>

using namespace std;

int main( )
{
deque<int> dq ;

dq.push_back(89) ;
dq.push_back(78) ;
dq.push_back( 90) ;

deque<int> ::iterator Idq ; ///non-const iterator
Idq=dq.begin( ) ;

*Idq =8998 ; //changing the first value to 8998
*(++Idq) =780 ; //changing the second value to 780

for(auto elem:dq )
{
cout << elem << endl ;
}

deque<int> ::const_iterator CIdq ; ///const iterator

CIdq=dq.begin() ;

*CIdq=7526 ; ///error read only

cin.get( ) ;
return 0 ;
}

In case of const_iterator we cannot use it to change the value in the container.So we can use it only for reading values from the container.

STL container and iterator are very much related to one another.Every container has an iterator of it’s own so we can use iterator without including the library <iterator>.But it is better that we include this library whenever we use iterator as it provides more functionality including those not found in the container