1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Qt Toolkit - Collection Classes</title><style type="text/css"><!--
h3.fn,span.fn { margin-left: 1cm; text-indent: -1cm; }
a:link { color: #004faf; text-decoration: none }
a:visited { color: #672967; text-decoration: none }body { background: white; color: black; }
--></style></head><body bgcolor="#ffffff">
<p>
<table width="100%">
<tr><td><a href="index.html">
<img width="100" height="100" src="qtlogo.png"
alt="Home" border="0"><img width="100"
height="100" src="face.png" alt="Home" border="0">
</a><td valign=top><div align=right><img src="dochead.png" width="472" height="27"><br>
<a href="classes.html"><b>Classes</b></a>
-<a href="annotated.html">Annotated</a>
- <a href="hierarchy.html">Tree</a>
-<a href="functions.html">Functions</a>
-<a href="index.html">Home</a>
-<a href="topicals.html"><b>Structure</b></a>
</div>
</table>
<h1 align=center> Collection Classes</h1><br clear="all">
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.
<p>
Qt has many reference based collection classes and some value based
collections.
<p>
The reference based collections are:
<ul>
<li> <a href="qcache.html">QCache</a> QCache and <a href="qintcache.html">QIntCache</a>
LRU (least recently used) cache structures.
<li> <a href="qdict.html">QDict</a>, <a href="qintdict.html">QIntDict</a> and <a href="qptrdict.html">QPtrDict</a> dictionary structures.
<li> <a href="qlist.html">QList</a> a double linked list structure.
<li> <a href="qqueue.html">QQueue</a> a FIFO (first in, first out) queue structure.
<li> <a href="qstack.html">QStack</a> a LIFO (last in, first out) stack structure.
<li> <a href="qvector.html">QVector</a> a vector structure.
</ul>
<p>
The value based collections are:
<ul>
<li> <a href="qvaluelist.html">QValueList</a> a value based list
<li> <a href="qvaluestack.html">QValueStack</a> a value based stack structure
<li> <a href="qmap.html">QMap</a> a value based dictionary structure
</ul>
<p>
The reference based collection classes work with pointers to items,
while the value based classes store copies of their items. An
exception is <a href="qarray.html">QArray</a>. It is neither reference nor value based, but
memory based. For maximum efficiency with the simple data types usually
used in arrays, it uses bitwise operations to copy and compare array
elements.
<p>
Some of these classes have corresponding iterators. An iterator
is a class for traversing the items in a collection:
<ul>
<li> <a href="qcacheiterator.html">QCacheIterator</a> and
<a href="qintcacheiterator.html">QIntCacheIterator</a>
<li> <a href="qdictiterator.html">QDictIterator</a>,
<a href="qintdictiterator.html">QIntDictIterator</a>, and
<a href="qptrdictiterator.html">QPtrDictIterator</a>
<li> <a href="qlistiterator.html">QListIterator</a>
<li> <a href="qvaluelistiterator.html">QValueListIterator</a>, and
<a href="qvaluelistconstiterator.html">QValueListConstIterator</a>
<li> <a href="qmapiterator.html">QMapIterator</a>, and
<a href="qmapconstiterator.html">QMapConstIterator</a>
</ul>
<p>
The value based collections plus algorithms operating on them are
grouped together in <a href="qtl.html">the Qt Template
Library</a>. See the respective documentation for details. The rest of
this page talks about the reference based containers only.
<p>
<h2>Architecture of the reference based containers</h2>
<p>
There are three internal base classes for the reference based
containers; <a href="qgcache.html">QGCache</a>, <a href="qgdict.html">QGDict</a> and <a href="qglist.html">QGList</a> that operate on <code>void*</code> pointers. A thin template layer implements the actual
collections by casting item pointers to and from <code>void*.</code>
<p>
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.
<p>
<h2>A QList Example</h2>
<p>
This example shows how to store Employee items in a list and prints
them out in the reverse order:
<p>
<pre> #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:
<a href="qstring.html">QString</a> n;
int s;
};
void main()
{
<a href="qlist.html">QList</a><Employee> list; // list of pointers to Employee
list.<a href="qcollection.html#a8ef9f">setAutoDelete</a>( TRUE ); // delete items when they are removed
list.<a href="qlist.html#c5746a">append</a>( new Employee("Bill", 50000) );
list.<a href="qlist.html#c5746a">append</a>( new Employee("Steve",80000) );
list.<a href="qlist.html#c5746a">append</a>( new Employee("Ron", 60000) );
<a href="qlistiterator.html">QListIterator</a><Employee> it(list); // iterator for employee list
for ( it.<a href="qlistiterator.html#70faa8">toLast</a>(); it.<a href="qlistiterator.html#e58f06">current</a>(); --it) ) {
Employee *emp = it.<a href="qlistiterator.html#e58f06">current</a>();
printf( "%s earns %d\n", emp->name(), emp->salary() );
}
}
</pre>
<p>
Program output:
<pre> Ron earns 60000
Steve earns 80000
Bill earns 50000
</pre>
<p>
<h2>Managing Collection Items</h2>
<p>
All reference based collections inherit the <a href="qcollection.html">QCollection</a> base class.
This class knows only the number of items in the collection and the
delete strategy.
<p>
Items in a collection are by default not deleted when they are removed
from the collection. The <a href="qcollection.html#a8ef9f">QCollection::setAutoDelete()</a> 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.
<p>
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 <a href="qcollection.html#55065e">QCollection::newItem()</a> for the item
to be inserted. Inherit a collection and reimplement it if you want
to have deep copies in your collection.
<p>
When removing an item from a list, the virtual function <a href="qcollection.html#8d78e7">QCollection::deleteItem()</a> is called.
The default implementation in all collection classes deletes the item
if auto-deletion is enabled.
<p>
<h2>Usage</h2>
<p>
A reference based collection class, such as QList<type>, defines a
collection of <em>pointers</em> to <em>type</em> objects. The pointer (*) is
implicit.
<p>
We discuss <a href="qlist.html">QList</a> here, but the same techniques apply for all
reference based collection classes and all collection class iterators.
<p>
Template instantiation:
<pre> <a href="qlist.html">QList</a><Employee> list; // wherever the list is used
</pre>
<p>
The item's class or type, Employee in our example, must be defined prior
to the list definition.
<p>
<pre> // Does not work: Employee is not defined
class Employee;
<a href="qlist.html">QList</a><Employee> list;
// This works: Employee is defined before it is used
class Employee {
...
};
<a href="qlist.html">QList</a><Employee> list;
</pre>
<p>
<h2>Iterators</h2>
<p>
Although <a href="qlist.html">QList</a> has member functions to traverse the list, it can
often be better to make use of an iterator. <a href="qlistiterator.html">QListIterator</a> is very
safe and can traverse lists that are being modified at the same time.
Multiple iterators can work independently on the same collection.
<p>
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.
<p>
The <a href="qdict.html">QDict</a> and <a href="qcache.html">QCache</a> collections have no traversal functions. To
traverse these collections, you must use <a href="qdictiterator.html">QDictIterator</a> or <a href="qcacheiterator.html">QCacheIterator</a>.
<p>
<h2>Predefined Collections</h2>
<p>
Qt has the following predefined collection classes:
<ul>
<li> String lists; <a href="qstrlist.html">QStrList</a>, <a href="qstrilist.html">QStrIList</a> (<a href="qstrlist-h.html">qstrlist.h</a> ) and
<a href="qstringlist.html">QStringList</a> (<a href="qstringlist-h.html">qstringlist.h</a> )
<li> String vectors; QStrVec and QStrIVec (qstrvec.h )
</ul>
<p>
In almost all cases you would choose QStringList, which is a value
list of implicitly shared QString unicode strings. QStrList and
QStrIList only store char* pointers.
<p>
<h2>Comparison with the STL</h2>
<p>
We often get questions about why Qt does not use the STL, and why Qt's
container templates are provided at all. Here are the major factors
why we use and provide these templates: <ul>
<li>Qt's reference based 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.
<li>Qt's reference based containers are often not as fast as the
STL's, for several reasons such as Qt's safe iterators.
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.)
<li>Qt's containers are much more portable than the STL. 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. Even today, the STL is
not portable across all platforms supported by Qt.
<li> Though primarily written for use internally in Qt, the containers
are well documented and so we saw no reason to hide them.
</ul>
<p>
Value based containers in the style of the STL do have one major
advantage, though: They are extremely efficient when being used with
value objects that implement a fast copy constructor. This is the case
with all implicit shared Qt classes such as QString or any of the C++
standard data types like int, bool or double. Since we needed that
functionality for Qt itself, we added a few <a href="qtl.html">value
based containers</a> in Qt-2.0. As with the other containers, the new
ones have a well documented interface and a naming scheme that matches
the usual Qt conventions - another advantage over the STL classes.
<p>
There are other differences, but the ones above are the important
reasons behind our decision to write, use and provide these classes.
<p>Classes:<ul plain>
<li><a href="qasciicache.html">QAsciiCache</a>
(Template class that provides a cache based on <code>char*</code> keys)
<li><a href="qasciicacheiterator.html">QAsciiCacheIterator</a>
(Iterator for <a href="qasciicache.html">QAsciiCache</a> collections)
<li><a href="qasciidict.html">QAsciiDict</a>
(Template class that provides a dictionary based on <code>char*</code> keys)
<li><a href="qasciidictiterator.html">QAsciiDictIterator</a>
(Iterator for <a href="qasciidict.html">QAsciiDict</a> collections)
<li><a href="qcache.html">QCache</a>
(Template class that provides a cache based on <code><a href="qstring.html">QString</a></code> keys)
<li><a href="qcacheiterator.html">QCacheIterator</a>
(Iterator for <a href="qcache.html">QCache</a> collections)
<li><a href="qcollection.html">QCollection</a>
(The base class of all Qt collections)
<li><a href="qdict.html">QDict</a>
(Template class that provides a dictionary based on <code><a href="qstring.html">QString</a></code> keys)
<li><a href="qdictiterator.html">QDictIterator</a>
(Iterator for <a href="qdict.html">QDict</a> collections)
<li><a href="qintcache.html">QIntCache</a>
(Template class that provides a cache based on <code>long</code> keys)
<li><a href="qintcacheiterator.html">QIntCacheIterator</a>
(Iterator for <a href="qintcache.html">QIntCache</a> collections)
<li><a href="qintdict.html">QIntDict</a>
(Template class that provides a dictionary based on <code>long</code> keys)
<li><a href="qintdictiterator.html">QIntDictIterator</a>
(Iterator for <a href="qintdict.html">QIntDict</a> collections)
<li><a href="qlist.html">QList</a>
(Template class that provides doubly linked lists)
<li><a href="qlistiterator.html">QListIterator</a>
(Iterator for <a href="qlist.html">QList</a> collections)
<li><a href="qptrdict.html">QPtrDict</a>
(Template class that provides a dictionary based on <code>void*</code> keys)
<li><a href="qptrdictiterator.html">QPtrDictIterator</a>
(Iterator for <a href="qptrdict.html">QPtrDict</a> collections)
<li><a href="qqueue.html">QQueue</a>
(Template class that provides a queue)
<li><a href="qsortedlist.html">QSortedList</a>
(List sorted by operator< and operator==)
<li><a href="qstack.html">QStack</a>
(Template class that provides a stack)
<li><a href="qstrilist.html">QStrIList</a>
(Doubly linked list of <code>char*</code> with case insensitive compare)
<li><a href="qstrlist.html">QStrList</a>
(Doubly linked list of <code>char*.</code>)
</ul>
<p><address><hr><div align="center">
<table width="100%" cellspacing="0" border="0"><tr>
<td>Copyright 2001 Trolltech<td><a href="http://www.trolltech.com/trademarks.html">Trademarks</a>
<td align="right"><div align="right">Qt version 2.3.2</div>
</table></div></address></body></html>
|
