Lists In STL

Get To Know All About Lists In STL Along With Its Implementation.

Lists are sequential containers. Lists contain elements in non-contiguous locations. We have discussed arrays and vectors in our previous tutorials.

In case of the array and vector containers, as these containers store data in contiguous memory, insert operation in the middle of these containers proves to be very costly as we have to shift the existing elements accordingly to make space for the new element.

=> See Here To Explore The Full C++ Tutorials List.

Overview

The list is a container that overcomes this drawback of the array and vector containers. It allows us to insert elements anywhere in the list without causing much of an overhead. But lists are slower than vectors as far as traversal is concerned.

In this tutorial, we will see the implementation of lists in STL along with the various operations of traversal, manipulations and accessing list with examples.

Note that a majority of list operations are similar to those of vectors and hence readers who have already read our tutorial on vectors will not have problems in interpreting list concepts.

Declaration And Initialization

For implementing list container and using all its benefits, we need to include a header file <list> in our program.

#include <list>

The general declaration for list container is

std::list<objectType> listName;

For Example, we can declare a list named ‘mylist’ of type int as follows:

std::list<int> mylist;

We can also initialize list at the time of declaration or add elements to it using one of the operations it supports.

Let’s see how we can initialize the list we created above.

std::list<int> mylist = {1, 1, 2, 3, 5};

The above initialization will be laid out in memory as shown below:

Once we initialize the list, we can access the elements of a list using an iterator. The Iterator functions ‘begin’ and ‘end’ help us to traverse through the list elements.

Note: Iterator for the list also supports other iterators like reverse iterators (rbegin, rend), constant iterators (cbegin, cend) and constant reverse iterators (crbegin, crend) and can be used in a similar way like vectors.

Following example shows this.

#include <iostream>
#include <string>
#include <list>
#include <iterator>
using namespace std;
int main()
{
   list<int> mylist = {1, 1, 2, 3, 5};
   cout<<”List elements are: “;
   list<int>::iterator it;
   for(it=mylist.begin();it!=mylist.end();++it)
  cout<<*it<<” “;
}

Output:

List elements are: 1 1 2 3 5

Thus in the above example, we have declared a list of the Fibonacci sequence. Next, we declare an iterator of the same type as list and then using for loop, we print the list contents from start to end.

Now let us jump to the operations or functions that list container in STL provides us with.

List Operations

• Insert: Used to insert an element at the given position. Returns an iterator pointing to the first element inserted.

insert(pos, num_elem, elem)

Where,

pos=> Position at which new elements are to be inserted.
num_elem=> Number of elements to be inserted; defaults to 1.
elem=> Actual value to be inserted.

Let us understand the insert function by taking an Example.

#include <iostream>
#include <list> // for list operations
using namespace std;

int main()
{
   list<int> mylist = {1,1,2};
   list<int>::iterator it = mylist.begin();
   // iterator to point to 4th position
   advance(it,` 3);
   // inserts 3 at 4th position
   mylist.insert(it, 3);
   cout << "The list after inserting"
   << " 1 element using insert() is : ";
   for (list<int>::iterator i = mylist.begin();i != mylist.end();i++)
      cout << *i << " ";
      cout << endl;
}

Output:

The list after inserting 1 element using insert() is : 1 1 2 3

This is an example to insert only one element at the 4^th position in the list which is eventually the last position. Hence, first, we have a list for which we have defined the iterator pointing to the beginning of the list. Then we shift this iterator to the 4^th position and then call insert to insert 1 element.

We can also insert more than one element, by specifying the second parameter in the insert function. Whenever it is not specified, it defaults to 1.

• push_back: Adds a new element at the end of the list.
• push_front: Adds a new element at the beginning of the list.

Let us see an example that demonstrates the usage of push_back and push_front functions.

#include <iostream>
#include <string>
#include <list>
#include <iterator>
using namespace std;
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout  <<*it<<'\t';
      cout  << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3};
   cout<<"List elements are: ";
   printlist(mylist);
   mylist.push_front(0);
   mylist.push_back(5);
   cout<<"\nList contents after push_front and push_back: ";
   printlist(mylist);
}

Output:

List elements are: 1            1           2               3

List contents after push_front and push_back: 0              1                 1               2              3                  5

In this example, we first create and list all two elements to it, one each at the front and at the back using push_front and push_back functions respectively. The output shows the changed list after both the functions are executed.

• pop_back: Removes the last element in the list thereby shrinking the list size by 1.
• pop_front: Removes the first element in the list thereby shrinking the list size by 1.

The following example shows the usage of pop_back and pop_front operations of the list.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
     cout <<*it<<'\t';
     cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   mylist.pop_front();
   mylist.pop_back();
   cout<<"\nList contents after push_front and push_back: ";
   printlist(mylist);
}

Output:

List elements are: 1 1 2 3 5

List contents after push_front and push_back: 1 2 3

As described in the operations’ definition each of the operations pop_front and pop_back removes the element from front and back of the list i.e. first and the last element of the list respectively and thus every time it reduces the size of the list by 1.

• size: Returns the size of the list i.e. number of elements in the list.
• empty: Checks if the list is empty.
• erase: Removes an element or range of elements from the list.
• clear: Removes all the elements from the list by making it to 0 size.

Given below is an example to demonstrate the usage of all the above functions i.e. size, empty, erase and clear.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   cout<<"size of the list: "<<mylist.size();
   list<int>::iterator it = mylist.begin();
   if(!(mylist.empty()))
      {
         mylist.erase(it);
         cout<<"\nList after erase first element: ";
         printlist(mylist);
         cout<<"New size of the list: "<<mylist.size();
       }
   else
      cout<<"list is empty";
      
      mylist.clear();
      cout<<"\nsize of the list after clear: "<<mylist.size();
}

Output:

List elements are: 1 1 2 3 5
size of the list: 5
List after erasing first element: 1 2 3 5
New size of the list: 4
size of the list after clear: 0

The above program demonstrates all the four functions related to the capacity of the list. We see that the list size decreases by 1 when we erase 1 element of the list. While when we call a clear operation on the list, the size is 0 which means all the elements in the list are removed.

• front: Returns value of the first element of the list.
• back: Returns value of the last element of the list.
• swap: Swaps the contents of one list with the contents of another list of same size and type.
• reverse: An algorithm that reverses the list.
• sort: Sorts the given list.

The below example demonstrates the usage of the front, back, reverse, sort and swap functions.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 2, 3, 5};
   cout<<"List elements are: ";
   printlist(mylist);
   cout<<"\nFront of the list: "<<mylist.front();
   cout<<"\nBack of the list: "<<mylist.back();
   cout<<endl;
   cout<<"\nReversed List: ";
   mylist.reverse();
   printlist(mylist);
   //swap two lists
   list<int> oddlist = {1,5,9,3,7};
   oddlist.sort();
   cout<<"\nContents of odd list:";
   printlist(oddlist);
   mylist.swap(oddlist);
   cout<<"After swapping\n mylist: ";
   printlist(mylist);
   cout<<"Oddlist : ";
   printlist(oddlist);
}

Output:

List elements are: 1          1            2             3              5

Front of the list: 1
Back of the list: 5

Reversed List: 5                3              2              1              1

Contents of odd list: 1           3            5               7           9

After swapping

mylist: 1            3              5             7                9
Oddlist : 5         3             2             1                  1

In this code, first, we print the front and back values of the list mylist. Then this list is reversed and the reversed list is printed. After that, we define one more list of odd numbers which is not in any order and we call the ‘Sort’ algorithm to sort this list. Then we swap the two lists using the swap function and print the exchanged lists.

• splice: This function is used to transfer the contents of one list to another list at a specified position.

Both the lists must be of the same type.

splice(position, list);

where,

position => Position at which the list contents are to be transferred.
list => List whose elements are to be transferred.

The example given below shows the usage of the splice function.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;
void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1, 8,13};
   cout<<"List elements are: ";
   printlist(mylist);
   list<int> seclist = {2,3,5};
   cout<<"list to be spliced: ";
   printlist(seclist);
   list<int>:: iterator it = mylist.begin(); it ++; it++;
   mylist.splice(it,seclist);
   cout<<"\nList contents after splicing at position 2: ";
   printlist(mylist);
}

Output:

List elements are: 1           1               8                   13
list to be spliced:  2           3               5

List contents after splicing at position 2: 1       1          2           3            5            8            13

The example shows that we use two lists. First, the iterator for mylist is moved to two positions and then the splice function is called to transfer the contents of the second list to the third position of the first list.

• merge: Unlike splice function that can be used to transfer contents of one list to another at a specific position, merge operation directly merges two lists to form one single list. For merge operation, both the lists need to be in sorted order.

Given below is an example to demonstrate the merge function.

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

void printlist(list <int> mylist)
{
   list <int> :: iterator it;
   for(it = mylist.begin(); it != mylist.end(); ++it)
      cout <<*it<<'\t';
      cout << '\n';
}
int main()
{
   std::list<int> mylist = {1, 1,2,3,5,8};
   list<int> seclist = {4,6,7};
   cout<<"First List: ";
   printlist(mylist);
   cout<<endl;
   cout<<"Second List: ";
   printlist(seclist);
   mylist.merge(seclist);
   cout<<"\nList contents after merging two lists:\n ";
   printlist(mylist);
}

Output:

First List: 11               2                  3                   5                    8
Second List: 4           6                  7

List contents after merging two lists:
1       1        2         3          4             5             6           7           8

Thus in the above program, we have two lists that are sorted. We call merge operation on these two lists. The resultant list is a sorted list containing the elements of both lists.

Conclusion

We have come to the end of this tutorial on Lists in STL. We hope this tutorial would have given you immense knowledge on Lists in STL.

=> Check Here To See A-Z Of C++ Training Tutorials Here.