Home > Articles

This chapter is from the book

This chapter is from the book

12.3 list

The standard library offers a doubly-linked list called list:

We use a list for sequences where we want to insert and delete elements without moving other elements. Insertion and deletion of phone book entries could be common, so a list could be appropriate for representing a simple phone book. For example:

list<Entry> phone_book = {
         {"David Hume",123456},
         {"Karl Popper",234567},
         {"Bertrand Arthur William Russell",345678}
};

When we use a linked list, we tend not to access elements using subscripting the way we commonly do for vectors. Instead, we might search the list looking for an element with a given value. To do this, we take advantage of the fact that a list is a sequence as described in Chapter 13:

int get_number(const string& s)
{
          for (const auto& x : phone_book)
                   if (x.name==s)
                          return x.number;
          return 0;  // use 0 to represent "number not found"
}

The search for s starts at the beginning of the list and proceeds until s is found or the end of phone_book is reached.

Sometimes, we need to identify an element in a list. For example, we may want to delete an element or insert a new element before it. To do that we use an iterator: a list iterator identifies an element of a list and can be used to iterate through a list (hence its name). Every standard-library container provides the functions begin() and end(), which return an iterator to the first and to one-past-the-last element, respectively (§13.1). Using iterators explicitly, we can – less elegantly – write the get_number() function like this:

int get_number(const string& s)
{
         for (auto p = phone_book.begin(); p!=phone_book.end(); ++p)
                 if (p->name==s)
                         return p->number;
         return 0;  // use 0 to represent "number not found"
}

In fact, this is roughly the way the terser and less error-prone range-for loop is implemented by the compiler. Given an iterator p, *p is the element to which it refers, ++p advances p to refer to the next element, and when p refers to a class with a member m, then p->m is equivalent to (*p).m.

Adding elements to a list and removing elements from a list is easy:

void f(const Entry& ee, list<Entry>::iterator p, list<Entry>::iterator q)
{
         phone_book.insert(p,ee);      // add ee before the element referred to by p
         phone_book.erase(q);           // remove the element referred to by q
}

For a list, insert(p,elem) inserts an element with a copy of the value elem before the element pointed to by p. Here, p may be an iterator pointing one-beyond-the-end of the list. Conversely, erase(p) removes the element pointed to by p and destroys it.

These list examples could be written identically using vector and (surprisingly, unless you understand machine architecture) often perform better with a vector than with a list. When all we want is a sequence of elements, we have a choice between using a vector and a list. Unless you have a reason not to, use a vector. A vector performs better for traversal (e.g., find() and count()) and for sorting and searching (e.g., sort() and equal_range(); §13.5, §15.3.3).

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.