List

As the name suggests, a list object is implemented by a doubly linked list in which each item has a link to the next item and the previous one. This means that it is quick to insert items (as the example in Chapter 2, Working with Memory, Arrays, and Pointers, showed with a singly linked list), but since, in a linked list, an item only has access to the items in front and behind it, there is no random access with the [] indexoperator.

The class allows you to provide values through the constructor, or you can use member methods. For example, the assign method allows you fill the container in one action using an initializer list, or, with iterators, to a range in another container. You can also insert a single item using the push_back or push_front method:

    list<int> primes{ 3,5,7 }; 
    primes.push_back(11); 
    primes.push_back(13); 
    primes.push_front(2); 
    primes.push_front(1);

The first line creates a list object that contains 3, 5, and 7, and then pushes 11 and 13 to the end (in that order), so that the list contains {3,5,7,11,13}. The code then pushes the numbers 2 and 1 to the front, so that the final list is {1,2,3,5,7,11,13}. In spite of the names, the pop_front and pop_back methods just remove the item at the front or back of the list, but will not return the item. If you want to get the item that has been removed, you must first access the item through the front or back method:

    int last = primes.back(); // get the last item 
    primes.pop_back();        // remove it

The clear method will remove all items in the list and the erase method will delete items. There are two versions: one with an iterator that identifies a single item and another that has two iterators that indicate a range. A range is indicated by providing the first item in the range and the item after the range.

    auto start = primes.begin(); // 1 
    start++;                     // 2 
    auto last = start;           // 2 
    last++;                      // 3 
    last++;                      // 5 
    primes.erase(start, last);   // remove 2 and 3

This is a general principle with iterators and the Standard Library containers; a range is indicated by iterators by the first item and the item after the last item. The remove method will remove all items with a specified value:

    list<int> planck{ 6,6,2,6,0,7,0,0,4,0 }; 
    planck.remove(6);            // {2,0,7,0,0,4,0}

There is also a method remove_if that takes a predicate and will only remove an item if the predicate returns true. Similarly, you can insert items into a list with an iterator, and the item is inserted before the specified item:

    list<int> planck{ 6,6,2,6,0,7,0,0,4,0 }; 
    auto it = planck.begin(); 
    ++it; 
    ++it; 
    planck.insert(it, -1); // {6,6,-1,2,6,0,7,0,0,4,0}

You can also indicate that the item should be inserted more than once at that position (and if so, how many copies) and you can provide several items to be inserted at one point. Of course, if the iterator you pass is obtained by calling the begin method, then the item is inserted at the beginning of the list. The same can be achieved by calling the push_front method. Similarly, if the iterator is obtained by calling the end method, then the item is inserted at the end of the list, which is the same as calling push_back.

When you call the insert method, you provide an object that will either be copied into the list or moved into the list (through rvalue semantics). The class also provides several emplace methods (emplace, emplace_front, and emplace_back) that will construct a new object based on the data you provide, and insert that object in the list. For example, if you have a point class that can be created from two double values, you can either insert a constructed point object or emplace a point object by providing two double values:

    struct point 
    { 
        double x = 0, y = 0; 
        point(double _x, double _y) : x(_x), y(_y) {} 
    }; 

    list<point> points; 
    point p(1.0, 1.0); 
    points.push_back(p); 
    points.emplace_back(2.0, 2.0);

Once you have created a list, you can manipulate it with member functions. The swap method takes a suitable list object as a parameter, it moves the items from the parameter into the current object, and moves the items in the current list to the parameter. Since the list object is implemented using linked lists, this operation is quick.

    list<int> num1 { 2,7,1,8,2,8 }; // digits of Euler's number 
    list<int> num2 { 3,1,4,5,6,8 }; // digits of pi 
    num1.swap(num2);

After this, code num1 will contain {3,1,4,5,6,8} and num2 will contain {2,7,1,8,2,8}, as the following illustrates:

A list will hold the items in the order that they were inserted into the container; however, you can sort them by calling the sort method that will, by default, order items in ascending order using the < operator for the items in the list container. You can also pass a function object for a comparison operation. Once sorted, you can reverse the order of items by calling the reverse method. Two sorted lists can be merged, which involves taking the items from the argument list and inserting them into the calling list, in order:

    list<int> num1 { 2,7,1,8,2,8 }; // digits of Euler's number 
    list<int> num2 { 3,1,4,5,6,8 }; // digits of pi 
    num1.sort();                    // {1,2,2,7,8,8} 
    num2.sort();                    // {1,3,4,5,6,8} 
    num1.merge(num2);               // {1,1,2,2,3,4,5,6,7,8,8,8}

Merging two lists may result in duplicates, and these can be removed by calling the unique method:

    num1.unique(); // {1,2,3,4,5,6,7,8}