The complete guide to STL. Part 2 - list

Introduction to list

In the second part of the tutorials, we will take a look at the STL list container. The list container implements the double linked list data structure. Unlike the vector container, list occupies uncontiguous memory, an element being accessed only through iterators.

Creating a list. Constructors

In order to use the list container, we must include the <list> header in our code, and, in order to specify that we use template classes from the std namespace, we declare using the std namespace:

#include <list>
using namespace std;

A list is created similar to a vector. In the next examples, we will create lists using the various forms of the constructor, we will show how to use the copy constructor, and also how to use the assign() function to assign values to lists.

// create an empty list (of zero size) capable of holding doubles
list<double> list0;

cout << "Size of list0 is " << list0.size() << endl;

// create a list with 5 empty elements
list<double> list1(5);

cout << "Size of list1 is " << list1.size() << endl;

// create a list with 5 elements, each element having the value 10.2
list<double> list2(5, 10.2);

cout << "list2: ";
list<double>::iterator it;
for(it = list2.begin(); it != list2.end(); ++it)
    cout << *it << " ";
cout << endl;

// create a list based on an array of elements
// only the first 5 elements of the array are copied into the vector
double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};

list<double> list3(array, array + 5);

cout << "list3: ";
for(it = list3.begin(); it != list3.end(); ++it)
    cout << *it << " ";
cout << endl;

// use the copy constructor to copy list3 list into list3copy list
list<double> list3copy(list3);

cout << "list3copy: ";
for(it = list3copy.begin(); it != list3copy.end(); ++it)
    cout << *it << " ";
cout << endl;

// assign 5 values of 10.2 to the list
list<double> list4;

list4.assign(5, 10.2);

cout << "list4: ";
for(it = list4.begin(); it != list4.end(); ++it)
    cout << *it << " ";
cout << endl;

// Output
// Size of list0 is 0
// Size of list1 is 5
// list2: 10.2 10.2 10.2 10.2 10.2
// list3: 3.45 67 10 0.67 8.99
// list3copy: 3.45 67 10 0.67 8.99
// list4: 10.2 10.2 10.2 10.2 10.2

Just like in the vector case, the begin() function returns an iterator to the first element of the list and the end() function returns an iterator which points to the position after the last element of the list.

Printing the elements of a list

Unlike vector, list doesn't have the [] operator overloaded and also it doesn't have the at() function for element access. Printing the elements of a list can only be done through iterators. Just like in the vector case, we construct a function, named print(), which prints the elements of a list, and which receives two parameters: the first parameter is the list to print and the second parameter represents the name of the list.

void print(list<double> lst, char * name)
{
    list<double>::iterator it;

    cout << name << ": ";

    for(it = lst.begin(); it != lst.end(); ++it)
        cout << *it << " ";

    cout << endl;
}

We can also print the elements of a list in reverse order, using a reverse iterator and rbegin() and rend() functions, like we did for vector.

double array[8] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677};
list<double> lst(array, array + 5);

print(lst, "lst");

cout << "lst in reverse order: ";

list<double>::reverse_iterator rit;
for(rit = lst.rbegin(); rit != lst.rend(); ++rit)
    cout << *rit << " ";

// Output
// lst: 3.45 67 10 0.67 8.99
// lst in reverse order: 8.99 0.67 10 67 3.45

Inserting elements into a list

Besides the push_back() and insert() functions, list has one more function for adding elements: push_front(), which adds an element (given as parameter) at the beginning of the list, right before the first element of the list.

list<double> lst;
list<double>::iterator it;

// add elements to the end of the list
lst.push_back(2.4);
lst.push_back(4.5);
lst.push_back(0.98);

print(lst, "lst");

// insert value 6.7 in the second position in the list
it = lst.begin();
lst.insert(++it, 6.7);

print(lst, "lst");

// insert elements from the array at the end of the list
double array[2] = {100.89, 789.76};
it = lst.end();
lst.insert(it, array, array + 2);

print(lst, "lst");

// add elements to the beginning of the list
lst.push_front(0.45);
lst.push_front(0.56);
lst.push_front(0.78);

print(lst, "lst");

// Output
// lst: 2.4 4.5 0.98
// lst: 2.4 6.7 4.5 0.98
// lst: 2.4 6.7 4.5 0.98 100.89 789.76
// lst: 0.78 0.56 0.45 2.4 6.7 4.5 0.98 100.89 789.76

Removing elements from a list

The pop_back() and erase() functions on lists are used exactly as we used them on vectors. Besides them, list has function pop_front(), which removes the first element of the list.

double array[10] = {3.45, 67, 10, 0.67, 8.99, 9.78, 6.77, 34.677, 100.67, 0.99};
list<double> lst(array, array + 10);
list<double>::iterator it;

print(lst, "lst");

// remove the last element of the list
lst.pop_back();

print(lst, "lst");

// remove the second element of the list
it = lst.begin();
lst.erase(++it);

print(lst, "lst");

// remove the first element of the list
lst.pop_front();
    
print(lst, "lst");

// Output
// lst: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 100.67 0.99
// lst: 3.45 67 10 0.67 8.99 9.78 6.77 34.677 100.67
// lst: 3.45 10 0.67 8.99 9.78 6.77 34.677 100.67
// lst: 10 0.67 8.99 9.78 6.77 34.677 100.67

For removing elements from the list, we can also use the remove() function. This function removes all the elements of the list with a specific value (given as parameter). Unlike the erase() function, which removes elements by position, the remove() function removes elements by value. In the example below, we will remove all elements with value 19.25 from the list.

double array[10] = {3.45, 67, 19.25, 0.67, 8.99, 9.78, 19.25, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
    
print(lst, "lst");

// remove all elements with value 19.25 from the list
lst.remove(19.25);

print(lst, "lst");

// Output
// lst: 3.45 67 19.25 0.67 8.99 9.78 19.25 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 9.78 34.677 100.67

For conditional removing of elements from a list, we use the remove_if() function. This function receives as parameter a predicate and removes all elements from the list for which predicate is true. The predicate is often implemented as a function which takes one parameter of the same type as the list, and returns a bool value. The remove_if() function goes through all the elements of the list and calls the predicate for each of them. The elements for which the predicate returns true are removed from the list.

In the following example, we remove all the elements from the list that are greater or equal to 15. First, we define the predicate, which is true for a given element only if the element is greater or equal to 15.

bool predicate(double& element)
{
    return (element >= 15.0) ? true : false;
}

Next, we call remove_if() to effectively remove the elements from the list that satisfy the above created predicate.

double array[10] = {3.45, 67, 19.25, 0.67, 8.99, 9.78, 19.25, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
    
print(lst, "lst");

// remove all elements greater or equal to 15.0 from the list
lst.remove_if(predicate);

print(lst, "lst");

// Output
// lst: 3.45 67 19.25 0.67 8.99 9.78 19.25 34.677 100.67 19.25
// lst: 3.45 0.67 8.99 9.78

For removing duplicate elements from a list, we use the unique() member function. This function has two forms. The first version, which takes no parameters, removes all elements from the list which are equal to their predecessors. From the definition, we see that the first element of the list will never be removed by this function, because it has no predecessor.

double array[10] = {3.45, 67, 67, 0.67, 8.99, 8.99, 8.99, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
    
print(lst, "lst");

// remove all duplicate elements from the list
lst.unique();

print(lst, "lst");

// Output
// lst: 3.45 67 67 0.67 8.99 8.99 8.99 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 34.677 100.67 19.25

The second version of unique() function receives as parameter a binary predicate. The predicate is often implemented as a function and has two parameters of the same type as the list and returns a bool value. The predicate specifies the condition that two consecutive elements of the list must satisfy in order to be considered duplicates. So, the function checks all consecutive pairs of elements from the list and removes those for which the predicate returns true. In the following example, we consider that two elements are duplicates if they are "almost equal" (their difference in absolute value is less or equal to 0.1).

First, we define the binary predicate which tests if two elements are "almost equal".

#include <math.h>

bool almost_equal(double& el1, double& el2)
{
    return (fabs(el1 - el2) <= 0.1) ? true : false;
}

Next, we call the unique() function to remove the duplicates using the predicate defined above.

double array[10] = {3.45, 3.455, 67, 0.67, 8.99, 9.0, 9.01, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);
    
print(lst, "lst");

// remove all duplicate elements from the list
lst.unique(almost_equal);
    
print(lst, "lst");

// Output
// lst: 3.45 3.455 67 0.67 8.99 9 9.01 34.677 100.67 19.25
// lst: 3.45 67 0.67 8.99 34.677 100.67 19.25

The functionality of clear() and empty() member functions remain unchanged for lists.

list<double> lst;

lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
    
if(lst.empty())
    cout << "lst is empty" << endl;
else
    cout << "lst is not empty" << endl;

// remove all the elements from the list
lst.clear();

if(lst.empty())
    cout << "lst is empty" << endl;
else
    cout << "lst is not empty" << endl;

// Output
// lst is not empty
// lst is empty

Sizing and resizing a list

Unlike the vector container, list doesn't have the capacity() and reserve() functions. The rest of the functions used for sizing and resizing a list are used in the same way as for vector. Thus, we will not go into details in this section. In what follows we present only an example of using those functions. For more details, please see the same section from the vector container.

list<double> lst;

lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
lst.push_back(10.67);
lst.push_back(9.89);
    
cout << "lst size is " << lst.size() << endl;
print(lst, "lst");

// case when new size <= size of list
lst.resize(3);

cout << "lst size is " << lst.size() << endl;
print(lst, "lst");

// case when new size > size of list
lst.resize(10);

cout << "lst size is " << lst.size() << endl;
print(lst, "lst");

// Output
// lst size is 5
// lst: 0.67 7.89 3.56 10.67 9.89
// lst size is 3
// lst: 0.67 7.89 3.56
// lst size is 10
// lst: 0.67 7.89 3.56 0 0 0 0 0 0 0

Reversing a list

In order to reverse the order of the elements in a list, we use the reverse() member function.

list<double> lst;

lst.push_back(0.67);
lst.push_back(7.89);
lst.push_back(3.56);
lst.push_back(10.67);
lst.push_back(9.89);
    
print(lst, "lst");

// reverse the elements of the list
lst.reverse();

print(lst, "lst reversed");

// Output
// lst: 0.67 7.89 3.56 10.67 9.89
// lst reversed: 9.89 10.67 3.56 7.89 0.67

Unlike the case of the reverse iterator, when we just print the elements of the list in reverse order, the reverse() function actually reverses the order of the elements in the list.

Sorting a list

For sorting the elements of a list, we use the sort() function, which compares each pair of elements in the list using a sorting function. We can specify the sorting function as a parameter of sort(). When no sorting function is specified, sort() uses the < operator to compare elements.

double array[10] = {3.45, 3.455, 67, 0.67, 8.99, 9.0, 9.01, 34.677, 100.67, 19.25};
list<double> lst(array, array + 10);

print(lst, "lst");
    
// sort the list;  
// < operator will be used as default
// the elements will be sorted in ascending order
lst.sort();

print(lst, "lst in ascending order");

// sort the list; specify the sorting function
// > operator will be used in this case
// the elements will be sorted in descending order
lst.sort( greater<double>() );

print(lst, "lst in descending order");

// sort the list; specify the sorting function
// < operator will be used in this case
// the elements will be sorted in descending order
lst.sort( less<double>() );

print(lst, "lst in ascending order");

// Output
// lst: 3.45 3.455 67 0.67 8.99 9 9.01 34.677 100.67 19.25
// lst in ascending order: 0.67 3.45 3.455 8.99 9 9.01 19.25 34.677 67 100.67
// lst in descending order: 100.67 67 34.677 19.25 9.01 9 8.99 3.455 3.45 0.67
// lst in ascending order: 0.67 3.45 3.455 8.99 9 9.01 19.25 34.677 67 100.67

Exchanging two lists

Exchanging the content of two lists is done using the swap() member function.

double odds[5] = {1.0, 3.0, 5.0, 7.0, 9.0};
double evens[5] = {2.0, 4.0, 6.0, 8.0, 10.0};
list<double> lst1(odds, odds + 5);
list<double> lst2(evens, evens + 5);

cout << "The lists before swap: " << endl;
print(lst1, "lst1");
print(lst2, "lst2");

// swap the contents of the two lists
lst1.swap(lst2);

cout << "The lists after swap: " << endl;
print(lst1, "lst1");
print(lst2, "lst2");

// Output
// The lists before swap:
// lst1: 1 3 5 7 9
// lst2: 2 4 6 8 10
// The lists after swap:
// lst1: 2 4 6 8 10
// lst2: 1 3 5 7 9

Merging two lists

One way to copy the elements of a list into another list is to use the splice() member function. This function has three forms. In the first form, we call splice() in the following way: list1.splice(it1, list2). This copies all elements of list list2 into list list1, starting from the position specified by iterator it1. After the operation is completed, list2 will be empty.

list<double> list1;
list<double> list2;

list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);

list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
    
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");

list<double>::iterator it1 = list1.begin();
++it1;

// move all the elements of list2 into list1, starting from the second position
list1.splice(it1, list2);

cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");

// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 2 3 4 5 6 7 8
// list2:

In the second form, we call splice() in the following way: list1.splice(it1, list2, it2). This moves into list list1, at the position specified by iterator it1, only the element from list list2 to which iterator it2 points. In this case, only the element being moved is removed from list list2.

list<double> list1;
list<double> list2;

list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);

list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
    
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");

list<double>::iterator it1 = list1.begin();
++it1;
list<double>::iterator it2 = list2.begin();

// move only the first element of list2 into list1, in the second position
list1.splice(it1, list2, it2);

cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");

// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 2 5 6 7 8
// list2: 3 4

The third way of calling splice() is the following: list1.splice(it1, list2, it2begin, it2end). This version moves the range of elements from list list2, from the position specified by iterator it2begin to the position specified by iterator it2end, into list list1, at the position specified by iterator it1.

list<double> list1;
list<double> list2;

list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);

list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);
    
cout << "Before splice: " << endl;
print(list1, "list1");
print(list2, "list2");

list<double>::iterator it1;
list<double>::iterator it2begin;
list<double>::iterator it2end;

it1 = list1.end();
it2begin = list2.begin();
it2end = list2.end();
--it2end;
    
// move from the first to the last element of list2 at the end of list1
// observe that the last element of list2 is not moved
list1.splice(it1, list2, it2begin, it2end);

cout << "After splice: " << endl;
print(list1, "list1");
print(list2, "list2");

// Output
// Before splice:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After splice:
// list1: 1 5 6 7 8 2 3
// list2: 4

Another useful function for merging two lists is merge(). The merge() function is called in the following way: list1.merge(list2). As a result of calling merge(), all elements from list2 will be inserted into list1, at their respective ordered positions. For each element el2 of list2, merge() finds the first element el1 less or equal than el2 and inserts el2 immediately after el1. This is done to preserve the order of the elements from list1. Please notice that, unlike splice() function, in order to use merge() function on two lists, both lists must be sorted. If the lists are not sorted, we must explicitely sort them, using the sort() function. If we try to use merge() on two lists, and not both of them are sorted, the application will crash. Also notice that, after calling merge(), list2 will be empty.

list<double> list1;
list<double> list2;

list1.push_back(1.0);
list1.push_back(5.0);
list1.push_back(6.0);
list1.push_back(7.0);
list1.push_back(8.0);

list2.push_back(2.0);
list2.push_back(3.0);
list2.push_back(4.0);

cout << "Before merge: " << endl;
print(list1, "list1");
print(list2, "list2");
    
// merge the two lists
list1.merge(list2);

cout << "After merge: " << endl;
print(list1, "list1");
print(list2, "list2");

// Output
// Before merge:
// list1: 1 5 6 7 8
// list2: 2 3 4
// After merge:
// list1: 1 2 3 4 5 6 7 8
// list2:

Two dimensional lists

Two dimensional lists are lists of lists.

list< list<double> > matrix;

list<double> lst1(5, 6.713);
list<double> lst2(6, 5.678);

matrix.push_back(lst1);
matrix.push_back(lst2);

list< list<double> >::iterator it2d;
for(it2d = matrix.begin(); it2d != matrix.end(); it2d++)
    print(*it2d, "row");

// Output
// row: 6.713 6.713 6.713 6.713 6.713
// row: 5.678 5.678 5.678 5.678 5.678 5.678

Above, we call print() function and we pass as the first parameter the value stored at the address of the current iterator, which is a list.

Lists of user defined elements

Lists can also store user defined elements. In what follows, we create the class Person, which has three members: name (of type char *), sex (of type char) and age (of type int). As mentioned before, the copy constructor is indispensable, and, since the class uses dynamic memory allocation, the destructor also becomes necessary. Also, we will overload the assignment (=) operator, the less than (<) operator, the equality (==) operator and the greater than (>) operator, because, some functions, like sort(), will need them. The sort() function makes comparison of elements based on their types and so, for user defined elements, those operators become indispensable.

class Person
{
    char * name;
    char sex;
    int age;

public:

    // constructor
    Person()
    {
        name = new char[strlen("Anonymous") + 1];
        sex = 'N';
        age = 0;
    }

    // constructor
    Person(char * pName, char pSex, int pAge)
        : sex(pSex), age(pAge)
    {
        name = new char[strlen(pName) + 1];
        strcpy(name, pName);
    }

    // copy constructor
    Person(const Person& rhs)
        : sex(rhs.sex), age(rhs.age)
    {
        name = new char[strlen(rhs.name) + 1];
        strcpy(name, rhs.name);
    }

    // overload the assignment operator
    Person& operator=(const Person& rhs)
    {
        name = new char[strlen(rhs.name) + 1];
        strcpy(name, rhs.name);
        sex = rhs.sex;
        age = rhs.age;

        return *this;
    }

    // overload the == operator
    // for sorting purposes, we consider that two Person objects are "equal"
    // if they have the same age
    bool operator==(const Person& rhs) const
    {
        return (age == rhs.age) ? true : false;
    }

    // overload the < operator
    // for sorting purposes, we consider that a Person object is "less than" another
    // if it's age is less than the other object's age
    bool operator<(const Person& rhs) const
    {
        return (age < rhs.age) ? true : false;
    }

    // overload the > operator
    // for sorting purposes, we consider that a Person object is "greater than" another
    // if it's age is greater than the other object's age
    bool operator>(const Person& rhs) const
    {
        return (age > rhs.age) ? true : false;
    }

    // print the object
    void print()
    {
        cout << name << " " << sex << " " << age << endl;
    }

    // destructor
    ~Person()
    {
        delete []name;
    }
};

We modify a little bit the function for printing the contents of the list.

void print(list<Person> lst, char * name)
{
    list<Person>::iterator it;

    cout << name << ":" << endl;

    for(it = lst.begin(); it != lst.end(); ++it)
        it->print();

    cout << endl;
}

Next, we create a list to hold Person objects, we add some elements to it, we print the contents of the list, we remove some elements, and then we sort the list in ascending and descending order.

list<Person> lst;

// create some Person objects
Person p1("Bill Gates", 'M', 50);
Person p2("Scott Meyers", 'M', 43);
Person p3("Charles Petzold", 'M', 48);
Person p4("Christina Dermayr", 'F', 30);
Person p5("Andrei Neagu", 'M', 22);
Person p6("Yin Su", 'F', 56);
Person p7("Georgeta Bills", 'F', 37);

// add the objects to the list
lst.push_back(p1);
lst.push_back(p2);
lst.push_back(p3);
lst.push_back(p4);
lst.push_back(p5);
lst.push_front(p6);
lst.push_front(p7);

print(lst, "lst");

// sort the list in ascending order
lst.sort( less<Person>() );

print(lst, "lst in ascending order");

// sort the list in descending order
lst.sort( greater<Person>() );

print(lst, "lst in descending order");

// delete the first element from the list
lst.pop_front();

print(lst, "lst");

// clear the list
lst.clear();

if(lst.empty())
    cout << "lst is empty" << endl;
else
    cout << "lst is not empty" << endl;

// Output
// lst:
// Georgeta Bills F 37
//Yin Su F 56
// Bill Gates M 50
// Scott Meyers M 43
// Charles Petzold M 48
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst in ascending order:
// Andrei Neagu M 22
// Christina Dermayr F 30
// Georgeta Bills F 37
// Scott Meyers M 43
// Charles Petzold M 48
// Bill Gates M 50
// Yin Su F 56
// 
// lst in descending order:
// Yin Su F 56
// Bill Gates M 50
// Charles Petzold M 48
// Scott Meyers M 43
// Georgeta Bills F 37
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst:
// Bill Gates M 50
// Charles Petzold M 48
// Scott Meyers M 43
// Georgeta Bills F 37
// Christina Dermayr F 30
// Andrei Neagu M 22
//
// lst is empty

Complexity

The way it is implemented suggests that the list container is mostly used for storing large objects, with multiple insertions and deletions, especially inside the list, because they involve only renewing some links and not moving objects in memory. Even the sort() and reverse() members functions work with pointers and not with stored objects. It is recommended to use them and not their generic alternatives. The fact that list uses uncontiguous memory leads to the conclusion that an iterator, once loaded with the address of a container element, cannot become invalid, unless the node to which it points is deleted.

Going through the elements of the list is much slower than in the vector case, because it assumes pointer movement, not address calculation. The list container also occupies additional memory for managing the previous and next links.