source: trunk/doc/html/qmap-h.html

Last change on this file was 190, checked in by rudi, 14 years ago

reference documentation added
File size: 24.7 KB
RevLine 
[190]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
2<!-- /home/espenr/tmp/qt-3.3.8-espenr-2499/qt-x11-free-3.3.8/include/qmap.h:1 -->
3<html>
4<head>
5<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
6<title>qmap.h Include File</title>
7<style type="text/css"><!--
8fn { margin-left: 1cm; text-indent: -1cm; }
9a:link { color: #004faf; text-decoration: none }
10a:visited { color: #672967; text-decoration: none }
11body { background: #ffffff; color: black; }
12--></style>
13</head>
14<body>
15
16<table border="0" cellpadding="0" cellspacing="0" width="100%">
17<tr bgcolor="#E5E5E5">
18<td valign=center>
19 <a href="index.html">
20<font color="#004faf">Home</font></a>
21 | <a href="classes.html">
22<font color="#004faf">All&nbsp;Classes</font></a>
23 | <a href="mainclasses.html">
24<font color="#004faf">Main&nbsp;Classes</font></a>
25 | <a href="annotated.html">
26<font color="#004faf">Annotated</font></a>
27 | <a href="groups.html">
28<font color="#004faf">Grouped&nbsp;Classes</font></a>
29 | <a href="functions.html">
30<font color="#004faf">Functions</font></a>
31</td>
32<td align="right" valign="center"><img src="logo32.png" align="right" width="64" height="32" border="0"></td></tr></table><h1 align=center>qmap.h</h1>
33
34<p>This is the verbatim text of the qmap.h include file. It is provided only for illustration; the copyright remains with Trolltech.
35<hr>
36<pre>
37/****************************************************************************
38** $Id: qmap-h.html 2051 2007-02-21 10:04:20Z chehrlic $
39**
40** Definition of QMap class
41**
42** Created : 990406
43**
44** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
45**
46** This file is part of the tools module of the Qt GUI Toolkit.
47**
48** This file may be distributed under the terms of the Q Public License
49** as defined by Trolltech ASA of Norway and appearing in the file
50** LICENSE.QPL included in the packaging of this file.
51**
52** This file may be distributed and/or modified under the terms of the
53** GNU General Public License version 2 as published by the Free Software
54** Foundation and appearing in the file LICENSE.GPL included in the
55** packaging of this file.
56**
57** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
58** licenses may use this file in accordance with the Qt Commercial License
59** Agreement provided with the Software.
60**
61** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
62** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
63**
64** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
65** information about Qt Commercial License Agreements.
66** See http://www.trolltech.com/qpl/ for QPL licensing information.
67** See http://www.trolltech.com/gpl/ for GPL licensing information.
68**
69** Contact info@trolltech.com if any conditions of this licensing are
70** not clear to you.
71**
72**********************************************************************/
73
74#ifndef QMAP_H
75#define QMAP_H
76
77#ifndef QT_H
78#include "qglobal.h"
79#include "qshared.h"
80#include "qdatastream.h"
81#include "qpair.h"
82#include "qvaluelist.h"
83#endif // QT_H
84
85#ifndef QT_NO_STL
86#include &lt;iterator&gt;
87#include &lt;map&gt;
88#endif
89
90//#define QT_CHECK_MAP_RANGE
91
92struct Q_EXPORT QMapNodeBase
93{
94 enum Color { Red, Black };
95
96 QMapNodeBase* left;
97 QMapNodeBase* right;
98 QMapNodeBase* parent;
99
100 Color color;
101
102 QMapNodeBase* minimum() {
103 QMapNodeBase* x = this;
104 while ( x-&gt;left )
105 x = x-&gt;left;
106 return x;
107 }
108
109 QMapNodeBase* maximum() {
110 QMapNodeBase* x = this;
111 while ( x-&gt;right )
112 x = x-&gt;right;
113 return x;
114 }
115};
116
117
118template &lt;class K, class T&gt;
119struct QMapNode : public QMapNodeBase
120{
121 QMapNode( const K&amp; _key, const T&amp; _data ) { data = _data; key = _key; }
122 QMapNode( const K&amp; _key ) { key = _key; }
123 QMapNode( const QMapNode&lt;K,T&gt;&amp; _n ) { key = _n.key; data = _n.data; }
124 QMapNode() { }
125 T data;
126 K key;
127};
128
129
130template&lt;class K, class T&gt;
131class QMapIterator
132{
133 public:
134 /**
135 * Typedefs
136 */
137 typedef QMapNode&lt; K, T &gt;* NodePtr;
138#ifndef QT_NO_STL
139 typedef std::bidirectional_iterator_tag iterator_category;
140#endif
141 typedef T value_type;
142#ifndef QT_NO_STL
143 typedef ptrdiff_t difference_type;
144#else
145 typedef int difference_type;
146#endif
147 typedef T* pointer;
148 typedef T&amp; reference;
149
150 /**
151 * Variables
152 */
153 QMapNode&lt;K,T&gt;* node;
154
155 /**
156 * Functions
157 */
158 QMapIterator() : node( 0 ) {}
159 QMapIterator( QMapNode&lt;K,T&gt;* p ) : node( p ) {}
160 QMapIterator( const QMapIterator&lt;K,T&gt;&amp; it ) : node( it.node ) {}
161
162 bool operator==( const QMapIterator&lt;K,T&gt;&amp; it ) const { return node == it.node; }
163 bool operator!=( const QMapIterator&lt;K,T&gt;&amp; it ) const { return node != it.node; }
164 T&amp; operator*() { return node-&gt;data; }
165 const T&amp; operator*() const { return node-&gt;data; }
166 // UDT for T = x*
167 // T* operator-&gt;() const { return &amp;node-&gt;data; }
168
169 const K&amp; key() const { return node-&gt;key; }
170 T&amp; data() { return node-&gt;data; }
171 const T&amp; data() const { return node-&gt;data; }
172
173private:
174 int inc();
175 int dec();
176
177public:
178 QMapIterator&lt;K,T&gt;&amp; operator++() {
179 inc();
180 return *this;
181 }
182
183 QMapIterator&lt;K,T&gt; operator++(int) {
184 QMapIterator&lt;K,T&gt; tmp = *this;
185 inc();
186 return tmp;
187 }
188
189 QMapIterator&lt;K,T&gt;&amp; operator--() {
190 dec();
191 return *this;
192 }
193
194 QMapIterator&lt;K,T&gt; operator--(int) {
195 QMapIterator&lt;K,T&gt; tmp = *this;
196 dec();
197 return tmp;
198 }
199};
200
201template &lt;class K, class T&gt;
202Q_INLINE_TEMPLATES int QMapIterator&lt;K,T&gt;::inc()
203{
204 QMapNodeBase* tmp = node;
205 if ( tmp-&gt;right ) {
206 tmp = tmp-&gt;right;
207 while ( tmp-&gt;left )
208 tmp = tmp-&gt;left;
209 } else {
210 QMapNodeBase* y = tmp-&gt;parent;
211 while (tmp == y-&gt;right) {
212 tmp = y;
213 y = y-&gt;parent;
214 }
215 if (tmp-&gt;right != y)
216 tmp = y;
217 }
218 node = (NodePtr)tmp;
219 return 0;
220}
221
222template &lt;class K, class T&gt;
223Q_INLINE_TEMPLATES int QMapIterator&lt;K,T&gt;::dec()
224{
225 QMapNodeBase* tmp = node;
226 if (tmp-&gt;color == QMapNodeBase::Red &amp;&amp;
227 tmp-&gt;parent-&gt;parent == tmp ) {
228 tmp = tmp-&gt;right;
229 } else if (tmp-&gt;left != 0) {
230 QMapNodeBase* y = tmp-&gt;left;
231 while ( y-&gt;right )
232 y = y-&gt;right;
233 tmp = y;
234 } else {
235 QMapNodeBase* y = tmp-&gt;parent;
236 while (tmp == y-&gt;left) {
237 tmp = y;
238 y = y-&gt;parent;
239 }
240 tmp = y;
241 }
242 node = (NodePtr)tmp;
243 return 0;
244}
245
246template&lt;class K, class T&gt;
247class QMapConstIterator
248{
249 public:
250 /**
251 * Typedefs
252 */
253 typedef QMapNode&lt; K, T &gt;* NodePtr;
254#ifndef QT_NO_STL
255 typedef std::bidirectional_iterator_tag iterator_category;
256#endif
257 typedef T value_type;
258#ifndef QT_NO_STL
259 typedef ptrdiff_t difference_type;
260#else
261 typedef int difference_type;
262#endif
263 typedef const T* pointer;
264 typedef const T&amp; reference;
265
266
267 /**
268 * Variables
269 */
270 QMapNode&lt;K,T&gt;* node;
271
272 /**
273 * Functions
274 */
275 QMapConstIterator() : node( 0 ) {}
276 QMapConstIterator( QMapNode&lt;K,T&gt;* p ) : node( p ) {}
277 QMapConstIterator( const QMapConstIterator&lt;K,T&gt;&amp; it ) : node( it.node ) {}
278 QMapConstIterator( const QMapIterator&lt;K,T&gt;&amp; it ) : node( it.node ) {}
279
280 bool operator==( const QMapConstIterator&lt;K,T&gt;&amp; it ) const { return node == it.node; }
281 bool operator!=( const QMapConstIterator&lt;K,T&gt;&amp; it ) const { return node != it.node; }
282 const T&amp; operator*() const { return node-&gt;data; }
283 // UDT for T = x*
284 // const T* operator-&gt;() const { return &amp;node-&gt;data; }
285
286 const K&amp; key() const { return node-&gt;key; }
287 const T&amp; data() const { return node-&gt;data; }
288
289private:
290 int inc();
291 int dec();
292
293public:
294 QMapConstIterator&lt;K,T&gt;&amp; operator++() {
295 inc();
296 return *this;
297 }
298
299 QMapConstIterator&lt;K,T&gt; operator++(int) {
300 QMapConstIterator&lt;K,T&gt; tmp = *this;
301 inc();
302 return tmp;
303 }
304
305 QMapConstIterator&lt;K,T&gt;&amp; operator--() {
306 dec();
307 return *this;
308 }
309
310 QMapConstIterator&lt;K,T&gt; operator--(int) {
311 QMapConstIterator&lt;K,T&gt; tmp = *this;
312 dec();
313 return tmp;
314 }
315};
316
317template &lt;class K, class T&gt;
318Q_INLINE_TEMPLATES int QMapConstIterator&lt;K,T&gt;::inc()
319{
320 QMapNodeBase* tmp = node;
321 if ( tmp-&gt;right ) {
322 tmp = tmp-&gt;right;
323 while ( tmp-&gt;left )
324 tmp = tmp-&gt;left;
325 } else {
326 QMapNodeBase* y = tmp-&gt;parent;
327 while (tmp == y-&gt;right) {
328 tmp = y;
329 y = y-&gt;parent;
330 }
331 if (tmp-&gt;right != y)
332 tmp = y;
333 }
334 node = (NodePtr)tmp;
335 return 0;
336}
337
338template &lt;class K, class T&gt;
339Q_INLINE_TEMPLATES int QMapConstIterator&lt;K,T&gt;::dec()
340{
341 QMapNodeBase* tmp = node;
342 if (tmp-&gt;color == QMapNodeBase::Red &amp;&amp;
343 tmp-&gt;parent-&gt;parent == tmp ) {
344 tmp = tmp-&gt;right;
345 } else if (tmp-&gt;left != 0) {
346 QMapNodeBase* y = tmp-&gt;left;
347 while ( y-&gt;right )
348 y = y-&gt;right;
349 tmp = y;
350 } else {
351 QMapNodeBase* y = tmp-&gt;parent;
352 while (tmp == y-&gt;left) {
353 tmp = y;
354 y = y-&gt;parent;
355 }
356 tmp = y;
357 }
358 node = (NodePtr)tmp;
359 return 0;
360}
361
362// ### 4.0: rename to something without Private in it. Not really internal.
363class Q_EXPORT QMapPrivateBase : public QShared
364{
365public:
366 QMapPrivateBase() {
367 node_count = 0;
368 }
369 QMapPrivateBase( const QMapPrivateBase* _map) {
370 node_count = _map-&gt;node_count;
371 }
372
373 /**
374 * Implementations of basic tree algorithms
375 */
376 void rotateLeft( QMapNodeBase* x, QMapNodeBase*&amp; root);
377 void rotateRight( QMapNodeBase* x, QMapNodeBase*&amp; root );
378 void rebalance( QMapNodeBase* x, QMapNodeBase*&amp; root );
379 QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*&amp; root,
380 QMapNodeBase*&amp; leftmost,
381 QMapNodeBase*&amp; rightmost );
382
383 /**
384 * Variables
385 */
386 int node_count;
387};
388
389
390template &lt;class Key, class T&gt;
391class QMapPrivate : public QMapPrivateBase
392{
393public:
394 /**
395 * Typedefs
396 */
397 typedef QMapIterator&lt; Key, T &gt; Iterator;
398 typedef QMapConstIterator&lt; Key, T &gt; ConstIterator;
399 typedef QMapNode&lt; Key, T &gt; Node;
400 typedef QMapNode&lt; Key, T &gt;* NodePtr;
401
402 /**
403 * Functions
404 */
405 QMapPrivate();
406 QMapPrivate( const QMapPrivate&lt; Key, T &gt;* _map );
407 ~QMapPrivate() { clear(); delete header; }
408
409 NodePtr copy( NodePtr p );
410 void clear();
411 void clear( NodePtr p );
412
413 Iterator begin() { return Iterator( (NodePtr)(header-&gt;left ) ); }
414 Iterator end() { return Iterator( header ); }
415 ConstIterator begin() const { return ConstIterator( (NodePtr)(header-&gt;left ) ); }
416 ConstIterator end() const { return ConstIterator( header ); }
417
418 ConstIterator find(const Key&amp; k) const;
419
420 void remove( Iterator it ) {
421 NodePtr del = (NodePtr) removeAndRebalance( it.node, header-&gt;parent, header-&gt;left, header-&gt;right );
422 delete del;
423 --node_count;
424 }
425
426#ifdef QT_QMAP_DEBUG
427 void inorder( QMapNodeBase* x = 0, int level = 0 ){
428 if ( !x )
429 x = header-&gt;parent;
430 if ( x-&gt;left )
431 inorder( x-&gt;left, level + 1 );
432 //cout &lt;&lt; level &lt;&lt; " Key=" &lt;&lt; key(x) &lt;&lt; " Value=" &lt;&lt; ((NodePtr)x)-&gt;data &lt;&lt; endl;
433 if ( x-&gt;right )
434 inorder( x-&gt;right, level + 1 );
435 }
436#endif
437
438#if 0
439 Iterator insertMulti(const Key&amp; v){
440 QMapNodeBase* y = header;
441 QMapNodeBase* x = header-&gt;parent;
442 while (x != 0){
443 y = x;
444 x = ( v &lt; key(x) ) ? x-&gt;left : x-&gt;right;
445 }
446 return insert(x, y, v);
447 }
448#endif
449
450 Iterator insertSingle( const Key&amp; k );
451 Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key&amp; k );
452
453protected:
454 /**
455 * Helpers
456 */
457 const Key&amp; key( QMapNodeBase* b ) const { return ((NodePtr)b)-&gt;key; }
458
459 /**
460 * Variables
461 */
462 NodePtr header;
463};
464
465
466template &lt;class Key, class T&gt;
467Q_INLINE_TEMPLATES QMapPrivate&lt;Key,T&gt;::QMapPrivate() {
468 header = new Node;
469 header-&gt;color = QMapNodeBase::Red; // Mark the header
470 header-&gt;parent = 0;
471 header-&gt;left = header-&gt;right = header;
472}
473template &lt;class Key, class T&gt;
474Q_INLINE_TEMPLATES QMapPrivate&lt;Key,T&gt;::QMapPrivate( const QMapPrivate&lt; Key, T &gt;* _map ) : QMapPrivateBase( _map ) {
475 header = new Node;
476 header-&gt;color = QMapNodeBase::Red; // Mark the header
477 if ( _map-&gt;header-&gt;parent == 0 ) {
478 header-&gt;parent = 0;
479 header-&gt;left = header-&gt;right = header;
480 } else {
481 header-&gt;parent = copy( (NodePtr)(_map-&gt;header-&gt;parent) );
482 header-&gt;parent-&gt;parent = header;
483 header-&gt;left = header-&gt;parent-&gt;minimum();
484 header-&gt;right = header-&gt;parent-&gt;maximum();
485 }
486}
487
488template &lt;class Key, class T&gt;
489Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::NodePtr QMapPrivate&lt;Key,T&gt;::copy( Q_TYPENAME QMapPrivate&lt;Key,T&gt;::NodePtr p )
490{
491 if ( !p )
492 return 0;
493 NodePtr n = new Node( *p );
494 n-&gt;color = p-&gt;color;
495 if ( p-&gt;left ) {
496 n-&gt;left = copy( (NodePtr)(p-&gt;left) );
497 n-&gt;left-&gt;parent = n;
498 } else {
499 n-&gt;left = 0;
500 }
501 if ( p-&gt;right ) {
502 n-&gt;right = copy( (NodePtr)(p-&gt;right) );
503 n-&gt;right-&gt;parent = n;
504 } else {
505 n-&gt;right = 0;
506 }
507 return n;
508}
509
510template &lt;class Key, class T&gt;
511Q_INLINE_TEMPLATES void QMapPrivate&lt;Key,T&gt;::clear()
512{
513 clear( (NodePtr)(header-&gt;parent) );
514 header-&gt;color = QMapNodeBase::Red;
515 header-&gt;parent = 0;
516 header-&gt;left = header-&gt;right = header;
517 node_count = 0;
518}
519
520template &lt;class Key, class T&gt;
521Q_INLINE_TEMPLATES void QMapPrivate&lt;Key,T&gt;::clear( Q_TYPENAME QMapPrivate&lt;Key,T&gt;::NodePtr p )
522{
523 while ( p != 0 ) {
524 clear( (NodePtr)p-&gt;right );
525 NodePtr y = (NodePtr)p-&gt;left;
526 delete p;
527 p = y;
528 }
529}
530
531template &lt;class Key, class T&gt;
532Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::ConstIterator QMapPrivate&lt;Key,T&gt;::find(const Key&amp; k) const
533{
534 QMapNodeBase* y = header; // Last node
535 QMapNodeBase* x = header-&gt;parent; // Root node.
536
537 while ( x != 0 ) {
538 // If as k &lt;= key(x) go left
539 if ( !( key(x) &lt; k ) ) {
540 y = x;
541 x = x-&gt;left;
542 } else {
543 x = x-&gt;right;
544 }
545 }
546
547 // Was k bigger/smaller then the biggest/smallest
548 // element of the tree ? Return end()
549 if ( y == header || k &lt; key(y) )
550 return ConstIterator( header );
551 return ConstIterator( (NodePtr)y );
552}
553
554template &lt;class Key, class T&gt;
555Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::Iterator QMapPrivate&lt;Key,T&gt;::insertSingle( const Key&amp; k )
556{
557 // Search correct position in the tree
558 QMapNodeBase* y = header;
559 QMapNodeBase* x = header-&gt;parent;
560 bool result = TRUE;
561 while ( x != 0 ) {
562 result = ( k &lt; key(x) );
563 y = x;
564 x = result ? x-&gt;left : x-&gt;right;
565 }
566 // Get iterator on the last not empty one
567 Iterator j( (NodePtr)y );
568 if ( result ) {
569 // Smaller then the leftmost one ?
570 if ( j == begin() ) {
571 return insert(x, y, k );
572 } else {
573 // Perhaps daddy is the right one ?
574 --j;
575 }
576 }
577 // Really bigger ?
578 if ( (j.node-&gt;key) &lt; k )
579 return insert(x, y, k );
580 // We are going to replace a node
581 return j;
582}
583
584
585template &lt;class Key, class T&gt;
586Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::Iterator QMapPrivate&lt;Key,T&gt;::insert( QMapNodeBase* x, QMapNodeBase* y, const Key&amp; k )
587{
588 NodePtr z = new Node( k );
589 if (y == header || x != 0 || k &lt; key(y) ) {
590 y-&gt;left = z; // also makes leftmost = z when y == header
591 if ( y == header ) {
592 header-&gt;parent = z;
593 header-&gt;right = z;
594 } else if ( y == header-&gt;left )
595 header-&gt;left = z; // maintain leftmost pointing to min node
596 } else {
597 y-&gt;right = z;
598 if ( y == header-&gt;right )
599 header-&gt;right = z; // maintain rightmost pointing to max node
600 }
601 z-&gt;parent = y;
602 z-&gt;left = 0;
603 z-&gt;right = 0;
604 rebalance( z, header-&gt;parent );
605 ++node_count;
606 return Iterator(z);
607}
608
609
610#ifdef QT_CHECK_RANGE
611# if !defined( QT_NO_DEBUG ) &amp;&amp; defined( QT_CHECK_MAP_RANGE )
612# define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )
613# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );
614# else
615# define QT_CHECK_INVALID_MAP_ELEMENT
616# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
617# endif
618#else
619# define QT_CHECK_INVALID_MAP_ELEMENT
620# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL
621#endif
622
623template &lt;class T&gt; class QDeepCopy;
624
625template&lt;class Key, class T&gt;
626class QMap
627{
628public:
629 /**
630 * Typedefs
631 */
632 typedef Key key_type;
633 typedef T mapped_type;
634 typedef QPair&lt;const key_type, mapped_type&gt; value_type;
635 typedef value_type* pointer;
636 typedef const value_type* const_pointer;
637 typedef value_type&amp; reference;
638 typedef const value_type&amp; const_reference;
639#ifndef QT_NO_STL
640 typedef ptrdiff_t difference_type;
641#else
642 typedef int difference_type;
643#endif
644 typedef size_t size_type;
645 typedef QMapIterator&lt;Key,T&gt; iterator;
646 typedef QMapConstIterator&lt;Key,T&gt; const_iterator;
647 typedef QPair&lt;iterator,bool&gt; insert_pair;
648
649 typedef QMapIterator&lt; Key, T &gt; Iterator;
650 typedef QMapConstIterator&lt; Key, T &gt; ConstIterator;
651 typedef T ValueType;
652 typedef QMapPrivate&lt; Key, T &gt; Priv;
653
654 /**
655 * API
656 */
657 QMap()
658 {
659 sh = new QMapPrivate&lt; Key, T &gt;;
660 }
661 QMap( const QMap&lt;Key,T&gt;&amp; m )
662 {
663 sh = m.sh; sh-&gt;ref();
664 }
665
666#ifndef QT_NO_STL
667 QMap( const std::map&lt;Key,T&gt;&amp; m )
668 {
669 sh = new QMapPrivate&lt;Key,T&gt;;
670 Q_TYPENAME std::map&lt;Key,T&gt;::const_iterator it = m.begin();
671 for ( ; it != m.end(); ++it ) {
672 value_type p( (*it).first, (*it).second );
673 insert( p );
674 }
675 }
676#endif
677 ~QMap()
678 {
679 if ( sh-&gt;deref() )
680 delete sh;
681 }
682 QMap&lt;Key,T&gt;&amp; operator= ( const QMap&lt;Key,T&gt;&amp; m );
683#ifndef QT_NO_STL
684 QMap&lt;Key,T&gt;&amp; operator= ( const std::map&lt;Key,T&gt;&amp; m )
685 {
686 clear();
687 Q_TYPENAME std::map&lt;Key,T&gt;::const_iterator it = m.begin();
688 for ( ; it != m.end(); ++it ) {
689 value_type p( (*it).first, (*it).second );
690 insert( p );
691 }
692 return *this;
693 }
694#endif
695
696 iterator begin() { detach(); return sh-&gt;begin(); }
697 iterator end() { detach(); return sh-&gt;end(); }
698 const_iterator begin() const { return ((const Priv*)sh)-&gt;begin(); }
699 const_iterator end() const { return ((const Priv*)sh)-&gt;end(); }
700 const_iterator constBegin() const { return begin(); }
701 const_iterator constEnd() const { return end(); }
702
703 iterator replace( const Key&amp; k, const T&amp; v )
704 {
705 remove( k );
706 return insert( k, v );
707 }
708
709 size_type size() const
710 {
711 return sh-&gt;node_count;
712 }
713 bool empty() const
714 {
715 return sh-&gt;node_count == 0;
716 }
717 QPair&lt;iterator,bool&gt; insert( const value_type&amp; x );
718
719 void erase( iterator it )
720 {
721 detach();
722 sh-&gt;remove( it );
723 }
724 void erase( const key_type&amp; k );
725 size_type count( const key_type&amp; k ) const;
726 T&amp; operator[] ( const Key&amp; k );
727 void clear();
728
729 iterator find ( const Key&amp; k )
730 {
731 detach();
732 return iterator( sh-&gt;find( k ).node );
733 }
734 const_iterator find ( const Key&amp; k ) const { return sh-&gt;find( k ); }
735
736 const T&amp; operator[] ( const Key&amp; k ) const
737 { QT_CHECK_INVALID_MAP_ELEMENT; return sh-&gt;find( k ).data(); }
738 bool contains ( const Key&amp; k ) const
739 { return find( k ) != end(); }
740 //{ return sh-&gt;find( k ) != ((const Priv*)sh)-&gt;end(); }
741
742 size_type count() const { return sh-&gt;node_count; }
743
744 QValueList&lt;Key&gt; keys() const {
745 QValueList&lt;Key&gt; r;
746 for (const_iterator i=begin(); i!=end(); ++i)
747 r.append(i.key());
748 return r;
749 }
750
751 QValueList&lt;T&gt; values() const {
752 QValueList&lt;T&gt; r;
753 for (const_iterator i=begin(); i!=end(); ++i)
754 r.append(*i);
755 return r;
756 }
757
758 bool isEmpty() const { return sh-&gt;node_count == 0; }
759
760 iterator insert( const Key&amp; key, const T&amp; value, bool overwrite = TRUE );
761 void remove( iterator it ) { detach(); sh-&gt;remove( it ); }
762 void remove( const Key&amp; k );
763
764#if defined(Q_FULL_TEMPLATE_INSTANTIATION)
765 bool operator==( const QMap&lt;Key,T&gt;&amp; ) const { return FALSE; }
766#ifndef QT_NO_STL
767 bool operator==( const std::map&lt;Key,T&gt;&amp; ) const { return FALSE; }
768#endif
769#endif
770
771protected:
772 /**
773 * Helpers
774 */
775 void detach() { if ( sh-&gt;count &gt; 1 ) detachInternal(); }
776
777 Priv* sh;
778private:
779 void detachInternal();
780
781 friend class QDeepCopy&lt; QMap&lt;Key,T&gt; &gt;;
782};
783
784template&lt;class Key, class T&gt;
785Q_INLINE_TEMPLATES QMap&lt;Key,T&gt;&amp; QMap&lt;Key,T&gt;::operator= ( const QMap&lt;Key,T&gt;&amp; m )
786{
787 m.sh-&gt;ref();
788 if ( sh-&gt;deref() )
789 delete sh;
790 sh = m.sh;
791 return *this;
792}
793
794template&lt;class Key, class T&gt;
795Q_INLINE_TEMPLATES Q_TYPENAME QMap&lt;Key,T&gt;::insert_pair QMap&lt;Key,T&gt;::insert( const Q_TYPENAME QMap&lt;Key,T&gt;::value_type&amp; x )
796{
797 detach();
798 size_type n = size();
799 iterator it = sh-&gt;insertSingle( x.first );
800 bool inserted = FALSE;
801 if ( n &lt; size() ) {
802 inserted = TRUE;
803 it.data() = x.second;
804 }
805 return QPair&lt;iterator,bool&gt;( it, inserted );
806}
807
808template&lt;class Key, class T&gt;
809Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::erase( const Key&amp; k )
810{
811 detach();
812 iterator it( sh-&gt;find( k ).node );
813 if ( it != end() )
814 sh-&gt;remove( it );
815}
816
817template&lt;class Key, class T&gt;
818Q_INLINE_TEMPLATES Q_TYPENAME QMap&lt;Key,T&gt;::size_type QMap&lt;Key,T&gt;::count( const Key&amp; k ) const
819{
820 const_iterator it( sh-&gt;find( k ).node );
821 if ( it != end() ) {
822 size_type c = 0;
823 while ( it != end() ) {
824 ++it;
825 ++c;
826 }
827 return c;
828 }
829 return 0;
830}
831
832template&lt;class Key, class T&gt;
833Q_INLINE_TEMPLATES T&amp; QMap&lt;Key,T&gt;::operator[] ( const Key&amp; k )
834{
835 detach();
836 QMapNode&lt;Key,T&gt;* p = sh-&gt;find( k ).node;
837 if ( p != sh-&gt;end().node )
838 return p-&gt;data;
839 return insert( k, T() ).data();
840}
841
842template&lt;class Key, class T&gt;
843Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::clear()
844{
845 if ( sh-&gt;count == 1 )
846 sh-&gt;clear();
847 else {
848 sh-&gt;deref();
849 sh = new QMapPrivate&lt;Key,T&gt;;
850 }
851}
852
853template&lt;class Key, class T&gt;
854Q_INLINE_TEMPLATES Q_TYPENAME QMap&lt;Key,T&gt;::iterator QMap&lt;Key,T&gt;::insert( const Key&amp; key, const T&amp; value, bool overwrite )
855{
856 detach();
857 size_type n = size();
858 iterator it = sh-&gt;insertSingle( key );
859 if ( overwrite || n &lt; size() )
860 it.data() = value;
861 return it;
862}
863
864template&lt;class Key, class T&gt;
865Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::remove( const Key&amp; k )
866{
867 detach();
868 iterator it( sh-&gt;find( k ).node );
869 if ( it != end() )
870 sh-&gt;remove( it );
871}
872
873template&lt;class Key, class T&gt;
874Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::detachInternal()
875{
876 sh-&gt;deref(); sh = new QMapPrivate&lt;Key,T&gt;( sh );
877}
878
879
880#ifndef QT_NO_DATASTREAM
881template&lt;class Key, class T&gt;
882Q_INLINE_TEMPLATES QDataStream&amp; operator&gt;&gt;( QDataStream&amp; s, QMap&lt;Key,T&gt;&amp; m ) {
883 m.clear();
884 Q_UINT32 c;
885 s &gt;&gt; c;
886 for( Q_UINT32 i = 0; i &lt; c; ++i ) {
887 Key k; T t;
888 s &gt;&gt; k &gt;&gt; t;
889 m.insert( k, t );
890 if ( s.atEnd() )
891 break;
892 }
893 return s;
894}
895
896
897template&lt;class Key, class T&gt;
898Q_INLINE_TEMPLATES QDataStream&amp; operator&lt;&lt;( QDataStream&amp; s, const QMap&lt;Key,T&gt;&amp; m ) {
899 s &lt;&lt; (Q_UINT32)m.size();
900 QMapConstIterator&lt;Key,T&gt; it = m.begin();
901 for( ; it != m.end(); ++it )
902 s &lt;&lt; it.key() &lt;&lt; it.data();
903 return s;
904}
905#endif
906
907#define Q_DEFINED_QMAP
908#include "qwinexport.h"
909#endif // QMAP_H
910</pre>
911<!-- eof -->
912<p><address><hr><div align=center>
913<table width=100% cellspacing=0 border=0><tr>
914<td>Copyright &copy; 2007
915<a href="troll.html">Trolltech</a><td align=center><a href="trademarks.html">Trademarks</a>
916<td align=right><div align=right>Qt 3.3.8</div>
917</table></div></address></body>
918</html>
Note: See TracBrowser for help on using the repository browser.