Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

qmap-h.html@ 190

Last change on this file since 190 was 190, checked in by rudi, 14 years ago
reference documentation added
File size: 24.7 KB

Line
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"><!--
8	fn { margin-left: 1cm; text-indent: -1cm; }
9	a:link { color: #004faf; text-decoration: none }
10	a:visited { color: #672967; text-decoration: none }
11	body { 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 Classes</font></a>
23	\| <a href="mainclasses.html">
24	<font color="#004faf">Main 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 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 <iterator>
87	#include <map>
88	#endif
89
90	//#define QT_CHECK_MAP_RANGE
91
92	struct 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->left )
105	x = x->left;
106	return x;
107	}
108
109	QMapNodeBase* maximum() {
110	QMapNodeBase* x = this;
111	while ( x->right )
112	x = x->right;
113	return x;
114	}
115	};
116
117
118	template <class K, class T>
119	struct QMapNode : public QMapNodeBase
120	{
121	QMapNode( const K& _key, const T& _data ) { data = _data; key = _key; }
122	QMapNode( const K& _key ) { key = _key; }
123	QMapNode( const QMapNode<K,T>& _n ) { key = _n.key; data = _n.data; }
124	QMapNode() { }
125	T data;
126	K key;
127	};
128
129
130	template<class K, class T>
131	class QMapIterator
132	{
133	public:
134	/**
135	* Typedefs
136	*/
137	typedef QMapNode< K, T >* 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& reference;
149
150	/**
151	* Variables
152	*/
153	QMapNode<K,T>* node;
154
155	/**
156	* Functions
157	*/
158	QMapIterator() : node( 0 ) {}
159	QMapIterator( QMapNode<K,T>* p ) : node( p ) {}
160	QMapIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
161
162	bool operator==( const QMapIterator<K,T>& it ) const { return node == it.node; }
163	bool operator!=( const QMapIterator<K,T>& it ) const { return node != it.node; }
164	T& operator*() { return node->data; }
165	const T& operator*() const { return node->data; }
166	// UDT for T = x*
167	// T* operator->() const { return &node->data; }
168
169	const K& key() const { return node->key; }
170	T& data() { return node->data; }
171	const T& data() const { return node->data; }
172
173	private:
174	int inc();
175	int dec();
176
177	public:
178	QMapIterator<K,T>& operator++() {
179	inc();
180	return *this;
181	}
182
183	QMapIterator<K,T> operator++(int) {
184	QMapIterator<K,T> tmp = *this;
185	inc();
186	return tmp;
187	}
188
189	QMapIterator<K,T>& operator--() {
190	dec();
191	return *this;
192	}
193
194	QMapIterator<K,T> operator--(int) {
195	QMapIterator<K,T> tmp = *this;
196	dec();
197	return tmp;
198	}
199	};
200
201	template <class K, class T>
202	Q_INLINE_TEMPLATES int QMapIterator<K,T>::inc()
203	{
204	QMapNodeBase* tmp = node;
205	if ( tmp->right ) {
206	tmp = tmp->right;
207	while ( tmp->left )
208	tmp = tmp->left;
209	} else {
210	QMapNodeBase* y = tmp->parent;
211	while (tmp == y->right) {
212	tmp = y;
213	y = y->parent;
214	}
215	if (tmp->right != y)
216	tmp = y;
217	}
218	node = (NodePtr)tmp;
219	return 0;
220	}
221
222	template <class K, class T>
223	Q_INLINE_TEMPLATES int QMapIterator<K,T>::dec()
224	{
225	QMapNodeBase* tmp = node;
226	if (tmp->color == QMapNodeBase::Red &&
227	tmp->parent->parent == tmp ) {
228	tmp = tmp->right;
229	} else if (tmp->left != 0) {
230	QMapNodeBase* y = tmp->left;
231	while ( y->right )
232	y = y->right;
233	tmp = y;
234	} else {
235	QMapNodeBase* y = tmp->parent;
236	while (tmp == y->left) {
237	tmp = y;
238	y = y->parent;
239	}
240	tmp = y;
241	}
242	node = (NodePtr)tmp;
243	return 0;
244	}
245
246	template<class K, class T>
247	class QMapConstIterator
248	{
249	public:
250	/**
251	* Typedefs
252	*/
253	typedef QMapNode< K, T >* 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& reference;
265
266
267	/**
268	* Variables
269	*/
270	QMapNode<K,T>* node;
271
272	/**
273	* Functions
274	*/
275	QMapConstIterator() : node( 0 ) {}
276	QMapConstIterator( QMapNode<K,T>* p ) : node( p ) {}
277	QMapConstIterator( const QMapConstIterator<K,T>& it ) : node( it.node ) {}
278	QMapConstIterator( const QMapIterator<K,T>& it ) : node( it.node ) {}
279
280	bool operator==( const QMapConstIterator<K,T>& it ) const { return node == it.node; }
281	bool operator!=( const QMapConstIterator<K,T>& it ) const { return node != it.node; }
282	const T& operator*() const { return node->data; }
283	// UDT for T = x*
284	// const T* operator->() const { return &node->data; }
285
286	const K& key() const { return node->key; }
287	const T& data() const { return node->data; }
288
289	private:
290	int inc();
291	int dec();
292
293	public:
294	QMapConstIterator<K,T>& operator++() {
295	inc();
296	return *this;
297	}
298
299	QMapConstIterator<K,T> operator++(int) {
300	QMapConstIterator<K,T> tmp = *this;
301	inc();
302	return tmp;
303	}
304
305	QMapConstIterator<K,T>& operator--() {
306	dec();
307	return *this;
308	}
309
310	QMapConstIterator<K,T> operator--(int) {
311	QMapConstIterator<K,T> tmp = *this;
312	dec();
313	return tmp;
314	}
315	};
316
317	template <class K, class T>
318	Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::inc()
319	{
320	QMapNodeBase* tmp = node;
321	if ( tmp->right ) {
322	tmp = tmp->right;
323	while ( tmp->left )
324	tmp = tmp->left;
325	} else {
326	QMapNodeBase* y = tmp->parent;
327	while (tmp == y->right) {
328	tmp = y;
329	y = y->parent;
330	}
331	if (tmp->right != y)
332	tmp = y;
333	}
334	node = (NodePtr)tmp;
335	return 0;
336	}
337
338	template <class K, class T>
339	Q_INLINE_TEMPLATES int QMapConstIterator<K,T>::dec()
340	{
341	QMapNodeBase* tmp = node;
342	if (tmp->color == QMapNodeBase::Red &&
343	tmp->parent->parent == tmp ) {
344	tmp = tmp->right;
345	} else if (tmp->left != 0) {
346	QMapNodeBase* y = tmp->left;
347	while ( y->right )
348	y = y->right;
349	tmp = y;
350	} else {
351	QMapNodeBase* y = tmp->parent;
352	while (tmp == y->left) {
353	tmp = y;
354	y = y->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.
363	class Q_EXPORT QMapPrivateBase : public QShared
364	{
365	public:
366	QMapPrivateBase() {
367	node_count = 0;
368	}
369	QMapPrivateBase( const QMapPrivateBase* _map) {
370	node_count = _map->node_count;
371	}
372
373	/**
374	* Implementations of basic tree algorithms
375	*/
376	void rotateLeft( QMapNodeBase* x, QMapNodeBase*& root);
377	void rotateRight( QMapNodeBase* x, QMapNodeBase*& root );
378	void rebalance( QMapNodeBase* x, QMapNodeBase*& root );
379	QMapNodeBase* removeAndRebalance( QMapNodeBase* z, QMapNodeBase*& root,
380	QMapNodeBase*& leftmost,
381	QMapNodeBase*& rightmost );
382
383	/**
384	* Variables
385	*/
386	int node_count;
387	};
388
389
390	template <class Key, class T>
391	class QMapPrivate : public QMapPrivateBase
392	{
393	public:
394	/**
395	* Typedefs
396	*/
397	typedef QMapIterator< Key, T > Iterator;
398	typedef QMapConstIterator< Key, T > ConstIterator;
399	typedef QMapNode< Key, T > Node;
400	typedef QMapNode< Key, T >* NodePtr;
401
402	/**
403	* Functions
404	*/
405	QMapPrivate();
406	QMapPrivate( const QMapPrivate< Key, T >* _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->left ) ); }
414	Iterator end() { return Iterator( header ); }
415	ConstIterator begin() const { return ConstIterator( (NodePtr)(header->left ) ); }
416	ConstIterator end() const { return ConstIterator( header ); }
417
418	ConstIterator find(const Key& k) const;
419
420	void remove( Iterator it ) {
421	NodePtr del = (NodePtr) removeAndRebalance( it.node, header->parent, header->left, header->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->parent;
430	if ( x->left )
431	inorder( x->left, level + 1 );
432	//cout << level << " Key=" << key(x) << " Value=" << ((NodePtr)x)->data << endl;
433	if ( x->right )
434	inorder( x->right, level + 1 );
435	}
436	#endif
437
438	#if 0
439	Iterator insertMulti(const Key& v){
440	QMapNodeBase* y = header;
441	QMapNodeBase* x = header->parent;
442	while (x != 0){
443	y = x;
444	x = ( v < key(x) ) ? x->left : x->right;
445	}
446	return insert(x, y, v);
447	}
448	#endif
449
450	Iterator insertSingle( const Key& k );
451	Iterator insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k );
452
453	protected:
454	/**
455	* Helpers
456	*/
457	const Key& key( QMapNodeBase* b ) const { return ((NodePtr)b)->key; }
458
459	/**
460	* Variables
461	*/
462	NodePtr header;
463	};
464
465
466	template <class Key, class T>
467	Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate() {
468	header = new Node;
469	header->color = QMapNodeBase::Red; // Mark the header
470	header->parent = 0;
471	header->left = header->right = header;
472	}
473	template <class Key, class T>
474	Q_INLINE_TEMPLATES QMapPrivate<Key,T>::QMapPrivate( const QMapPrivate< Key, T >* _map ) : QMapPrivateBase( _map ) {
475	header = new Node;
476	header->color = QMapNodeBase::Red; // Mark the header
477	if ( _map->header->parent == 0 ) {
478	header->parent = 0;
479	header->left = header->right = header;
480	} else {
481	header->parent = copy( (NodePtr)(_map->header->parent) );
482	header->parent->parent = header;
483	header->left = header->parent->minimum();
484	header->right = header->parent->maximum();
485	}
486	}
487
488	template <class Key, class T>
489	Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::NodePtr QMapPrivate<Key,T>::copy( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
490	{
491	if ( !p )
492	return 0;
493	NodePtr n = new Node( *p );
494	n->color = p->color;
495	if ( p->left ) {
496	n->left = copy( (NodePtr)(p->left) );
497	n->left->parent = n;
498	} else {
499	n->left = 0;
500	}
501	if ( p->right ) {
502	n->right = copy( (NodePtr)(p->right) );
503	n->right->parent = n;
504	} else {
505	n->right = 0;
506	}
507	return n;
508	}
509
510	template <class Key, class T>
511	Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear()
512	{
513	clear( (NodePtr)(header->parent) );
514	header->color = QMapNodeBase::Red;
515	header->parent = 0;
516	header->left = header->right = header;
517	node_count = 0;
518	}
519
520	template <class Key, class T>
521	Q_INLINE_TEMPLATES void QMapPrivate<Key,T>::clear( Q_TYPENAME QMapPrivate<Key,T>::NodePtr p )
522	{
523	while ( p != 0 ) {
524	clear( (NodePtr)p->right );
525	NodePtr y = (NodePtr)p->left;
526	delete p;
527	p = y;
528	}
529	}
530
531	template <class Key, class T>
532	Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::ConstIterator QMapPrivate<Key,T>::find(const Key& k) const
533	{
534	QMapNodeBase* y = header; // Last node
535	QMapNodeBase* x = header->parent; // Root node.
536
537	while ( x != 0 ) {
538	// If as k <= key(x) go left
539	if ( !( key(x) < k ) ) {
540	y = x;
541	x = x->left;
542	} else {
543	x = x->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 < key(y) )
550	return ConstIterator( header );
551	return ConstIterator( (NodePtr)y );
552	}
553
554	template <class Key, class T>
555	Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insertSingle( const Key& k )
556	{
557	// Search correct position in the tree
558	QMapNodeBase* y = header;
559	QMapNodeBase* x = header->parent;
560	bool result = TRUE;
561	while ( x != 0 ) {
562	result = ( k < key(x) );
563	y = x;
564	x = result ? x->left : x->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->key) < k )
579	return insert(x, y, k );
580	// We are going to replace a node
581	return j;
582	}
583
584
585	template <class Key, class T>
586	Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate<Key,T>::Iterator QMapPrivate<Key,T>::insert( QMapNodeBase* x, QMapNodeBase* y, const Key& k )
587	{
588	NodePtr z = new Node( k );
589	if (y == header \|\| x != 0 \|\| k < key(y) ) {
590	y->left = z; // also makes leftmost = z when y == header
591	if ( y == header ) {
592	header->parent = z;
593	header->right = z;
594	} else if ( y == header->left )
595	header->left = z; // maintain leftmost pointing to min node
596	} else {
597	y->right = z;
598	if ( y == header->right )
599	header->right = z; // maintain rightmost pointing to max node
600	}
601	z->parent = y;
602	z->left = 0;
603	z->right = 0;
604	rebalance( z, header->parent );
605	++node_count;
606	return Iterator(z);
607	}
608
609
610	#ifdef QT_CHECK_RANGE
611	# if !defined( QT_NO_DEBUG ) && 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
623	template <class T> class QDeepCopy;
624
625	template<class Key, class T>
626	class QMap
627	{
628	public:
629	/**
630	* Typedefs
631	*/
632	typedef Key key_type;
633	typedef T mapped_type;
634	typedef QPair<const key_type, mapped_type> value_type;
635	typedef value_type* pointer;
636	typedef const value_type* const_pointer;
637	typedef value_type& reference;
638	typedef const value_type& 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<Key,T> iterator;
646	typedef QMapConstIterator<Key,T> const_iterator;
647	typedef QPair<iterator,bool> insert_pair;
648
649	typedef QMapIterator< Key, T > Iterator;
650	typedef QMapConstIterator< Key, T > ConstIterator;
651	typedef T ValueType;
652	typedef QMapPrivate< Key, T > Priv;
653
654	/**
655	* API
656	*/
657	QMap()
658	{
659	sh = new QMapPrivate< Key, T >;
660	}
661	QMap( const QMap<Key,T>& m )
662	{
663	sh = m.sh; sh->ref();
664	}
665
666	#ifndef QT_NO_STL
667	QMap( const std::map<Key,T>& m )
668	{
669	sh = new QMapPrivate<Key,T>;
670	Q_TYPENAME std::map<Key,T>::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->deref() )
680	delete sh;
681	}
682	QMap<Key,T>& operator= ( const QMap<Key,T>& m );
683	#ifndef QT_NO_STL
684	QMap<Key,T>& operator= ( const std::map<Key,T>& m )
685	{
686	clear();
687	Q_TYPENAME std::map<Key,T>::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->begin(); }
697	iterator end() { detach(); return sh->end(); }
698	const_iterator begin() const { return ((const Priv*)sh)->begin(); }
699	const_iterator end() const { return ((const Priv*)sh)->end(); }
700	const_iterator constBegin() const { return begin(); }
701	const_iterator constEnd() const { return end(); }
702
703	iterator replace( const Key& k, const T& v )
704	{
705	remove( k );
706	return insert( k, v );
707	}
708
709	size_type size() const
710	{
711	return sh->node_count;
712	}
713	bool empty() const
714	{
715	return sh->node_count == 0;
716	}
717	QPair<iterator,bool> insert( const value_type& x );
718
719	void erase( iterator it )
720	{
721	detach();
722	sh->remove( it );
723	}
724	void erase( const key_type& k );
725	size_type count( const key_type& k ) const;
726	T& operator[] ( const Key& k );
727	void clear();
728
729	iterator find ( const Key& k )
730	{
731	detach();
732	return iterator( sh->find( k ).node );
733	}
734	const_iterator find ( const Key& k ) const { return sh->find( k ); }
735
736	const T& operator[] ( const Key& k ) const
737	{ QT_CHECK_INVALID_MAP_ELEMENT; return sh->find( k ).data(); }
738	bool contains ( const Key& k ) const
739	{ return find( k ) != end(); }
740	//{ return sh->find( k ) != ((const Priv*)sh)->end(); }
741
742	size_type count() const { return sh->node_count; }
743
744	QValueList<Key> keys() const {
745	QValueList<Key> r;
746	for (const_iterator i=begin(); i!=end(); ++i)
747	r.append(i.key());
748	return r;
749	}
750
751	QValueList<T> values() const {
752	QValueList<T> 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->node_count == 0; }
759
760	iterator insert( const Key& key, const T& value, bool overwrite = TRUE );
761	void remove( iterator it ) { detach(); sh->remove( it ); }
762	void remove( const Key& k );
763
764	#if defined(Q_FULL_TEMPLATE_INSTANTIATION)
765	bool operator==( const QMap<Key,T>& ) const { return FALSE; }
766	#ifndef QT_NO_STL
767	bool operator==( const std::map<Key,T>& ) const { return FALSE; }
768	#endif
769	#endif
770
771	protected:
772	/**
773	* Helpers
774	*/
775	void detach() { if ( sh->count > 1 ) detachInternal(); }
776
777	Priv* sh;
778	private:
779	void detachInternal();
780
781	friend class QDeepCopy< QMap<Key,T> >;
782	};
783
784	template<class Key, class T>
785	Q_INLINE_TEMPLATES QMap<Key,T>& QMap<Key,T>::operator= ( const QMap<Key,T>& m )
786	{
787	m.sh->ref();
788	if ( sh->deref() )
789	delete sh;
790	sh = m.sh;
791	return *this;
792	}
793
794	template<class Key, class T>
795	Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::insert_pair QMap<Key,T>::insert( const Q_TYPENAME QMap<Key,T>::value_type& x )
796	{
797	detach();
798	size_type n = size();
799	iterator it = sh->insertSingle( x.first );
800	bool inserted = FALSE;
801	if ( n < size() ) {
802	inserted = TRUE;
803	it.data() = x.second;
804	}
805	return QPair<iterator,bool>( it, inserted );
806	}
807
808	template<class Key, class T>
809	Q_INLINE_TEMPLATES void QMap<Key,T>::erase( const Key& k )
810	{
811	detach();
812	iterator it( sh->find( k ).node );
813	if ( it != end() )
814	sh->remove( it );
815	}
816
817	template<class Key, class T>
818	Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::size_type QMap<Key,T>::count( const Key& k ) const
819	{
820	const_iterator it( sh->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
832	template<class Key, class T>
833	Q_INLINE_TEMPLATES T& QMap<Key,T>::operator[] ( const Key& k )
834	{
835	detach();
836	QMapNode<Key,T>* p = sh->find( k ).node;
837	if ( p != sh->end().node )
838	return p->data;
839	return insert( k, T() ).data();
840	}
841
842	template<class Key, class T>
843	Q_INLINE_TEMPLATES void QMap<Key,T>::clear()
844	{
845	if ( sh->count == 1 )
846	sh->clear();
847	else {
848	sh->deref();
849	sh = new QMapPrivate<Key,T>;
850	}
851	}
852
853	template<class Key, class T>
854	Q_INLINE_TEMPLATES Q_TYPENAME QMap<Key,T>::iterator QMap<Key,T>::insert( const Key& key, const T& value, bool overwrite )
855	{
856	detach();
857	size_type n = size();
858	iterator it = sh->insertSingle( key );
859	if ( overwrite \|\| n < size() )
860	it.data() = value;
861	return it;
862	}
863
864	template<class Key, class T>
865	Q_INLINE_TEMPLATES void QMap<Key,T>::remove( const Key& k )
866	{
867	detach();
868	iterator it( sh->find( k ).node );
869	if ( it != end() )
870	sh->remove( it );
871	}
872
873	template<class Key, class T>
874	Q_INLINE_TEMPLATES void QMap<Key,T>::detachInternal()
875	{
876	sh->deref(); sh = new QMapPrivate<Key,T>( sh );
877	}
878
879
880	#ifndef QT_NO_DATASTREAM
881	template<class Key, class T>
882	Q_INLINE_TEMPLATES QDataStream& operator>>( QDataStream& s, QMap<Key,T>& m ) {
883	m.clear();
884	Q_UINT32 c;
885	s >> c;
886	for( Q_UINT32 i = 0; i < c; ++i ) {
887	Key k; T t;
888	s >> k >> t;
889	m.insert( k, t );
890	if ( s.atEnd() )
891	break;
892	}
893	return s;
894	}
895
896
897	template<class Key, class T>
898	Q_INLINE_TEMPLATES QDataStream& operator<<( QDataStream& s, const QMap<Key,T>& m ) {
899	s << (Q_UINT32)m.size();
900	QMapConstIterator<Key,T> it = m.begin();
901	for( ; it != m.end(); ++it )
902	s << it.key() << 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 © 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.

Context Navigation

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

Download in other formats: