Home > Articles > Programming > C/C++

C++ GUI Programming with Qt4: Container Classes

This chapter looks at sequential and associative containers, generic algorithms, as well as strings, byte arrays, and variants.
This chapter is from the book

11. Container Classes

  • Sequential Containers
  • Associative Containers
  • Generic Algorithms
  • Strings, Byte Arrays, and Variants

Container classes are general-purpose template classes that store items of a given type in memory. C++ already offers many containers as part of the Standard Template Library (STL), which is included in the Standard C++ library.

Qt provides its own container classes, so for Qt programs we can use both the Qt and the STL containers. The main advantages of the Qt containers are that they behave the same on all platforms and that they are implicitly shared. Implicit sharing, or "copy on write", is an optimization that makes it possible to pass entire containers as values without any significant performance cost. The Qt containers also feature easy-to-use iterator classes inspired by Java, they can be streamed using QDataStream, and they usually result in less code in the executable than the corresponding STL containers. Finally, on some hardware platforms supported by Qt/Embedded Linux, the Qt containers are the only ones available.

Qt offers both sequential containers such as QVector<T>, QLinkedList<T>, and QList<T>, and associative containers such as QMap<K, T> and QHash<K, T>. Conceptually, the sequential containers store items one after another, whereas the associative containers store key–value pairs.

Qt also provides generic algorithms that perform operations on arbitrary containers. For example, the qSort() algorithm sorts a sequential container, and qBinaryFind() performs a binary search on a sorted sequential container. These algorithms are similar to those offered by the STL.

If you are already familiar with the STL containers and have STL available on your target platforms, you might want to use them instead of, or in addition to, the Qt containers. For more information about the STL classes and functions, a good place to start is SGI's STL web site: http://www.sgi.com/tech/stl/.

In this chapter, we will also look at QString, QByteArray, and QVariant, since they have a lot in common with containers. QString is a 16-bit Unicode string used throughout Qt's API. QByteArray is an array of 8-bit chars useful for storing raw binary data. QVariant is a type that can store most C++ and Qt value types.

Sequential Containers

A QVector<T> is an array-like data structure that stores its items at adjacent positions in memory, as Figure 11.1 illustrates. What distinguishes a vector from a plain C++ array is that a vector knows its own size and can be resized. Appending extra items to the end of a vector is fairly efficient, whereas inserting items at the front or in the middle of a vector can be expensive.

11fig01.gif

Figure 11.1 A vector of s

If we know in advance how many items 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 the items; otherwise, we must either resize the vector later on or append items. Here's an example where we specify the initial size:

QVector<double> vect(3);
vect[0] = 1.0;
vect[1] = 0.540302;
vect[2] = -0.416147;

Here's the same example, this time starting with an empty vector and using the append() function to append items at the end:

QVector<double> vect;
vect.append(1.0);
vect.append(0.540302);
vect.append(-0.416147);

We can also use the << operator instead of append():

vect << 1.0 << 0.540302 << -0.416147;

One way to iterate over the vector's items is to use [] and count():

double sum = 0.0;
for (int i = 0; i < vect.count(); ++i)
    sum += vect[i];

Vector entries that are created without being assigned an explicit value are initialized using the item class's default constructor. Basic types and pointer types are initialized to zero.

Inserting items at the beginning or in the middle of a QVector<T>, or removing items from these positions, can be inefficient for large vectors. For this reason, Qt also offers QLinkedList<T>, a data structure that stores its items at non-adjacent locations in memory, as illustrated by Figure 11.2. Unlike vectors, linked lists don't support random access, but they provide "constant time" insertions and removals.

11fig02.gif

Figure 11.2 A linked list of s

Linked lists do not provide the [] operator, so iterators must be used to traverse their items. Iterators are also used to specify the position of items. For example, the following code inserts the string "Tote Hosen" between "Clash" and "Ramones":

QLinkedList<QString> list;
list.append("Clash");
list.append("Ramones");

QLinkedList<QString>::iterator i = list.find("Ramones");
list.insert(i, "Tote Hosen");

We will take a more detailed look at iterators later in this section.

The QList<T> sequential container is an "array-list" that combines the most important benefits of QVector<T> and QLinkedList<T> in a single class. It supports random access, and its interface is index-based like QVector's. Inserting or removing an item at either end of a QList<T> is very fast, and inserting in the middle is fast for lists with up to about one thousand items. Unless we want to perform insertions in the middle of huge lists or need the list's items to occupy consecutive addresses in memory, QList<T> is usually the most appropriate general-purpose container class to use.

The QStringList class is a subclass of QList<QString> that is widely used in Qt's API. In addition to the functions it inherits from its base class, it provides some extra functions that make the class more versatile for string handling. We discuss QStringList in the last section of this chapter (p. 290).

QStack<T> and QQueue<T> are two more examples of convenience subclasses. QStack<T> is a vector that provides push(), pop(), and top(). QQueue<T> is a list that provides enqueue(), dequeue(), and head().

For all the container classes seen so far, the value type T can be a basic type like int or double, a pointer type, or a class that has a default constructor (a constructor that takes no arguments), a copy constructor, and an assignment operator. Classes that qualify include QByteArray, QDateTime, QRegExp, QString, and QVariant. Qt classes that are derived from QObject do not qualify, because they lack a copy constructor and an assignment operator. This is no problem in practice, since we can simply store pointers to QObject types rather than the objects themselves.

The value type T can also be a container, in which case we must remember to separate consecutive angle brackets with spaces; otherwise, the compiler will choke on what it thinks is a >> operator. For example:

QList<QVector<double> > list;

In addition to the types just mentioned, a container's value type can be any custom class that meets the criteria described earlier. Here is an example of such a class:

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

    void setTitle(const QString &title) { myTitle = title; }
    QString title() const { return myTitle; }
    void setDuration(int duration) { myDuration = duration; }
    QString duration() const { return myDuration; }

private:
    QString myTitle;
    int myDuration;
};

The class has a constructor that requires no arguments (although it can take up to two). It also has a copy constructor and an assignment operator, both implicitly provided by C++. For this class, a member-by-member copy is sufficient, so there is no need to implement our own copy constructor and assignment operator.

Qt provides two categories of iterators for traversing the items stored in a container: Java-style iterators and STL-style iterators. The Java-style iterators are easier to use, whereas the STL-style iterators can be combined with Qt's and STL's generic algorithms and are more powerful.

For each container class, there are two Java-style iterator types: a read-only iterator and a read-write iterator. Their valid positions are shown in Figure 11.3. The read-only iterator classes are QVectorIterator<T>, QLinkedListIterator<T>, and QListIterator<T>. The corresponding read-write iterators have Mutable in their name (e.g., QMutableVectorIterator<T>). In this discussion, we will concentrate on QList's iterators; the iterators for linked lists and vectors have the same API.

11fig03.gif

Figure 11.3 Valid positions for Java-style iterators

The first thing to keep in mind when using Java-style iterators is that they don't point directly at items. Instead, they can be located before the first item, after the last item, or between two items. A typical iteration loop looks like this:

QList<double> list;
...
QListIterator<double> i(list);
while (i.hasNext()) {
    do_something(i.next());
}

The iterator is initialized with the container to traverse. At this point, the iterator is located just before the first item. The call to hasNext() returns true if there is an item to the right of the iterator. The next() function returns the item to the right of the iterator and advances the iterator to the next valid position.

Iterating backward is similar, except that we must first call toBack() to position the iterator after the last item:

QListIterator<double> i(list);
i.toBack();
while (i.hasPrevious()) {
    do_something(i.previous());
}

The hasPrevious() function returns true if there is an item to the left of the iterator; previous() returns the item to the left of the iterator and moves the iterator back by one position. Another way to think about the next() and previous() iterators is that they return the item that the iterator has just jumped over, as Figure 11.4 illustrates.

11fig04.gif

Figure 11.4 Effect of and on a Java-style iterator

Mutable iterators provide functions to insert, modify, and remove items while iterating. The following loop removes all the negative numbers from a list:

QMutableListIterator<double> i(list);
while (i.hasNext()) {
    if (i.next() < 0.0)
        i.remove();
}

The remove() function always operates on the last item that was jumped over. It also works when iterating backward:

QMutableListIterator<double> i(list);
i.toBack();
while (i.hasPrevious()) {
    if (i.previous() < 0.0)
        i.remove();
}

Similarly, the mutable Java-style iterators provide a setValue() function that modifies the last item that was jumped over. Here's how we would replace negative numbers with their absolute value:

QMutableListIterator<double> i(list);
while (i.hasNext()) {
    int val = i.next();
    if (val < 0.0)
        i.setValue(-val);
}

It is also possible to insert an item at the current iterator position by calling insert(). The iterator is then advanced to point between the new item and the following item.

In addition to the Java-style iterators, every sequential container class C<T> has two STL-style iterator types: C<T>::iterator and C<T>::const_iterator. The difference between the two is that const_iterator doesn't let us modify the data.

A container's begin() function returns an STL-style iterator that refers to the first item in the container (e.g., list[0]), whereas end() returns an iterator to the "one past the last" item (e.g., list[5] for a list of size 5). Figure 11.5 shows the valid positions for STL-style iterators. If a container is empty, begin() equals end(). This can be used to see whether the container has any items, although it is usually more convenient to call isEmpty() for this purpose.

11fig05.gif

Figure 11.5 Valid positions for STL-style iterators

The STL-style iterator syntax is modeled after that of C++ pointers into an array. We can use the ++ and -- operators to move to the next or previous item, and the unary * operator to retrieve the current item. For QVector<T>, the iterator and const_iterator types are merely typedefs for T * and const T *. (This is possible because QVector<T> stores its items in consecutive memory locations.)

The following example replaces each value in a QList<double> with its absolute value:

QList<double>::iterator i = list.begin();
while (i != list.end()) {
    *i = qAbs(*i);
    ++i;
}

A few Qt functions return a container. If we want to iterate over the return value of a function using an STL-style iterator, we must take a copy of the container and iterate over the copy. For example, the following code is the correct way to iterate over the QList<int> returned by QSplitter::sizes():

QList<int> list = splitter->sizes();
QList<int>::const_iterator i = list.begin();
while (i != list.end()) {
    do_something(*i);
    ++i;
}

The following code is wrong:

// WRONG
QList<int>::const_iterator i = splitter->sizes().begin();
while (i != splitter->sizes().end()) {
    do_something(*i);
    ++i;
}

This is because QSplitter::sizes() returns a new QList<int> 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: When using STL-style iterators, always iterate on a copy of a container returned by value.

With read-only Java-style iterators, we don't need to take a copy. The iterator takes a copy for us behind the scenes, ensuring that we always iterate over the data that the function first returned. For example:

QListIterator<int> i(splitter->sizes());
while (i.hasNext()) {
    do_something(i.next());
}

Copying a container like this sounds expensive, but it isn't, thanks to an optimization called implicit sharing. This means that copying a Qt container is about as fast as copying a single pointer. Only if one of the copies is changed is data actually copied—and this is all handled automatically behind the scenes. For this reason, implicit sharing is sometimes called "copy on write".

The beauty of implicit sharing is that it is an optimization that we don't need to think about; it simply works, without requiring any programmer intervention. At the same time, implicit sharing encourages a clean programming style where objects are returned by value. Consider the following function:

QVector<double> sineTable()
{
    QVector<double> vect(360);
    for (int i = 0; i < 360; ++i)
        vect[i] = std::sin(i / (2 * M_PI));
    return vect;
}

The call to the function looks like this:

QVector<double> table = sineTable();

STL, in comparison, encourages us to pass the vector as a non-const reference to avoid the copy that takes place when the function's return value is stored in a variable:

void sineTable(std::vector<double> &vect)
{
    vect.resize(360);
    for (int i = 0; i < 360; ++i)
        vect[i] = std::sin(i / (2 * M_PI));
}

The call then becomes more tedious to write and less clear to read:

std::vector<double> table;
sineTable(table);

Qt uses implicit sharing for all of its containers and for many other classes, including QByteArray, QBrush, QFont, QImage, QPixmap, and QString. This makes these classes very efficient to pass by value, both as function parameters and as return values.

Implicit sharing is a guarantee from Qt that the data won't be copied if we don't modify it. To get the best out of implicit sharing, we can adopt a couple of new programming habits. One habit is to use the at() function rather than the [] operator for read-only access on a (non-const) vector or list. Since Qt's containers cannot tell whether [] appears on the left side of an assignment or not, it assumes the worst and forces a deep copy to occur—whereas at() isn't allowed on the left side of an assignment.

A similar issue arises when we iterate over a container with STL-style iterators. Whenever we call begin() or end() on a non-const container, Qt forces a deep copy to occur if the data is shared. To prevent this inefficiency, the solution is to use const_iterator, constBegin(), and constEnd() whenever possible.

Qt provides one last method for iterating over items in a sequential container: the foreach loop. It looks like this:

QLinkedList<Movie> list;
...
foreach (Movie movie, list) {
    if (movie.title() == "Citizen Kane") {
        std::cout << "Found Citizen Kane" << std::endl;
        break;
    }
}

The foreach pseudo-keyword is implemented in terms of the standard for loop. At each iteration of the loop, the iteration variable (movie) is set to a new item, starting at the first item in the container and progressing forward. The foreach loop automatically takes a copy of the container when the loop is entered, and for this reason the loop is not affected if the container is modified during iteration.

The break and continue loop statements are supported. If the body consists of a single statement, the braces are unnecessary. Just like a for statement, the iteration variable can be defined outside the loop, like this:

QLinkedList<Movie> list;
Movie movie;
...
foreach (movie, list) {
    if (movie.title() == "Citizen Kane") {
        std::cout << "Found Citizen Kane" << std::endl;
        break;
    }
}

Defining the iteration variable outside the loop is the only option for containers that hold data types that contain a comma (e.g., QPair<QString, int>).

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.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020