Vectors

The STL and Qt classes for vectors, lists, and maps are template classes parameterized by the types of the objects we want to store in them. The values that can be stored in these classes can be basic types (like int and double), pointers, or classes that have a default constructor (a constructor that takes or needs no arguments), a copy constructor, and an assignment operator. Classes that qualify include QDateTime, QRegExp, QString, and QVariant. Qt classes that inherit from QObject don't qualify, because they don't implement a copy constructor and an assignment operator. This isn't usually a problem, since we can still store pointers to these types.

In this section, we will review the most common operations for vectors, and in the next two sections, we will review lists and maps. For most of the examples, we will use the Film class, which stores the title and duration of a film. (We will not call the class Movie because that looks too similar to Qt's QMovie class, which is used to show animated images.)

Here's the definition of Film:

class Film
{
public:
 Film(int id = 0, const QString &title = "", int duration = 0);

 int id() const { return myId; }
 void setId(int catalogId) { myId = catalogId; }
 QString title() const { return myTitle; }
 void setTitle(const QString &title) { myTitle = title; }
 int duration() const { return myDuration; }
 void setDuration(int minutes) { myDuration = minutes; }

private:
 int myId;
 QString myTitle;
 int myDuration;
};

int operator==(const Film &film1, const Film &film2);
int operator<(const Film &film1, const Film &film2);

We don't explicitly provide a copy constructor or an assignment operator because the ones automatically supplied by C++ suffice here. If the class had included pointers to memory allocated by the class, we would have to implement them ourselves.

In addition to the class, we provide an equality operator and a "less than" operator. The equality operator is used when we search a container to see if it contains a particular item. The "less than" operator is used for comparing items when sorting them. We don't need to implement the four other comparison operators (!=, <=, >, >=) since STL never uses them.

Here's the implementation of the three non-inline functions:

Film::Film(int id, const QString &title, int duration)
{
 myId = id;
 myTitle = title;
 myDuration = duration;
}

int operator==(const Film &film1, const Film &film2)
{
 return film1.id() == film2.id();
}

int operator<(const Film &film1, const Film &film2)
{
 return film1.id() < film2.id();
}

When comparing Film objects, we use IDs rather than titles because titles are not necessarily unique.

Figure 11.1. A vector of Films

A vector is a data structure that stores its items at adjacent positions in memory. What distinguishes a vector from a plain C++ array is that a vector knows its own size and can be resized. Appending extra elements to the end of a vector is fairly efficient, but inserting elements at the front or in the middle of a vector is expensive.

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

vector films;

The Qt equivalent is called QValueVector:

QValueVector films;

A vector created like this has size 0. If we know in advance how many elements we are going to need, we can give the vector an initial size when we define it and use the [] operator to assign a value to its elements; otherwise, we must either resize it later or append items.

A convenient way to populate a vector is to use push_back(). This function appends an element at the end, extending the vector by one:

films.push_back(Film(4812, "A Hard Day's Night", 85));
films.push_back(Film(5051, "Seven Days to Noon", 94));
films.push_back(Film(1301, "Day of Wrath", 105));
films.push_back(Film(9227, "A Special Day", 110));
films.push_back(Film(1817, "Day for Night", 116));

In general, Qt offers the same function names as the STL, although in some cases Qt has additional more Qt-like names. For example, if we are using the Qt classes, we can append items using either push_back() or append().

Another way to populate a vector is to give the vector an initial size and to initialize the elements individually:

vector films(5);
films[0] = Film(4812, "A Hard Day's Night", 85);
films[1] = Film(5051, "Seven Days to Noon", 94);
films[2] = Film(1301, "Day of Wrath", 105);
films[3] = Film(9227, "A Special Day", 110);
films[4] = Film(1817, "Day for Night", 116);

Vector entries that are created without being assigned an explicit value are initialized using the item class's default constructor. For basic and pointer types, the value is undefined, just as it is when we define variables of these types on the stack.

We can iterate over the vector's elements using the [] operator:

for (int i = 0; i < (int)films.size(); ++i)
 cerr << films[i].title().ascii() << endl;

Alternatively, we can use an iterator:

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

Every container class has two iterator types: iterator and const_iterator. The difference between the two is that const_iterator doesn't allow us to modify the data.

A container's begin() function returns an iterator that refers to the first item in the container (for example, films[0]). A container's end() function returns an iterator that refers to the "one past the last" item (for example, films[5]). If a container is empty, begin() equals end(). This can be used to see if the container has any elements, although it is more convenient to call empty() for this purpose.

Iterators have an intuitive syntax that resembles the syntax of C++ pointers. We can use the ++ and -- operators to move to the next or previous item, and unary * to retrieve the item stored at the current iterator position. In fact, for vector, the iterator and const_iterator types are merely typedefs for T * and const T *.

If we want to find an item in a vector using a linear search, we can use the STL find() function:

vector::iterator it = find(films.begin(), films.end(),
 Film(4812));
if (it != films.end())
 films.erase(it);

The find() function returns an iterator to the first item that compared equal (using operator==()) to the item passed as the last argument. It is defined in , along with many other template functions. These functions typically operate on iterators. Qt provides a few of these functions under different names (for example, qFind()). You can use them if you want to use Qt without the STL.

To sort the items in a vector, we can call sort():

sort(films.begin(), films.end());

The sort() function uses the < operator to compare items, unless we pass a different comparison function.

Once sorted, we can use the binary_search() function to see if an item is present. On a sorted vector, binary_search() gives the same result as find() (assuming no two films have the same ID), but is much faster:

int id = 1817;
if (binary_search(films.begin(), films.end(), Film(id)))
 cerr << "Found" << id << endl;

Given a position indicated by an iterator, we can expensively insert a new item using insert() or remove an existing item using erase():

films.erase(it);

The items that follow the erased item in the vector are then moved one position to the left to fill its position, and the vector's size is reduced by one.