Lists

A list (or linked list) is a data structure that stores its items at non-adjacent locations in memory. Unlike vectors, lists have very poor random access performance; on the other hand, insert() and erase() are very fast.

Many algorithms that work on vectors don't work on lists, notably sort() and binary_search(). This is because lists don't provide fast random access. For sorting an STL list, we can use its sort() member function.

Figure 11.2. A list of Films

The STL's list class is called std::list and is defined in . Here's an example:

list films;

The Qt equivalent is called QValueList:

QValueList films;

The Film class was presented in the previous section (p. 244).

New items can be added using push_back() or with insert(). Unlike vectors, inserting at the beginning or in the middle of a list is not expensive.

STL lists do not provide the [] operator, so iterators must be used to traverse their elements. (Qt lists support the [] operator, but it can be very slow on large lists.) The syntax and usage is exactly the same as for vectors, except that we write list instead of vector in front of the iterator type. For example:

list::const_iterator it = films.begin();
while (it != films.end()) {
 cerr << (*it).title().ascii() << endl;
 ++it;
}

Otherwise, lists mostly provide the same functions as vectors, including empty(), size(), erase(), and clear(). The find() algorithm can also be used on lists.

A few Qt functions return a QValueList. If we want to iterate over the return value of a function, we must take a copy of the list and iterate over the copy. For example, the following code is the correct way to iterate over the QValueList returned by QSplitter::sizes():

QValueList list = splitter->sizes();
QValueList::const_iterator it = list.begin();
while (it != list.end()) {
 do_something(*it);
 ++it;
}

The following code is wrong:

// WRONG
QValueList::const_iterator it = splitter->sizes().begin();
while (it != splitter->sizes().end()) {
 do_something(*it);
 ++it;
}

This is because QSplitter::sizes() returns a new QValueList by value every time it is called. If we don't store the return value, C++ automatically destroys it before we have even started iterating, leaving us with a dangling iterator. To make matters worse, each time the loop is run, QSplitter::sizes() must generate a new copy of the list because of the splitter->sizes().end() call. In summary: Always iterate on a copy of a container returned by value.

Copying a container like this sounds expensive, but it isn't, because Qt uses an optimization called implicit sharing. This optimization means that we can program as if the data has been copied, even though behind the scenes no data copying has taken place.

The QStringList class, which is used in many places in Qt, is a subclass of QValueList. In addition to the functions it inherits from its base class, it provides some extra functions that make the class more powerful. These functions will be discussed in the last section of this chapter.