/****************************************************************************
** $Id:  qt/qtl.doc   3.0.3   edited Jan 18 14:12 $
**
** Qt Template Library classes documentation
**
** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
**
** This file is part of the Qt GUI Toolkit.
**
** This file may be distributed under the terms of the Q Public License
** as defined by Trolltech AS of Norway and appearing in the file
** LICENSE.QPL included in the packaging of this file.
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.
**
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
** licenses may use this file in accordance with the Qt Commercial License
** Agreement provided with the Software.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
**   information about Qt Commercial License Agreements.
** See http://www.trolltech.com/qpl/ for QPL licensing information.
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact info@trolltech.com if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

/*! 

\page qt-template-lib.html

\title Qt Template Library

The Qt Template Library (QTL) is a set of templates that provide
object containers.  If a suitable STL implementation is not
available for your compiler, the QTL can be used instead.  It
provides a list of objects, a vector (dynamic array) of objects, a map
(or dictionary) from one type to another, and associated <a
href="#Iterators">iterators</a> and <a
href="#Algorithms">algorithms</a>.  A container is an object which
contains and manages other objects and provides iterators that allow
the contained objects to be accessed.

The QTL classes' naming conventions are consistent with the other Qt
classes (e.g., count(), isEmpty()). They also provide extra functions
for compatibility with STL algorithms, such as size() and empty().
Programmers already familiar with the STL \c map can use these
functions instead.

Compared to the STL, the QTL contains only the most important
features of the STL container API, has no platform differences, is
often a little slower and often expands to less object code.

If you cannot make copies of the objects you want to store you are
better off with QPtrCollection and friends. They were designed to handle
exactly that kind of pointer semantics. This applies for example to
all classes derived from \l QObject. A QObject does not have a copy
constructor, so using it as value is impossible. You may choose to
store pointers to QObjects in a QValueList, but using QPtrList directly
seems to be the better choice for this kind of application
domain. QPtrList, like all other QPtrCollection based containers, provides
far more sanity checking than a speed-optimized value based container.

If you have objects that implement value semantics, and the STL is not
available on your target platform, the Qt Template Library can be used
instead.  Value semantics require at least 

\list 
	\i a copy constructor, 
	\i an assignment operator and 
	\i a defaultconstructor, i.e. a constructor that does not take any arguments.
\endlist

Note that a fast copy constructor is absolutely crucial for a good
overall performance of the container, since many copy operations are
going to happen.

If you intend sorting your data you must implement \c{operator<()} for
your data's class.

Good candidates for value based classes are QRect, QPoint, QSize,
QString and all simple C++ types, such as int, bool or double.

The Qt Template Library is designed for speed. Iterators are extremely
fast. To achieve this performance, less error checking is done than in
the QPtrCollection based containers. A QTL container, for example,
does not track any associated iterators. This makes certain validity
checks, for example when removing items, impossible to perform
automatically, however it provides extremely good performance.

\target Iterators
\section1 Iterators

The Qt Template Library deals with value objects, not with pointers.
For that reason, there is no other way of iterating over containers
other than with iterators. This is no disadvantage as the size of an
iterator matches the size of a normal pointer.

To iterate over a container, use a loop like this:

\code
    typedef QValueList<int> List;
    List l;
    for( List::Iterator it = l.begin(); it != l.end(); ++it )
	printf( "Number is %i\n", *it );
\endcode

begin() returns the iterator pointing at the first element, while
end() returns an iterator that points \e after the last
element. end() marks an invalid position, it can never be
dereferenced. It's the break condition in any iteration, may it be
from begin() or fromLast(). For maximum speed, use increment or
decrement iterators with the prefix operator (++it, --it) instead of the
postfix one (it++, it--), since the former is slightly faster.

The same concept applies to the other container classes:

\code
    typedef QMap<QString,QString> Map;
    Map map;
    for( Map::iterator it = map.begin(); it != map.end(); ++it )
	printf( "Key=%s Data=%s\n", it.key().ascii(), it.data().ascii() );

    typedef QValueVector<int> Vector;
    Vector vec;
    for( Vector::iterator it = vec.begin(); it != vec.end(); ++it )
	printf( "Data=%d\n", *it );
\endcode

There are two kind of iterators, the volatile iterator shown in the
examples above and a version that returns a const reference to its
current object, the ConstIterator. Const iterators are required
whenever the container itself is const, such as a member variable
inside a const function. Assigning a ConstIterator to a normal
Iterator is not allowed as it would violate const semantics.

\target Algorithms
\section1 Algorithms

The Qt Template Library defines a number of algorithms that operate on
its containers.  These algorithms are implemented as template
functions and provide useful generic code which can be applied to any
container that provides iterators (even your own containers).

qHeapSort() and qBubbleSort() provide the well known sorting
algorithms. You can use them like this:

\code
    typedef QValueList<int> List;
    List l;
    l << 42 << 100 << 1234 << 12 << 8;
    qHeapSort( l );

    List l2;
    l2 << 42 << 100 << 1234 << 12 << 8;
    List::Iterator b = l2.find( 100 );
    List::Iterator e = l2.find( 8 );
    qHeapSort( b, e );

    double arr[] = { 3.2, 5.6, 8.9 };
    qHeapSort( arr, arr + 3 );
\endcode

The first example sorts the entire list. The second one sorts all
elements enclosed in the two iterators, namely 100, 1234 and 12.  The
third example shows that iterators act like pointers and can be
treated as such.

If using your own data types you must implement \c{operator<()} for
your data's class.

Naturally, the sorting templates won't work with const iterators.

\target qSwap
Another utility is qSwap(). It exchanges the values of two variables:

\code
    QString second( "Einstein" );
    QString name( "Albert" );
    qSwap( second, name );
\endcode

\target qCount
Another template function is qCount().  It counts the number of
occurrences of a value within a container.  For example:
\code
    QValueList<int> l;
    l.push_back( 1 );	       
    l.push_back( 1 );	       
    l.push_back( 1 );	       
    l.push_back( 2 );	       
    int c = 0;
    qCount( l.begin(), l.end(), 1, c ); // c == 3
\endcode	

\target qFind
Another template function is qFind.  It find the first occurrence of a
value within a container. For example:

\code
    QValueList<int> l;
    l.push_back( 1 );	       
    l.push_back( 1 );	       
    l.push_back( 1 );	       
    l.push_back( 2 );	       
    QValueListIterator<int> it = qFind( l.begin(), l.end(), 2 );
\endcode	

\target qFill
Another template function is qFill.  It fills a
range with copies of a value.  For example:

\code
    QValueVector<int> v(3);
    qFill( v.begin(), v.end(), 99 ); // v contains 99, 99, 99
\endcode

\target qEqual
Another template function is qEqual.  It compares
two ranges for equality of their elements.  Note that the number of
elements in each range is not considered, only if the elements in the
first range are equal to the corresponding elements in the second
range (consequently, both ranges must be valid).  For example:

\code
    QValueVector<int> v1(3);
    v1[0] = 1;
    v1[2] = 2;
    v1[3] = 3;

    QValueVector<int> v2(5);
    v1[0] = 1;
    v1[2] = 2;
    v1[3] = 3;
    v1[4] = 4;
    v1[5] = 5;

    bool b = qEqual( v1.begin(), v2.end(), v2.begin() );
    // b == TRUE
\endcode

\target qCopy
Another template function is qCopy(). It copies a
range of elements to an OutputIterator, in this case a
QTextOStreamIterator:

\code
    QValueList<int> l;
    l.push_back( 100 );
    l.push_back( 200 );
    l.push_back( 300 );
    QTextOStream str( stdout );
    qCopy( l.begin(), l.end(), QTextOStreamIterator(str) );
\endcode

\omit
Here is another example which copies a range of elements from one
container into another.  It uses the qBackInserter() template function
which creates a QBackInsertIterator<> whose job is to insert elements
into the end of a container.  For example:

\code
    QValueList<int> l;
    l.push_back( 100 );
    l.push_back( 200 );
    l.push_back( 300 );
    QValueVector<int> v;
    qCopy( l.begin(), l.end(), qBackInserter(v) );
\endcode
\endomit

\target qCopyBackward
Another template function is
qCopyBackward().  It copies a container or a slice of it to an
OutputIterator, but in backwards fashion, for example:

\code
    QValueVector<int> vec(3);
    vec.push_back( 100 );
    vec.push_back( 200 );
    vec.push_back( 300 );
    QValueVector<int> another;
    qCopyBackward( vec.begin(), vec.end(), another.begin() );
    // 'another' now contains 100, 200, 300
    // however the elements are copied one at a time 
    // in reverse order (300, 200, then 100)
\endcode

\target qMakePair
Another template function is qMakePair(). This is a convenience
function which is used for creating QPair\<\> objects.  For example:
\code
    QMap<QString,QString> m;
    m.insert( qMakePair("Clinton", "Bill") );
\endcode

The above code is equivalent to:
\code
    QMap<QString,QString> m;
    QPair<QString,QString> p( "Clinton", "Bill" );
    m.insert( p );
\endcode

In addition, you can use any Qt Template Library iterator as the
OutputIterator. Just make sure that the right hand of the iterator has
as many elements present as you want to insert. The following example
illustrates this:

\code
    QStringList l1, l2;
    l1 << "Weis" << "Ettrich" << "Arnt" << "Sue";
    l2 << "Torben" << "Matthias";
    qCopy( l2.begin(), l2.end(), l1.begin() );

    QValueVector<QString> v( l1.size(), "Dave" );
    qCopy( l2.begin(), l2.end(), v.begin() );
\endcode

At the end of this code fragment, the list l1 contains "Torben",
"Matthias", "Arnt" and "Sue", with the prior contents being
overwritten.  The vector v contains "Torben", "Matthias", "Dave"
and "Dave, also with the prior contents being overwritten.

If you write new algorithms, consider writing them as template
functions in order to make them usable with as many containers
possible.  In the above example, you could just as easily print out a
standard C++ array with qCopy():

\code
    int arr[] = { 100, 200, 300 };
    QTextOStream str( stdout );
    qCopy( arr, arr + 3, QTextOStreamIterator( str ) );	
\endcode


\section1 Streaming

All mentioned containers can be serialized with the respective
streaming operators. Here is an example.

\code
    QDataStream str(...);
    QValueList<QRect> l;
    // ... fill the list here
    str << l;
\endcode

The container can be read in again with:

\code
    QValueList<QRect> l;
    str >> l;
\endcode

The same applies to QStringList, QValueStack and QMap.
*/