Collection Classes

A collection class is a class that can contain a number of items in a certain data structure and perform operations on the contained items; insert, remove, find etc.

Qt has many reference based collection classes and some value based collections.

The reference based collections are:

• QCache QCache and QIntCache LRU (least recently used) cache structures.
• QDict, QIntDict and QPtrDict dictionary structures.
• QList a double linked list structure.
• QQueue a FIFO (first in, first out) queue structure.
• QStack a LIFO (last in, first out) stack structure.
• QVector a vector structure.

The value based collections are:

• QValueList a value based list
• QValueStack a value based stack structure
• QMap a value based dictionary structure

The reference based collection classes work with pointers to items, while the value based classes store copies of their items. An exception is QArray. It is neither reference nor value based, but memory based. For maximum efficiency with the simple data types usually used in arrays, it uses bitwise operations to copy and compare array elements.

Some of these classes have corresponding iterators. An iterator is a class for traversing the items in a collection:

• QCacheIterator and QIntCacheIterator
• QDictIterator, QIntDictIterator, and QPtrDictIterator
• QListIterator
• QValueListIterator, and QValueListConstIterator
• QMapIterator, and QMapConstIterator

The value based collections plus algorithms operating on them are grouped together in the Qt Template Library. See the respective documentation for details. The rest of this page talks about the reference based containers only.

Architecture of the reference based containers

There are three internal base classes for the reference based containers; QGCache, QGDict and QGList that operate on void* pointers. A thin template layer implements the actual collections by casting item pointers to and from void*.

This strategy allows Qt's templates to be very economical on space (instantiating one of these templates adds only inline-able calls to the base classes), while it does not hurt performance too much.

A QList Example

This example shows how to store Employee items in a list and prints them out in the reverse order:

    #include <qlist.h>
    #include <qstring.h>
    #include <stdio.h>

    class Employee
    {
    public:
        Employee( const char *name, int salary ) { n=name; s=salary; }
        const char *name()   const               { return n; }
        int         salary() const               { return s; }
    private:
        QString     n;
        int         s;
    };

    void main()
    {
        QList<Employee> list;           // list of pointers to Employee
        list.setAutoDelete( TRUE );     // delete items when they are removed

        list.append( new Employee("Bill", 50000) );
        list.append( new Employee("Steve",80000) );
        list.append( new Employee("Ron",  60000) );

        QListIterator<Employee> it(list); // iterator for employee list
        for ( it.toLast(); it.current(); --it) ) {
            Employee *emp = it.current();
            printf( "%s earns %d\n", emp->name(), emp->salary() );
        }
    }

Program output:

        Ron earns 60000
        Steve earns 80000
        Bill earns 50000

Managing Collection Items

All reference based collections inherit the QCollection base class. This class knows only the number of items in the collection and the delete strategy.

Items in a collection are by default not deleted when they are removed from the collection. The QCollection::setAutoDelete() function specifies the delete strategy. In the list example, we enable auto-deletion to make the list delete the items when they are removed from the list.

When inserting an item into a collection, only the pointer is copied, not the item itself. This is called a shallow copy. It is possible to make the collection copy all of the item's data (known as a deep copy) when an item is inserted. All collection functions that insert an item call the virtual function QCollection::newItem() for the item to be inserted. Inherit a collection and reimplement it if you want to have deep copies in your collection.

When removing an item from a list, the virtual function QCollection::deleteItem() is called. The default implementation in all collection classes deletes the item if auto-deletion is enabled.

Usage

A reference based collection class, such as QList<type>, defines a collection of pointers to type objects. The pointer (*) is implicit.

We discuss QList here, but the same techniques apply for all reference based collection classes and all collection class iterators.

Template instantiation:

  QList<Employee> list;         // wherever the list is used

The item's class or type, Employee in our example, must be defined prior to the list definition.

  // Does not work: Employee is not defined
  class Employee;
  QList<Employee> list;

  // This works: Employee is defined before it is used
  class Employee {
    ...
  };
  QList<Employee> list;

Iterators

Although QList has member functions to traverse the list, it can often be better to make use of an iterator. QListIterator is very safe and can traverse lists that are being modified at the same time. Multiple iterators can work independently on the same collection.

A QList has an internal list of all iterators that are currently operating on the list. When a list entry is removed, the list updates all iterators to point to this entry.

The QDict and QCache collections have no traversal functions. To traverse these collections, you must use QDictIterator or QCacheIterator.

Predefined Collections

Qt has the following predefined collection classes:

• String lists; QStrList, QStrIList (qstrlist.h ) and QStringList (qstringlist.h )
• String vectors; QStrVec and QStrIVec (qstrvec.h )

In almost all cases you would choose QStringList, which is a value list of implicitly shared QString unicode strings. QStrList and QStrIList only store char* pointers.

Comparison with the STL

We often get questions about why Qt does not use the STL, and why Qt's container templates are provided at all. Here are the major factors why we use and provide these templates:

• Qt's reference based container templates add less space when instantiated than the STL ones do. Size is important for a library, and Qt contains many instantiations of QDict, QList etc.
• Qt's reference based containers are often not as fast as the STL's, for several reasons such as Qt's safe iterators. This is however not very important for Qt, as they are used in code that doesn't need to be very fast. (The speed-critical data structures in Qt are mostly caches - either QCache instantiations or custom-written, custom-optimized ones.)
• Qt's containers are much more portable than the STL. When we started writing Qt, STL was far away in the future, and when we released Qt 1.0, no widely-used compilers could compile the STL. For a library such as Qt, it is of course very important to compile on the widest possible variety of compilers. Even today, the STL is not portable across all platforms supported by Qt.
• Though primarily written for use internally in Qt, the containers are well documented and so we saw no reason to hide them.

Value based containers in the style of the STL do have one major advantage, though: They are extremely efficient when being used with value objects that implement a fast copy constructor. This is the case with all implicit shared Qt classes such as QString or any of the C++ standard data types like int, bool or double. Since we needed that functionality for Qt itself, we added a few value based containers in Qt-2.0. As with the other containers, the new ones have a well documented interface and a naming scheme that matches the usual Qt conventions - another advantage over the STL classes.

There are other differences, but the ones above are the important reasons behind our decision to write, use and provide these classes.

Classes:

• QAsciiCache (Template class that provides a cache based on char* keys)
• QAsciiCacheIterator (Iterator for QAsciiCache collections)
• QAsciiDict (Template class that provides a dictionary based on char* keys)
• QAsciiDictIterator (Iterator for QAsciiDict collections)
• QCache (Template class that provides a cache based on QString keys)
• QCacheIterator (Iterator for QCache collections)
• QCollection (The base class of all Qt collections)
• QDict (Template class that provides a dictionary based on QString keys)
• QDictIterator (Iterator for QDict collections)
• QIntCache (Template class that provides a cache based on long keys)
• QIntCacheIterator (Iterator for QIntCache collections)
• QIntDict (Template class that provides a dictionary based on long keys)
• QIntDictIterator (Iterator for QIntDict collections)
• QList (Template class that provides doubly linked lists)
• QListIterator (Iterator for QList collections)
• QObjectList (QList of QObjects)
• QPtrDict (Template class that provides a dictionary based on void* keys)
• QPtrDictIterator (Iterator for QPtrDict collections)
• QQueue (Template class that provides a queue)
• QSortedList (List sorted by operator< and operator==)
• QStack (Template class that provides a stack)
• QStrIList (Doubly linked list of char* with case insensitive compare)
• QStrList (Doubly linked list of char*.)