List

The list container is a very different sequence container compared to vector and deque. list does not use random access iterators, but as a trade-off allow constant time insertion and deletion at any point in the list, instead of reallocating memory to cope with the locations of elements in the container. Elements are just inserted into the list by providing a link from the element it was inserted after and a link to the element it was inserted before. It is much like a naive linked-list data-structure in which each time elements are added, instead of reordering the data, you just slip them in to wherever they need to be, ignoring the overall structure and order of the list. The same is true of element deletion. The consequence of this is that we can insert or remove elements quickly, but as a forfeit sacrafice the ability to use random access iterators (we've given up the ability to recall where element i is). Lists are included in your program by including <list>.

With no need to worry about reallocation of elements within the list, insertions do not invalidate iterators, and deletions only invalidate elements which are being referred to.

The lack of random access also means that a few key generic algorithms will not work. These are instead defined as member functions of list.

Let's look at a few examples of using a list.

     /* list1.cc
        Compiled using g++ list1.cc Address.cc -o list1 */
     #include <list>
     #include "AddressRepository.hh"
     int main()
     {
       list<Address> list1;
       /* Add all of the address objects to the list: */
       list1.push_front(addr1);
       list1.push_front(addr2);
       list1.push_front(addr3);
       list1.push_front(addr4);
       list1.push_front(addr5);
       /* Declare an iterator to work with: */
       std::list<Address>::iterator pos;
       /* Loop through the list printing out elements: */
       cout << "Iterating through list1: " << endl;
       for (pos=list1.begin() ; pos!=list1.end(); ++pos)
         {
           pos->print();
         }
       /* Create a new list to work with: */
       list<Address> list2;
       for (pos=list1.begin(); pos!=list1.end(); ++pos)
         {
           list2.insert(list2.begin(), *pos);
         }
     
       /* Create and insert a new Address object: */
       Address addr6("Reggie", "1 Card Rd.", "Hamps", 892286);
       list2.push_front(addr6);
       cout << "Iterating through list2:" << endl;
       for (pos=list2.begin() ; pos!=list2.end(); ++pos)
         {
           pos->print();
         }
       exit(0);
     }
     

     Example 3.9: list1.cc
     

A few changes have been made since the deque and vector examples that also utilised the Address class. However, it's been modified to create a copy of list list1 using the insert function to add elements to list2:

       list<Address> list2;
       for (pos=list1.begin(); pos!=list1.end(); ++pos)
         {
           list2.insert(list2.begin(), *pos);
         }
     

This doesn't really demonstrate anything unless we actually time it; recall that inserting elements into a list is extremely fast. Thus, whereas with a vector or deque we can use insert as needed, it is extremely inefficient becuase memory needs to be reallocated each time. Our list does not suffer from this restriction, so we insert elements at will knowing that it will be fast.

Using algorithms to sort data in containers is discussed in Generic Algorithms and Function Objects. However, these sorting algorithms will not work with list because we need random access iterators to be able to sort data. Therefore, a number of member functions are defined that enable us to take advantage of a number of algorithms denied to us. These are sort to sort data using the less-than equality operator and unique to remove duplicate elements in a list (Some Predefined Function Objects discusses how you can alter the default sorting criterion on a list). They're trivial to use, as can be seen in the example below:

     /* list2.cc
        Compiled using g++ list2.cc Address.cc -o list2 */
     #include <list>
     #include "AddressRepository.hh"
     int main()
     {
       list<Address> list1;
       /* Add all of the address objects to the list: */
       list1.push_front(addr1);
       list1.push_front(addr2);
       list1.push_front(addr3);
       list1.push_front(addr4);
       list1.push_front(addr5);
     
       /* Sort the list: */
       list1.sort();
       /* Remove any duplicate names: */
       list1.unique();
       std::list<Address>::iterator pos;
       for (pos=list1.begin() ; pos!=list1.end(); ++pos)
         {
           pos->print();
         }
       exit(0);
     }
     

     Example 3.10: list2.cc
     

The result is fairly predictable; the elements are sorted according to the < operator, and then any unique elements are removed - in this instance, Address objects that have matching names "Jane". Here's the output:

     $ ./list2
     Name: Adam, Street: 23 Big St., City: Worcs, Phone: 443098
     Name: Bob, Street: 2 St. Annes Walk, City: Oxford, Phone: 303022
     Name: Edith, Street: 91 Glib Terrace, City: Shrops, Phone: 858976
     Name: Jane, Street: 55 Almond Terrace, City: Worcs, Phone: 242783