/****************************************************************************
**
** Qt Template Library classes documentation
**
** Copyright (C) 1992-2008 Trolltech ASA.  All rights reserved.
**
** This file is part of the Qt GUI Toolkit.
**
** This file may be used under the terms of the GNU General
** Public License versions 2.0 or 3.0 as published by the Free
** Software Foundation and appearing in the files LICENSE.GPL2
** and LICENSE.GPL3 included in the packaging of this file.
** Alternatively you may (at your option) use any later version
** of the GNU General Public License if such license has been
** publicly approved by Trolltech ASA (or its successors, if any)
** and the KDE Free Qt Foundation.
**
** Please review the following information to ensure GNU General
** Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/.
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at sales@trolltech.com.
**
** This file may be used under the terms of the Q Public License as
** defined by Trolltech ASA and appearing in the file LICENSE.QPL
** included in the packaging of this file.  Licensees holding valid Qt
** Commercial 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 WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
** A PARTICULAR PURPOSE. Trolltech reserves all rights not granted
** herein.
**
**********************************************************************/

/*! 

\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
on all your target platforms, the QTL can be used instead. It provides
a list of objects, a vector (dynamic array) of objects, a map relating
one type to another (also called a dictionary or associative array),
and associated \link #Iterators iterators\endlink and \link
#Algorithms algorithms\endlink. 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 the
STL-compatible functions if preferred.

Compared to the STL, the QTL only contains the most important features
of the STL container API. Compared with the STL, QTL has no platform
differences, but 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 should
use QPtrCollection and friends, all of which operate on pointers
rather than values. 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;
\i a defaultconstructor, i.e. a constructor that does not take any arguments.
\endlist

Note that a fast copy constructor is absolutely crucial to achieve
good overall performance of the container, since many copy operations
will occur.

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, but does lead to 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 list;
    for( List::Iterator it = list.begin(); it != list.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, so it can never be dereferenced. It's the
break condition in any iteration, whether the start point is from
begin() or fromLast(). For maximum speed, use increment or decrement
iterators with the prefix operator (++it, --it) instead of the postfix
operator (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 (including your own containers).

\section2 qHeapSort()

qHeapSort() provides a well known sorting algorithm. You can use it
like this:
\code
    typedef QValueList<int> List;
    List list;
    list << 42 << 100 << 1234 << 12 << 8;
    qHeapSort( list );

    List list2;
    list2 << 42 << 100 << 1234 << 12 << 8;
    List::Iterator b = list2.find( 100 );
    List::Iterator e = list2.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 example sorts only
those elements that fall between the two iterators, i.e. 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
\section2 qSwap()

qSwap() exchanges the values of two variables:
\code
    QString second( "Einstein" );
    QString name( "Albert" );
    qSwap( second, name );
\endcode

\target qCount
\section2 qCount()

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

\target qFind
\section2 qFind()

The qFind() template function finds the first occurrence of a value
within a container. For example:
\code
    QValueList<int> list;
    list.push_back( 1 );	       
    list.push_back( 1 );	       
    list.push_back( 1 );	       
    list.push_back( 2 );	       
    QValueListIterator<int> it = qFind( list.begin(), list.end(), 2 );
\endcode	

\target qFill
\section2 qFill()

The qFill() template function fills a range with copies of a value.
For example:
\code
    QValueVector<int> vec(3);
    qFill( vec.begin(), vec.end(), 99 ); // vec contains 99, 99, 99
\endcode

\target qEqual
\section2 qEqual()

The qEqual() template function 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);
    v2[0] = 1;
    v2[2] = 2;
    v2[3] = 3;
    v2[4] = 4;
    v2[5] = 5;

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

\target qCopy
\section2 qCopy()

The qCopy() template function copies a range of elements to an
OutputIterator, in this case a QTextOStreamIterator:
\code
    QValueList<int> list;
    list.push_back( 100 );
    list.push_back( 200 );
    list.push_back( 300 );
    QTextOStream str( stdout );
    qCopy( list.begin(), list.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
\section2 qCopyBackward()

The qCopyBackward() template function copies a container or a slice of
a container to an OutputIterator, but in reverse order, 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

\section2 QTL Iterators

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 list1, list2;
    list1 << "Weis" << "Ettrich" << "Arnt" << "Sue";
    list2 << "Torben" << "Matthias";
    qCopy( list2.begin(), list2.end(), list1.begin() );

    QValueVector<QString> vec( list1.size(), "Dave" );
    qCopy( list2.begin(), list2.end(), vec.begin() );
\endcode

At the end of this code fragment, the list list1 contains "Torben",
"Matthias", "Arnt" and "Sue", with the prior contents being
overwritten. The vector vec 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
as 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 the containers we've mentioned can be serialized with the
appropriate streaming operators. Here is an example.

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

The container can be read in again with:

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

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

/*!
    \fn QPair qMakePair(T1 t1, T2 t2)

    \relates QPair

    This is a template convenience function. It is used to create a
    QPair\<\> object that contains \a t1 and \a t2.
*/