Question

A collection class is a container which holds a number of items in a certain data structure and performs operations on the contained items; insert, remove, find etc.

Qt has several value-based and several pointer-based collection classes. The pointer-based collection classes work with pointers to items, while the value-based classes store copies of their items. The value-based collections are very similar to STL container classes, and can be used with STL algorithms and containers. See the Qt Template Library documentation for details.

The value-based collections are:

• QValueList, a value-based list
• QValueVector, a value-based vector structure
• QValueStack, a value-based stack structure
• QMap, a value-based dictionary structure

The pointer-based collections are:

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

QMemArray is exceptional; it is neither pointer 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
• QPtrListIterator
• 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 dicusses the pointer-based containers.

Architecture of the pointer-based containers

There are four internal base classes for the pointer-based containers (QGCache, QGDict, QGList and QGVector) that operate on void pointers. A thin template layer implements the actual collections by casting item pointers to and from void pointers.

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

A QPtrList Example

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

    #include <qptrlist.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;
    };

    int main()
    {
        QPtrList<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) );

        QPtrListIterator<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() );
        }

        return 0;
    }

Program output:

    Ron earns 60000
    Steve earns 80000
    Bill earns 50000

Managing Collection Items

All pointer-based collections inherit the QPtrCollection 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 QPtrCollection::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 QPtrCollection::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 QPtrCollection::deleteItem() is called. The default implementation in all collection classes deletes the item if auto-deletion is enabled.

Usage

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

We discuss QPtrList here, but the same techniques apply for all pointer-based collection classes and all collection class iterators.

Template instantiation:

    QPtrList<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;
    QPtrList<Employee> list;

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

Iterators

Although QPtrList has member functions to traverse the list, it can often be better to make use of an iterator. QPtrListIterator 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 QPtrList 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); these are obsolete

In almost all cases you would choose QStringList, a value list of implicitly shared QString unicode strings. QPtrStrList and QPtrStrIList store only char pointers, not the strings themselves.

List of Pointer-based Collection Classes and Related Iterator 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
QBitArray	Array of bits
QBitVal	Internal class, used with QBitArray
QBuffer	I/O device that operates on a QByteArray
QByteArray	Array of bytes
QCache	Template class that provides a cache based on QString keys
QCacheIterator	Iterator for QCache collections
QCString	Abstraction of the classic C zero-terminated char array (char *)
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
QObjectList	QPtrList of QObjects
QObjectListIt	Iterator for QObjectLists
QPtrCollection	The base class of most pointer-based Qt collections
QPtrDict	Template class that provides a dictionary based on void* keys
QPtrDictIterator	Iterator for QPtrDict collections
QPtrList	Template class that provides doubly-linked lists
QPtrListIterator	Iterator for QPtrList collections
QPtrQueue	Template class that provides a queue
QStrIList	Doubly-linked list of char* with case-insensitive comparison
QStrList	Doubly-linked list of char*