1 /****************************************************************************
4 ** QValueList and QValueListIterator class documentation
6 ** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.
8 ** This file is part of the Qt GUI Toolkit.
10 ** This file may be distributed under the terms of the Q Public License
11 ** as defined by Trolltech AS of Norway and appearing in the file
12 ** LICENSE.QPL included in the packaging of this file.
14 ** This file may be distributed and/or modified under the terms of the
15 ** GNU General Public License version 2 as published by the Free Software
16 ** Foundation and appearing in the file LICENSE.GPL included in the
17 ** packaging of this file.
19 ** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
20 ** licenses may use this file in accordance with the Qt Commercial License
21 ** Agreement provided with the Software.
23 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
24 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
26 ** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
27 ** information about Qt Commercial License Agreements.
28 ** See http://www.trolltech.com/qpl/ for QPL licensing information.
29 ** See http://www.trolltech.com/gpl/ for GPL licensing information.
31 ** Contact info@trolltech.com if any conditions of this licensing are
34 **********************************************************************/
37 /*****************************************************************************
38 QValueList documentation
39 *****************************************************************************/
42 \class QValueList qvaluelist.h
43 \brief The QValueList class is a value based template class that provides doubly linked lists.
49 Define a template instance QValueList\<X\> to create a list of values which all
50 have the class X. Please notice that QValueList does not store pointers to the
51 members of the list. It holds a copy of every member. That is the reason why this
52 kind of classes are called "value based" while QList and QDict are "reference based".
54 Some classes can not be used within a QValueList, for example everything
55 derived from QObject and thus all classes that implement widgets.
56 Only values can be used in a QValueList. To qualify as a value, the class
59 <li>a copy constructor,
60 <li>an assignment operator and
61 <li> a default constructor, i.e. a constructor that does not take any arguments.
64 Note that C++ defaults to field-by-field assignment operators and
65 copy constructors if no explicit version is supplied. In many cases,
70 #include <qvaluelist.h>
78 Employee( const QString& name, int salary )
82 QString name() const { return n; }
83 int salary() const { return s; }
84 void setSalary( int salary ) { s = salary; }
92 typedef QValueList<Employee> EmployeeList;
93 EmployeeList list; // list of Employee
95 list.append( Employee("Bill", 50000) );
96 list.append( Employee("Steve",80000) );
97 list.append( Employee("Ron", 60000) );
99 Employee joe( "Joe", 50000 );
101 joe.setSalary( 4000 );
103 EmployeeList::Iterator it;
104 for( it = list.begin(); it != list.end(); ++it )
105 printf( "%s earns %d\n", (*it).name().latin1(), (*it).salary().latin1() );
117 As you can see, the latest changes to Joes salary did not affect the value
118 in the list because the list created a copy of Joes entry.
120 There are three ways of finding items in the list. The first one is by using
121 the at() function. It returns an iterator. The advantages of
122 getting an iterator is that you can now move forward or backward from this
123 position by incrementing/decrementing the iterator. To get the amount of
124 items in the list call count(). Valid indices are 0..count().
126 The second way of accessing a list is with operator[]. That means you can address
127 it like an array. The return value is a reference to the value stored in the list.
128 There exist two versions of this operator. The first one is const and returns a
129 const reference to the value. The second on is non const and returns a non const
130 reference to the value. It is up to your compiler to choose the correct one.
132 The third method is to use the functions begin() and end().
133 With a simple for loop as shown in the example you can iterate over the complete list.
134 It is save to have multiple iterators at the same time. If some member of the list is
135 removed then only iterators pointing to the removed member become invalid. Inserting in
136 the list does not invalidate any iterator. For convenience the function last() returns
137 an iterator for the last and first() for the first element in the list.
139 In addition you can search items in the list with the find() function. It exists in a const
140 and a non const version. It starts searching from the beginning of the list, but another
141 flavor of the find() function allows you to specify where searching should start.
142 If you just want to know whether a certain item is at least once in the list, then you
143 can use the contains() function.
145 Since QValueList is value based there is no need to care about deleting elements in the
146 list. The list holds its own copies and will free them if the corresponding member or
147 the list itself is deleted. You can force the list to free all of its item with clear().
149 QValueList is implicitly shared. That means you can just make copies of the list
150 in time O(1). If multiple QValueList instances share the same data and one
151 is doing a modification of the lists data then this modifying instance makes a copy
152 and modifies its private copy. So it does not affect the other instances.
153 From a developers point of view you can think that a QValueList and a copy of this
154 list have nothing to do with each other. Developers may only notice that copying is
155 very fast. People known to a CPUs MMU architecture will know this pattern as "copy on write".
157 There exist three functions to insert items in the list. append()
158 inserts an item at the end, prepend() inserts at the beginning
159 and insert() inserts in front of the position given by an iterator.
161 Items can be removed from the list in two ways. The first is to pass an iterator to
162 the remove(). The other possibility is to pass a value to remove() which will
163 delete all members which match this value.
165 Lists can be sorted with the algorithms provided by the <a
166 href="qtl.html">Qt Template Library</a>, for example with
179 \sa QValueListIterator
184 \fn QValueList::QValueList()
185 Constructs an empty list.
189 \fn QValueList::QValueList( const QValueList<T>& l )
190 Constructs a copy of \e l.
192 This operation costs O(1) time since QValueList is implicit shared.
193 The first instance applying modifications to a shared list will create
194 a copy which takes in turn O(n) time. However returning a QValueList from
195 a function is very fast.
199 \fn QValueList::~QValueList()
200 Destroys the list. References to the values in the list and all iterators
201 of this list become invalidated. Since QValueList is highly tuned for performance
202 you won't see warnings if you use invalid iterators,
203 because it is impossible for
204 an iterator to check whether it is valid or not.
208 \fn QValueList<T>& QValueList::operator= ( const QValueList<T>& l )
209 Assigns \e l to this list and returns a reference to this list.
211 All iterators of the current list become invalidated by this operation.
212 The cost of such an assignment is O(1) since QValueList is implicitly shared.
216 \fn QValueList<T> QValueList::operator+ ( const QValueList<T>& l ) const
217 Creates a new list and fills it with the elements of this list. Then the
218 elements of \e l are appended.
220 Returns the new list.
224 \fn QValueList<T>& QValueList::operator+= ( const QValueList<T>& l )
225 Adds \e list to this list.
227 Returns a reference to this list.
231 \fn bool QValueList::operator== ( const QValueList<T>& l ) const
234 Returns TRUE if both list are equal.
238 \fn bool QValueList::operator!= ( const QValueList<T>& l ) const
241 Returns TRUE if both list are unequal.
245 \fn QValueList<T>& QValueList::operator+= ( const T& x )
246 Adds the value \e x to the end of the list.
248 Returns a reference to the list.
252 \fn QValueList<T>& QValueList::operator<< ( const T& x )
253 Adds the value \e x to the end of the list.
255 Returns a reference to the list.
259 \fn const T& QValueList::operator[] ( uint i ) const
260 Returns a const reference to the item with index \e i in the list.
261 It is up to you to check whether this item really exists. You can do that easily
262 with the count() function. However this operator does not check whether \e i
263 is in range and will deliver undefined results if it does not exist.
267 \fn T& QValueList::operator[] ( uint i )
268 Returns a reference to the item with index \e i in the list.
269 It is up to you to check whether this item really exists. You can do that easily
270 with the count() function. However this operator does not check whether \e i
271 is in range and will deliver undefined results if it does not exist.
272 In contrast to the const operator[] you may manipulate the value returned by this
277 \fn uint QValueList::count() const
278 Returns the number of items in the list.
283 \fn bool QValueList::isEmpty() const
284 Returns TRUE if the list is empty, i.e. count() == 0. Returns FALSE
290 \fn Iterator QValueList::insert( Iterator it, const T& x )
291 Inserts the value \e x in front of the iterator \e it.
293 Returns an iterator pointing at the inserted item.
295 \sa append(), prepend()
299 \fn Iterator QValueList::append( const T& x )
300 Inserts the value \e x at the end of the list.
302 Returns an iterator pointing at the inserted item.
304 \sa insert(), prepend()
308 \fn Iterator QValueList::prepend( const T& x )
309 Inserts the value \e x at the beginning of the list.
311 Returns an iterator pointing at the inserted item.
313 \sa insert(), append()
317 \fn Iterator QValueList::remove( Iterator it )
318 Removes the item at position \e it in the list.
320 Returns an iterator pointing to the item following the
321 removed on or end() if the last item was deleted.
327 \fn void QValueList::remove( const T& x )
328 Removes all items which have the value \e x.
334 \fn void QValueList::clear()
335 Removes all items from the list.
341 \fn Iterator QValueList::find( const T& x )
342 Finds the first occurrence of \e x in the list.
344 Returns end() if no item did match.
348 \fn ConstIterator QValueList::find( const T& x ) const
349 Finds the first occurrence of \e x in the list.
351 Returns end() if no item did match.
355 \fn Iterator QValueList::find( Iterator it, const T& x )
356 Finds the first occurrence of \e x in the list starting at
357 the position given by \e it.
359 Returns end() if no item did match.
363 \fn ConstIterator QValueList::find( ConstIterator it, const T& x ) const
364 Finds the first occurrence of \e x in the list starting at
365 the position given by \e it.
367 Returns end() if no item did match.
371 \fn uint QValueList::contains( const T& x ) const
372 Counts and returns the number of occurrences of the value \e x in the list.
376 \fn int QValueList::findIndex( const T& x ) const
377 Returns the first index of the value \e x in the list or -1 if no such value
378 can be found in the list.
382 \fn Iterator QValueList::at( uint i )
383 Returns an iterator pointing to the item at position \e i in the list, or
384 end() if the index is out of range.
388 \fn ConstIterator QValueList::at( uint i ) const
389 Returns an iterator pointing to the item at position \e i in the list, or
390 end() if the index is out of range.
394 \fn T& QValueList::first()
395 Returns a reference to the first item in the list or the item
397 if no such items exists. Please note that you may not change
398 the value the end() Iterator is pointing to.
404 \fn const T& QValueList::first() const
405 Returns a reference to the first item in the list or the item
406 referenced by end() if
407 no such items exists.
413 \fn Iterator QValueList::fromLast()
414 Returns an iterator pointing to the last element in the list or
415 end() if no such item exists.
421 \fn ConstIterator QValueList::fromLast() const
422 Returns an iterator pointing to the last element in the list or
423 end() if no such item exists.
429 \fn T& QValueList::last()
430 Returns a reference to the last item in the list or the item
431 referenced by end() if no
432 such item exists. Please note that you may not change
433 the value the end() Iterator is pointing to.
435 \sa end(), first(), fromLast()
439 \fn const T& QValueList::last() const
440 Returns a reference to the last item in the list or the item
441 referenced by end() if no such item exists.
443 \sa end(), first(), fromLast()
447 \fn Iterator QValueList::begin()
448 Returns an iterator pointing to the first element in the list. This
449 iterator equals end() if the list is empty;
454 \fn ConstIterator QValueList::begin() const
455 Returns an iterator pointing to the first element in the list. This
456 iterator equals end() if the list is empty;
461 \fn Iterator QValueList::end()
462 Returns an iterator pointing behind the last element in the list. This
463 iterator equals begin() if the list is empty.
469 \fn ConstIterator QValueList::end() const
470 Returns an iterator pointing behind the last element in the list. This
471 iterator equals begin() if the list is empty.
477 \fn void QValueList::detach()
478 If the list does not share its data with another QValueList instance, then nothing
479 happens, otherwise the function creates a new copy of this data and detaches
480 from the shared one. This function is called whenever the list is modified.
481 The implicit sharing mechanism is implemented this way.
485 \fn QDataStream& operator>>( QDataStream& s, QValueList<T>& l )
487 Reads a list from the stream. The type \e T stored in the list must implement
488 the streaming operator, too.
492 \fn QDataStream& operator<<( QDataStream& s, const QValueList<T>& l )
494 Writes a list to the stream. The type \e T stored in the list must implement
495 the streaming operator, too.
498 /*****************************************************************************
499 QValueListIterator documentation
500 *****************************************************************************/
503 \class QValueListIterator qvaluelist.h
504 \brief The QValueListIterator class provides an iterator for QValueList.
509 You can not create an iterator by yourself. Instead you have to
510 ask a list to give you one. An iterator has only the size of a pointer.
511 On 32 bit machines that means 4 bytes otherwise 8 bytes. That makes them
512 very fast. In fact they resemble the semantics of pointers as good as possible
513 and they are almost as fast as usual pointers.
517 #include <qvaluelist.h>
525 Employee( const QString& name, int salary )
529 QString name() const { return n; }
530 int salary() const { return s; }
531 void setSalary( int salary ) { s = salary; }
539 typedef QValueList<Employee> EmployeeList;
540 EmployeeList list; // list of Employee
542 list.append( Employee("Bill", 50000) );
543 list.append( Employee("Steve",80000) );
544 list.append( Employee("Ron", 60000) );
546 Employee joe( "Joe", 50000 );
548 joe.setSalary( 4000 );
550 EmployeeList::Iterator it;
551 for( it = list.begin(); it != list.end(); ++it )
552 printf( "%s earns %d\n", (*it).name().latin1(), (*it).salary() );
564 In contrast to QList there are no built in functions in QValueList to
565 traverse the list. The only way to do this is to use iterators.
566 QValueList is highly optimized for performance and memory usage.
567 On the other hand that means that you have to be a bit more careful
568 by what you are doing. QValueList does not know about all its iterators
569 and the iterators don't even know to which list they belong. That makes
570 things fast and slim but a bit dangerous because it is up to you to make
571 sure that iterators you are using are still valid. QListIterator will be able
572 to give warnings while QValueListIterator may end up in an undefined state.
574 For every Iterator there is a ConstIterator. When accessing a QValueList
575 in a const environment or if the reference or pointer to the list is itself
576 const, then you have to use the ConstIterator. Its semantics are the same,
577 but it returns only const references to the item it points to.
579 \sa QValueList, QValueListConstIterator
583 \fn QValueListIterator::QValueListIterator()
584 Creates un uninitialized iterator.
588 \fn QValueListIterator::QValueListIterator( NodePtr p )
593 \fn QValueListIterator::QValueListIterator( const QValueListIterator<T>& it )
594 Constructs a copy of the iterator \e it.
598 \fn QValueListIterator::~QValueListIterator()
599 Destroys the iterator.
602 /* Unfortunately not with MSVC
603 \fn T *QValueListIterator::operator->()
604 Pointer operator. Returns a pointer to the current iterator item.
605 The great advantage of this operator is that you can treat the
606 iterator like a pointer.
610 QValueList<int>::Iterator it = list.begin();
611 for( ; it != end(); ++it )
617 \fn T& QValueListIterator::operator*()
618 Asterix operator. Returns a reference to the current iterator item.
622 \fn const T& QValueListIterator::operator*() const
623 Asterix operator. Returns a reference to the current iterator item.
627 \fn QValueListIterator<T>& QValueListIterator::operator++()
628 Prefix ++ makes the succeeding item current and returns
629 an iterator pointing to the new current item.
630 The iterator can not check whether it reached the end of the list. Incrementing
631 the iterator as returned by end() causes undefined results.
635 \fn QValueListIterator<T> QValueListIterator::operator++(int)
636 Postfix ++ makes the succeeding item current and returns
637 an iterator pointing to the new current item.
638 The iterator can not check whether it reached the end of the list. Incrementing
639 the iterator as returned by end() causes undefined results.
643 \fn QValueListIterator<T>& QValueListIterator::operator--()
644 Prefix -- makes the previous item current and returns
645 an iterator pointing to the new current item.
646 The iterator can not check whether it reached the beginning of the list. Decrementing
647 the iterator as returned by begin() causes undefined results.
651 \fn QValueListIterator<T> QValueListIterator::operator--(int)
652 Postfix -- makes the previous item current and returns
653 an iterator pointing to the new current item.
654 The iterator can not check whether it reached the beginning of the list. Decrementing
655 the iterator as returned by begin() causes undefined results.
659 \fn bool QValueListIterator::operator==( const QValueListIterator<T>& it ) const
660 Compares both iterators and returns TRUE if they point to the same item.
664 \fn bool QValueListIterator::operator!=( const QValueListIterator<T>& it ) const
665 Compares both iterators and returns TRUE if they point to different items.
668 /*****************************************************************************
669 QValueListConstIterator documentation
670 *****************************************************************************/
673 \class QValueListConstIterator qvaluelist.h
674 \brief The QValueListConstIterator class provides an iterator for QValueList.
679 In contrast to QValueListIterator this class is used to iterate over a const
680 list. It does not allow to modify the values of the list since this would
681 break the const semantics.
683 For more information on QValueList iterators see QValueListIterator.
685 \sa QValueListIterator, QValueList
689 \fn QValueListConstIterator::QValueListConstIterator()
690 Creates un uninitialized iterator.
694 \fn QValueListConstIterator::QValueListConstIterator( NodePtr p )
699 \fn QValueListConstIterator::QValueListConstIterator( const QValueListConstIterator<T>& it )
700 Constructs a copy of the iterator \e it.
704 \fn QValueListConstIterator::QValueListConstIterator( const QValueListIterator<T>& it )
705 Constructs a copy of the iterator \e it.
709 \fn QValueListConstIterator::~QValueListConstIterator()
710 Destroys the iterator.
713 /* Unfortunately not with MSVC
714 \fn const T *QValueListConstIterator::operator->()
715 Pointer operator. Returns a pointer to the current iterator item.
716 The great advantage of this operator is that you can treat the
717 iterator like a pointer.
721 QValueList<int>::Iterator it = list.begin();
722 for( ; it != end(); ++it )
728 \fn const T& QValueListConstIterator::operator*() const
729 Asterix operator. Returns a reference to the current iterator item.
733 \fn QValueListConstIterator<T>& QValueListConstIterator::operator++()
734 Prefix ++ makes the succeeding item current and returns
735 an iterator pointing to the new current item.
736 The iterator can not check whether it reached the end of the list. Incrementing
737 the iterator as returned by end() causes undefined results.
741 \fn QValueListConstIterator<T> QValueListConstIterator::operator++(int)
742 Postfix ++ makes the succeeding item current and returns
743 an iterator pointing to the new current item.
744 The iterator can not check whether it reached the end of the list. Incrementing
745 the iterator as returned by end() causes undefined results.
749 \fn QValueListConstIterator<T>& QValueListConstIterator::operator--()
750 Prefix -- makes the previous item current and returns
751 an iterator pointing to the new current item.
752 The iterator can not check whether it reached the beginning of the list. Decrementing
753 the iterator as returned by begin() causes undefined results.
757 \fn QValueListConstIterator<T> QValueListConstIterator::operator--(int)
758 Postfix -- makes the previous item current and returns
759 an iterator pointing to the new current item.
760 The iterator can not check whether it reached the beginning of the list. Decrementing
761 the iterator as returned by begin() causes undefined results.
765 \fn bool QValueListConstIterator::operator==( const QValueListConstIterator<T>& it ) const
766 Compares both iterators and returns TRUE if they point to the same item.
770 \fn bool QValueListConstIterator::operator!=( const QValueListConstIterator<T>& it ) const
771 Compares both iterators and returns TRUE if they point to different items.