/****************************************************************************
** $Id$
**
** 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 qtl.html

\title Qt Template library

Thq Qt Template Library is a set of templates within Qt dealing with
containers of objects.  It provides a list of objects, a stack of
objects, a map (or dictionary) from one type to another, and
associated iterators and algorithms.

Qt also contains similar classes that deal with pointers to objects;
\l QValueList vs. \l QList, etc.  Compared to the pointer-based
templates, the QTL offers easy copying of the container, real support
for classes that e.g. require constructors, expand to much more object
code, can often be a bit faster, require that the objects stored can
be copied, and finally, have a worse record of compiler problems.

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


If you can not make copies of the objects you want to store you are
better off with QCollection 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 be
store pointers to QObjects in a QValueList, but using QList directly
seems to be the better choice for this kind of application
domain. QList, like all other QCollection based containers, provides
far more sanity checking than a speed-optimized value
based container.

If you have objects that implement value semantics, use the Qt
template library.  Value semantics require at least
<ul>
<li>a copy constructor,
<li>an assignment operator and
<li> a default constructor, i.e. a constructor that does not take
any arguments.
</ul>
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.

Examples for value based classes are QRect, QPoint, QSize and all
simple C++ types like int, bool or double.

The Qt template library is designed for speed. Especially iterators
are extremely fast. On the drawback side, less error checking is done
than in the QCollection based containers. A template library container
for example does not track associated iterators. This makes certain
validity checks, like on removing items, impossible to perform
automatically.

<h2> Iterators </h2>

The Qt template library deals with value objects, not with pointers.
For that reason, there is no other way of iterating over containers
than using iterators. This is no disadvantage as the size of an
iterator matches the size of a normal pointer - 32 or 64 bits
depending on your CPU architecture.

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 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 QArray<int> Array;
	Array array;
	for( Array::Iterator it = array.begin(); it != array.end(); ++it )
		printf("Data=%i\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.

<h2> Algorithms </h2>

The template library defines a number of algorithms that operate on
its containers: qHeapSort(), qBubbleSort(), qSwap() and
qCopy(). These algorithms are implemented as template functions.

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.

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

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

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

Another template function is qCopy(). It copies a container or a slice
of it to an OutputIterator, in this case a QTextOStreamIterator:

\code
	typedef QValueList<int> List;
	List l;
	l << 100 << 200 << 300;
	QTextOStream str( stdout );
	qCopy( l, QTextOStreamIterator( str ) );
\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, l1.begin();
\endcode

At the end of this code fragment, the List l1 contains "Torben",
"Matthias", "Arnt" and "Sue", with the prior contents being
overwritten. Another flavor of qCopy() takes three arguments to make
it possible to copy a slice of a container:

\code
	typedef QValueList<int> List;
	List l;
	l << 42 << 100 << 1234 << 12 << 8;
	List::Iterator b = l.find( 100 );
	List::Iterator e = l.find( 8 );
	QTextOStream str( stdout );
	qCopy( b, e, QTextOStreamIterator( str ) );
\endcode

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


<h2> Streaming </h2>

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.

*/