qmap-h.html

来自「QT 下载资料仅供参考」· HTML 代码 · 共 918 行 · 第 1/2 页

HTML
918 行
字号
     * Variables     */    NodePtr header;};template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES QMapPrivate&lt;Key,T&gt;::QMapPrivate() {    header = new Node;    header-&gt;color = QMapNodeBase::Red; // Mark the header    header-&gt;parent = 0;    header-&gt;left = header-&gt;right = header;}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES QMapPrivate&lt;Key,T&gt;::QMapPrivate( const QMapPrivate&lt; Key, T &gt;* _map ) : QMapPrivateBase( _map ) {    header = new Node;    header-&gt;color = QMapNodeBase::Red; // Mark the header    if ( _map-&gt;header-&gt;parent == 0 ) {	header-&gt;parent = 0;	header-&gt;left = header-&gt;right = header;    } else {	header-&gt;parent = copy( (NodePtr)(_map-&gt;header-&gt;parent) );	header-&gt;parent-&gt;parent = header;	header-&gt;left = header-&gt;parent-&gt;minimum();	header-&gt;right = header-&gt;parent-&gt;maximum();    }}template &lt;class Key, class T&gt;Q_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 ){    if ( !p )	return 0;    NodePtr n = new Node( *p );    n-&gt;color = p-&gt;color;    if ( p-&gt;left ) {	n-&gt;left = copy( (NodePtr)(p-&gt;left) );	n-&gt;left-&gt;parent = n;    } else {	n-&gt;left = 0;    }    if ( p-&gt;right ) {	n-&gt;right = copy( (NodePtr)(p-&gt;right) );	n-&gt;right-&gt;parent = n;    } else {	n-&gt;right = 0;    }    return n;}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMapPrivate&lt;Key,T&gt;::clear(){    clear( (NodePtr)(header-&gt;parent) );    header-&gt;color = QMapNodeBase::Red;    header-&gt;parent = 0;    header-&gt;left = header-&gt;right = header;    node_count = 0;}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMapPrivate&lt;Key,T&gt;::clear( Q_TYPENAME QMapPrivate&lt;Key,T&gt;::NodePtr p ){    while ( p != 0 ) {	clear( (NodePtr)p-&gt;right );	NodePtr y = (NodePtr)p-&gt;left;	delete p;	p = y;    }}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::ConstIterator QMapPrivate&lt;Key,T&gt;::find(const Key&amp; k) const{    QMapNodeBase* y = header;        // Last node    QMapNodeBase* x = header-&gt;parent; // Root node.    while ( x != 0 ) {	// If as k &lt;= key(x) go left	if ( !( key(x) &lt; k ) ) {	    y = x;	    x = x-&gt;left;	} else {	    x = x-&gt;right;	}    }    // Was k bigger/smaller then the biggest/smallest    // element of the tree ? Return end()    if ( y == header || k &lt; key(y) )	return ConstIterator( header );    return ConstIterator( (NodePtr)y );}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::Iterator QMapPrivate&lt;Key,T&gt;::insertSingle( const Key&amp; k ){    // Search correct position in the tree    QMapNodeBase* y = header;    QMapNodeBase* x = header-&gt;parent;    bool result = TRUE;    while ( x != 0 ) {	result = ( k &lt; key(x) );	y = x;	x = result ? x-&gt;left : x-&gt;right;    }    // Get iterator on the last not empty one    Iterator j( (NodePtr)y );    if ( result ) {	// Smaller then the leftmost one ?	if ( j == begin() ) {	    return insert(x, y, k );	} else {	    // Perhaps daddy is the right one ?	    --j;	}    }    // Really bigger ?    if ( (j.node-&gt;key) &lt; k )	return insert(x, y, k );    // We are going to replace a node    return j;}template &lt;class Key, class T&gt;Q_INLINE_TEMPLATES Q_TYPENAME QMapPrivate&lt;Key,T&gt;::Iterator QMapPrivate&lt;Key,T&gt;::insert( QMapNodeBase* x, QMapNodeBase* y, const Key&amp; k ){    NodePtr z = new Node( k );    if (y == header || x != 0 || k &lt; key(y) ) {	y-&gt;left = z;                // also makes leftmost = z when y == header	if ( y == header ) {	    header-&gt;parent = z;	    header-&gt;right = z;	} else if ( y == header-&gt;left )	    header-&gt;left = z;           // maintain leftmost pointing to min node    } else {	y-&gt;right = z;	if ( y == header-&gt;right )	    header-&gt;right = z;          // maintain rightmost pointing to max node    }    z-&gt;parent = y;    z-&gt;left = 0;    z-&gt;right = 0;    rebalance( z, header-&gt;parent );    ++node_count;    return Iterator(z);}#ifdef QT_CHECK_RANGE# if !defined( QT_NO_DEBUG ) &amp;&amp; defined( QT_CHECK_MAP_RANGE )#  define QT_CHECK_INVALID_MAP_ELEMENT if ( empty() ) qWarning( "QMap: Warning invalid element" )#  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL Q_ASSERT( !empty() );# else#  define QT_CHECK_INVALID_MAP_ELEMENT#  define QT_CHECK_INVALID_MAP_ELEMENT_FATAL# endif#else# define QT_CHECK_INVALID_MAP_ELEMENT# define QT_CHECK_INVALID_MAP_ELEMENT_FATAL#endiftemplate&lt;class Key, class T&gt;class QMap{public:    /**     * Typedefs     */    typedef Key key_type;    typedef T mapped_type;    typedef QPair&lt;const key_type, mapped_type&gt; value_type;    typedef value_type* pointer;    typedef const value_type* const_pointer;    typedef value_type&amp; reference;    typedef const value_type&amp; const_reference;#ifndef QT_NO_STL    typedef ptrdiff_t  difference_type;#else    typedef int difference_type;#endif    typedef size_t      size_type;    typedef QMapIterator&lt;Key,T&gt; iterator;    typedef QMapConstIterator&lt;Key,T&gt; const_iterator;    typedef QPair&lt;iterator,bool&gt; insert_pair;    /**     * API     */    QMap()    {	sh = new QMapPrivate&lt; Key, T &gt;;    }    QMap( const QMap&lt;Key,T&gt;&amp; m )    {	sh = m.sh; sh-&gt;ref();    }#ifndef QT_NO_STL    QMap( const Q_TYPENAME std::map&lt;Key,T&gt;&amp; m )    {	sh = new QMapPrivate&lt;Key,T&gt;;#if defined(Q_OS_WIN32)	std::map&lt;Key,T&gt;::const_iterator it = m.begin();#else	QMapConstIterator&lt;Key,T&gt; it = m.begin();#endif	for ( ; it != m.end(); ++it ) {	    value_type p( (*it).first, (*it).second );	    insert( p );	}    }#endif    ~QMap()    {	if ( sh-&gt;deref() )	    delete sh;    }    QMap&lt;Key,T&gt;&amp; operator= ( const QMap&lt;Key,T&gt;&amp; m );#ifndef QT_NO_STL    QMap&lt;Key,T&gt;&amp; operator= ( const Q_TYPENAME std::map&lt;Key,T&gt;&amp; m )    {	clear();#if defined(Q_OS_WIN32)	std::map&lt;Key,T&gt;::const_iterator it = m.begin();#else	QMapConstIterator&lt;Key,T&gt; it = m.begin();#endif	for ( ; it != m.end(); ++it ) {	    value_type p( (*it).first, (*it).second );	    insert( p );	}	return *this;    }#endif    iterator begin() { detach(); return sh-&gt;begin(); }    iterator end() { detach(); return sh-&gt;end(); }    const_iterator begin() const { return ((const Priv*)sh)-&gt;begin(); }    const_iterator end() const { return ((const Priv*)sh)-&gt;end(); }    iterator replace( const Key&amp; k, const T&amp; v )    {	remove( k );	return insert( k, v );    }    size_type size() const    {	return sh-&gt;node_count;    }    bool empty() const    {	return sh-&gt;node_count == 0;    }    QPair&lt;iterator,bool&gt; insert( const value_type&amp; x );    void erase( iterator it )    {	detach();	sh-&gt;remove( it );    }    void erase( const key_type&amp; k );    size_type count( const key_type&amp; k ) const;    T&amp; operator[] ( const Key&amp; k );    void clear();    typedef QMapIterator&lt; Key, T &gt; Iterator;    typedef QMapConstIterator&lt; Key, T &gt; ConstIterator;    typedef T ValueType;    typedef QMapPrivate&lt; Key, T &gt; Priv;    iterator find ( const Key&amp; k )    {	detach();	return iterator( sh-&gt;find( k ).node );    }    const_iterator find ( const Key&amp; k ) const {	return sh-&gt;find( k ); }    const T&amp; operator[] ( const Key&amp; k ) const	{ QT_CHECK_INVALID_MAP_ELEMENT; return sh-&gt;find( k ).data(); }    bool contains ( const Key&amp; k ) const	{ return find( k ) != end(); }	//{ return sh-&gt;find( k ) != ((const Priv*)sh)-&gt;end(); }    size_type count() const { return sh-&gt;node_count; }    QValueList&lt;Key&gt; keys() const {	QValueList&lt;Key&gt; r;	for (const_iterator i=begin(); i!=end(); ++i)	    r.append(i.key());	return r;    }    QValueList&lt;T&gt; values() const {	QValueList&lt;T&gt; r;	for (const_iterator i=begin(); i!=end(); ++i)	    r.append(*i);	return r;    }    bool isEmpty() const { return sh-&gt;node_count == 0; }    iterator insert( const Key&amp; key, const T&amp; value, bool overwrite = TRUE );    void remove( iterator it ) { detach(); sh-&gt;remove( it ); }    void remove( const Key&amp; k );#if defined(Q_FULL_TEMPLATE_INSTANTIATION)    bool operator==( const QMap&lt;Key,T&gt;&amp; ) const { return FALSE; }#ifndef QT_NO_STL    bool operator==( const Q_TYPENAME std::map&lt;Key,T&gt;&amp; ) const { return FALSE; }#endif#endifprotected:    /**     * Helpers     */    void detach() {  if ( sh-&gt;count &gt; 1 ) detachInternal(); }    Priv* sh;private:    void detachInternal();};template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES QMap&lt;Key,T&gt;&amp; QMap&lt;Key,T&gt;::operator= ( const QMap&lt;Key,T&gt;&amp; m ){    m.sh-&gt;ref();    if ( sh-&gt;deref() )	delete sh;    sh = m.sh;    return *this;}template&lt;class Key, class T&gt;Q_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 ){    detach();    size_type n = size();    iterator it = sh-&gt;insertSingle( x.first );    bool inserted = FALSE;    if ( n &lt; size() ) {	inserted = TRUE;	it.data() = x.second;    }    return QPair&lt;iterator,bool&gt;( it, inserted );}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::erase( const Key&amp; k ){    detach();    iterator it( sh-&gt;find( k ).node );    if ( it != end() )	sh-&gt;remove( it );}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES Q_TYPENAME QMap&lt;Key,T&gt;::size_type QMap&lt;Key,T&gt;::count( const Key&amp; k ) const{    const_iterator it( sh-&gt;find( k ).node );    if ( it != end() ) {	size_type c = 0;	while ( it != end() ) {	    ++it;	    ++c;	}	return c;    }    return 0;}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES T&amp; QMap&lt;Key,T&gt;::operator[] ( const Key&amp; k ){    detach();    QMapNode&lt;Key,T&gt;* p = sh-&gt;find( k ).node;    if ( p != sh-&gt;end().node )	return p-&gt;data;    return insert( k, T() ).data();}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::clear(){    if ( sh-&gt;count == 1 )	sh-&gt;clear();    else {	sh-&gt;deref();	sh = new QMapPrivate&lt;Key,T&gt;;    }}template&lt;class Key, class T&gt;Q_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 ){    detach();    size_type n = size();    iterator it = sh-&gt;insertSingle( key );    if ( overwrite || n &lt; size() )	it.data() = value;    return it;}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::remove( const Key&amp; k ){    detach();    iterator it( sh-&gt;find( k ).node );    if ( it != end() )	sh-&gt;remove( it );}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES void QMap&lt;Key,T&gt;::detachInternal(){    sh-&gt;deref(); sh = new QMapPrivate&lt;Key,T&gt;( sh );}#ifndef QT_NO_DATASTREAMtemplate&lt;class Key, class T&gt;Q_INLINE_TEMPLATES QDataStream&amp; operator&gt;&gt;( QDataStream&amp; s, QMap&lt;Key,T&gt;&amp; m ) {    m.clear();    Q_UINT32 c;    s &gt;&gt; c;    for( Q_UINT32 i = 0; i &lt; c; ++i ) {	Key k; T t;	s &gt;&gt; k &gt;&gt; t;	m.insert( k, t );	if ( s.atEnd() )	    break;    }    return s;}template&lt;class Key, class T&gt;Q_INLINE_TEMPLATES QDataStream&amp; operator&lt;&lt;( QDataStream&amp; s, const QMap&lt;Key,T&gt;&amp; m ) {    s &lt;&lt; (Q_UINT32)m.size();    QMapConstIterator&lt;Key,T&gt; it = m.begin();    for( ; it != m.end(); ++it )	s &lt;&lt; it.key() &lt;&lt; it.data();    return s;}#endif#endif // QMAP_H</pre><!-- eof --><p><address><hr><div align=center><table width=100% cellspacing=0 border=0><tr><td>Copyright &copy; 2002 <a href="http://www.trolltech.com">Trolltech</a><td><a href="http://www.trolltech.com/trademarks.html">Trademarks</a><td align=right><div align=right>Qt version 3.0.5</div></table></div></address></body></html>

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?