# 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 collection classes:

- QCache and QIntCache; LRU (least recently used) cache structures.
- QDict and QIntDict; dictionary structures.
- QList; a doubly 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.

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

- QCacheIterator and QIntCacheIterator
- QDictIterator and QIntDictIterator
- QListIterator

The collection classes work with pointers to items. Qt has an array template class, QArray, which stores the items directly in the array. QArray only works for classes that do not have a constructor, a destructor or any virtual functions.

## Architecture

Basically, there are two different implementation strategies for collection classes.

1. The collection can only contain objects that inherit a special collectable class. This is the Smalltalk way of doing it.
2. The collection is a template (generic) class. Specific collections must be instantiated from the template. This allows any object to be stored in a collection.

In Qt, we have chosen the second approach. There are three internal base classes; 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. Qt's templates do not afford as much scope for optimization as the STL templates do, so for applications where speed is critical and code size is less important, the STL is preferable.

## A List 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 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 is to delete the item if auto-deletion is enabled.

## Templates and Macros

A template-based collection, for instance QList<type>, defines a collection of pointers to type objects. The pointer (*) is implicit.

We discuss QList here, but the same applies for all 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;

The list can also be instantiated through a macro expansion. This is necessary only for compilers that do not support templates.

Macro instantiation:

      Q_DECLARE(QListM,Employee);   // declare once (for instance in a .h file)
        ...
      QListM(Employee) list;        // wherever the list is used

If you want to make your code work for compilers that do not have template support, but use templates if they are available, you can use `typedef:`

        ...
      #if defined(USE_TEMPLATECLASS)
      typedef QListT<Employee>         EmployeeList;
      #else
      typedef Q_DECLARE(QListM,Employee) EmployeeList;
      #endif

      void main()
      {
          EmployeeList list;        // list of pointers to Employee
          ...

`USE_TEMPLATECLASS` is defined in qglobal.h.

QListT refers to the QList template and QListM refers to the QList macro. QList defaults to QListT if templates are supported, QListM otherwise.

We recommend using templates, because macro collections are harder to debug. C++ debuggers understand templates but not macros.

## 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 the these collections, you must use QDictIterator or QCacheIterator .

## Predefined Collections

Qt has the following predefined collection classes:

- String lists; QStrList and QStrIList (qstrlist.h)
- String vectors; QStrVec and QStrIVec (qstrvec.h)

## Comparison with the STL

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

- Qt's 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 containers are often not as fast as the STL's, for several reasons. 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 is. 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.

- Qt's containers are documented because we document our APIs, and the containers and their documentation are provided as parts of Qt's external API because we saw no reason to hide them.

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

  Classes:

  - QCache (Template class that provides a cache based on `char*` keys)
  - QCacheIterator (Iterator for QCache collections)
  - QCollection (The base class of all Qt collections)
  - QDict (Template class that provides a dictionary based on `char*` 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)
  - QPtrDict (Template class that provides a dictionary based on `void*` keys)
  - QPtrDictIterator (Iterator for QPtrDict collections)
  - QQueue (Template class that provides a queue)
  - QStack (Template class that provides a stack)
  - QStrIList (Doubly linked list of `char*` with case insensitive compare)
  - QStrList (Doubly linked list of `char*.`)