- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- Class List
- Class Hierarchy
- Class Members

Classes | Public Types | Public Member Functions | Friends

# QMap< Key, T > Class Template Reference

Search for all occurrences

## Detailed Description

### template<class Key, class T>
class QMap< Key, T >

Definition at line 161 of file qmap.h.

`#include <qmap.h>`

Inheritance diagram for QMap< Key, T >:
[legend]

List of all members.

## Classes
class | const_iterator
class | iterator
## Public Types
typedef iterator | Iterator
typedef const_iterator | ConstIterator
typedef Key | key_type
typedef T | mapped_type
typedef qptrdiff | difference_type
typedef int | size_type
## Public Member Functions
| QMap ()
| QMap (const QMap< Key, T > &other)
| ~QMap ()
QMap< Key, T > & | operator= (const QMap< Key, T > &other)
| QMap (const typename std::map< Key, T > &other)
std::map< Key, T > | toStdMap () const
bool | operator== (const QMap< Key, T > &other) const
bool | operator!= (const QMap< Key, T > &other) const
int | size () const
bool | isEmpty () const
void | detach ()
bool | isDetached () const
void | setSharable (bool sharable)
bool | isSharedWith (const QMap< Key, T > &other) const
void | setInsertInOrder (bool ordered)
void | clear ()
int | remove (const Key &key)
T | take (const Key &key)
bool | contains (const Key &key) const
const Key | key (const T &value) const
const Key | key (const T &value, const Key &defaultKey) const
const T | value (const Key &key) const
const T | value (const Key &key, const T &defaultValue) const
T & | operator[] (const Key &key)
const T | operator[] (const Key &key) const
QList< Key > | uniqueKeys () const
QList< Key > | keys () const
QList< Key > | keys (const T &value) const
QList< T > | values () const
QList< T > | values (const Key &key) const
int | count (const Key &key) const
iterator | begin ()
const_iterator | begin () const
const_iterator | constBegin () const
iterator | end ()
const_iterator | end () const
const_iterator | constEnd () const
iterator | erase (iterator it)
int | count () const
iterator | find (const Key &key)
const_iterator | find (const Key &key) const
const_iterator | constFind (const Key &key) const
iterator | lowerBound (const Key &key)
const_iterator | lowerBound (const Key &key) const
iterator | upperBound (const Key &key)
const_iterator | upperBound (const Key &key) const
iterator | insert (const Key &key, const T &value)
iterator | insertMulti (const Key &key, const T &value)
QMap< Key, T > & | unite (const QMap< Key, T > &other)
bool | empty () const
## Friends
class | iterator
class | const_iterator

## Member Typedef Documentation

typedef iterator Iterator

Search for all occurrences

Definition at line 385 of file qmap.h.

typedef const_iterator ConstIterator

Search for all occurrences

Definition at line 386 of file qmap.h.

typedef Key key_type

Search for all occurrences

Definition at line 406 of file qmap.h.

typedef T mapped_type

Search for all occurrences

Definition at line 407 of file qmap.h.

typedef qptrdiff difference_type

Search for all occurrences

Definition at line 408 of file qmap.h.

typedef int size_type

Search for all occurrences

Definition at line 409 of file qmap.h.

## Constructor & Destructor Documentation

QMap | ( |  | ) | `[inline]`

Definition at line 184 of file qmap.h.

    : d(&QMapData::shared_null) { d->ref.ref(); }

QMap | ( | const QMap< Key, T > & | other | ) | `[inline]`

Definition at line 185 of file qmap.h.

                                               : d(other.d)
        { d->ref.ref(); if (!d->sharable) detach(); }

~QMap | ( |  | ) | `[inline]`

Definition at line 187 of file qmap.h.

    { if (!d) return; if (!d->ref.deref()) freeData(d); }

QMap | ( | const typename std::map< Key, T > & | other | ) | `[explicit]`

## Member Function Documentation

Q_INLINE_TEMPLATE QMap< Key, T > & operator= | ( | const QMap< Key, T > & | other | ) |

Definition at line 426 of file qmap.h.

    {
        if (d != other.d) {
            QMapData* o = other.d;
            o->ref.ref();
            if (!d->ref.deref())
                freeData(d);
            d = o;
            if (!d->sharable)
                detach_helper();
        }
        return *this;
    }

Q_OUTOFLINE_TEMPLATE std::map< Key, T > toStdMap | ( |  | ) | const

Search for all occurrences

Definition at line 955 of file qmap.h.

    {
        std::map<Key, T> map;
        const_iterator it = end();
        while (it != begin()) {
            --it;
            map.insert(std::pair<Key, T>(it.key(), it.value()));
        }
        return map;
    }

Q_OUTOFLINE_TEMPLATE bool operator== | ( | const QMap< Key, T > & | other | ) | const

Definition at line 921 of file qmap.h.

    {
        if (size() != other.size())
            return false;
        if (d == other.d)
            return true;

        const_iterator it1 = begin();
        const_iterator it2 = other.begin();

        while (it1 != end()) {
            if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
                return false;
            ++it2;
            ++it1;
        }
        return true;
    }

bool operator!= | ( | const QMap< Key, T > & | other | ) | const `[inline]`

Definition at line 196 of file qmap.h.

    { return !(*this == other); }

int size | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 198 of file qmap.h.

    { return d->size; }

bool isEmpty | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 200 of file qmap.h.

    { return d->size == 0; }

void detach | ( |  | ) | `[inline]`

Search for all occurrences

Definition at line 202 of file qmap.h.

    { if (d->ref != 1) detach_helper(); }

bool isDetached | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 203 of file qmap.h.

    { return d->ref == 1; }

void setSharable | ( | bool | sharable | ) | `[inline]`

Search for all occurrences

Definition at line 204 of file qmap.h.

    { if (!sharable) detach(); d->sharable = sharable; }

bool isSharedWith | ( | const QMap< Key, T > & | other | ) | const `[inline]`

Search for all occurrences

Definition at line 205 of file qmap.h.

    { return d == other.d; }

void setInsertInOrder | ( | bool | ordered | ) | `[inline]`

Search for all occurrences

Definition at line 206 of file qmap.h.

    { d->insertInOrder = ordered; }

Q_INLINE_TEMPLATE void clear | ( |  | ) |

Search for all occurrences

Definition at line 441 of file qmap.h.

    {
        *this = QMap<Key, T>();
    }

Q_OUTOFLINE_TEMPLATE int remove | ( | const Key & | key | ) |

Search for all occurrences

Definition at line 658 of file qmap.h.

    {
        detach();

        QMapData::Node *update[QMapData::LastLevel + 1];
        QMapData::Node *cur = e;
        QMapData::Node *next = e;
        int oldSize = d->size;

        for (int i = d->topLevel; i >= 0; i--) {
            while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
                cur = next;
            update[i] = cur;
        }

        if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
            bool deleteNext = true;
            do {
                cur = next;
                next = cur->forward[0];
                deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
                concrete(cur)->key.~Key();
                concrete(cur)->value.~T();
                d->node_delete(update, payload(), cur);
            } while (deleteNext);
        }
        return oldSize - d->size;
    }

Q_OUTOFLINE_TEMPLATE T take | ( | const Key & | key | ) |

Search for all occurrences

Definition at line 688 of file qmap.h.

    {
        detach();

        QMapData::Node *update[QMapData::LastLevel + 1];
        QMapData::Node *cur = e;
        QMapData::Node *next = e;

        for (int i = d->topLevel; i >= 0; i--) {
            while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
                cur = next;
            update[i] = cur;
        }

        if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
            T t = concrete(next)->value;
            concrete(next)->key.~Key();
            concrete(next)->value.~T();
            d->node_delete(update, payload(), next);
            return t;
        }
        return T();
    }

Q_INLINE_TEMPLATE bool contains | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 550 of file qmap.h.

    {
        return findNode(akey) != e;
    }

Q_OUTOFLINE_TEMPLATE const Key key | ( | const T & | value | ) | const

Search for all occurrences

Definition at line 840 of file qmap.h.

    {
        return key(avalue, Key());
    }

Q_OUTOFLINE_TEMPLATE const Key key | ( | const T & | value,
|  | const Key & | defaultKey
| ) |  | const

Search for all occurrences

Definition at line 846 of file qmap.h.

    {
        const_iterator i = begin();
        while (i != end()) {
            if (i.value() == avalue)
                return i.key();
            ++i;
        }

        return defaultKey;
    }

Q_INLINE_TEMPLATE const T value | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 496 of file qmap.h.

    {
        QMapData::Node *node;
        if (d->size == 0 || (node = findNode(akey)) == e) {
            return T();
        } else {
            return concrete(node)->value;
        }
    }

Q_INLINE_TEMPLATE const T value | ( | const Key & | key,
|  | const T & | defaultValue
| ) |  | const

Search for all occurrences

Definition at line 507 of file qmap.h.

    {
        QMapData::Node *node;
        if (d->size == 0 || (node = findNode(akey)) == e) {
            return adefaultValue;
        } else {
            return concrete(node)->value;
        }
    }

Q_INLINE_TEMPLATE T & operator[] | ( | const Key & | key | ) |

Definition at line 524 of file qmap.h.

    {
        detach();

        QMapData::Node *update[QMapData::LastLevel + 1];
        QMapData::Node *node = mutableFindNode(update, akey);
        if (node == e)
            node = node_create(d, update, akey, T());
        return concrete(node)->value;
    }

Q_INLINE_TEMPLATE const T operator[] | ( | const Key & | key | ) | const

Definition at line 518 of file qmap.h.

    {
        return value(akey);
    }

Q_OUTOFLINE_TEMPLATE QList< Key > uniqueKeys | ( |  | ) | const

Search for all occurrences

Definition at line 794 of file qmap.h.

    {
        QList<Key> res;
        res.reserve(size()); // May be too much, but assume short lifetime
        const_iterator i = begin();
        if (i != end()) {
            for (;;) {
                const Key &aKey = i.key();
                res.append(aKey);
                do {
                    if (++i == end())
                        goto break_out_of_outer_loop;
                } while (!(aKey < i.key()));   // loop while (key == i.key())
            }
        }
    break_out_of_outer_loop:
        return res;
    }

Q_OUTOFLINE_TEMPLATE QList< Key > keys | ( |  | ) | const

Search for all occurrences

Definition at line 814 of file qmap.h.

    {
        QList<Key> res;
        res.reserve(size());
        const_iterator i = begin();
        while (i != end()) {
            res.append(i.key());
            ++i;
        }
        return res;
    }

Q_OUTOFLINE_TEMPLATE QList< Key > keys | ( | const T & | value | ) | const

Search for all occurrences

Definition at line 827 of file qmap.h.

    {
        QList<Key> res;
        const_iterator i = begin();
        while (i != end()) {
            if (i.value() == avalue)
                res.append(i.key());
            ++i;
        }
        return res;
    }

Q_OUTOFLINE_TEMPLATE QList< T > values | ( |  | ) | const

Search for all occurrences

Definition at line 859 of file qmap.h.

    {
        QList<T> res;
        res.reserve(size());
        const_iterator i = begin();
        while (i != end()) {
            res.append(i.value());
            ++i;
        }
        return res;
    }

Q_OUTOFLINE_TEMPLATE QList< T > values | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 872 of file qmap.h.

    {
        QList<T> res;
        QMapData::Node *node = findNode(akey);
        if (node != e) {
            do {
                res.append(concrete(node)->value);
                node = node->forward[0];
            } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
        }
        return res;
    }

Q_INLINE_TEMPLATE int count | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 536 of file qmap.h.

    {
        int cnt = 0;
        QMapData::Node *node = findNode(akey);
        if (node != e) {
            do {
                ++cnt;
                node = node->forward[0];
            } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
        }
        return cnt;
    }

iterator begin | ( |  | ) | `[inline]`

Search for all occurrences

Definition at line 369 of file qmap.h.

    { detach(); return iterator(e->forward[0]); }

const_iterator begin | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 370 of file qmap.h.

    { return const_iterator(e->forward[0]); }

const_iterator constBegin | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 371 of file qmap.h.

    { return const_iterator(e->forward[0]); }

iterator end | ( |  | ) | `[inline]`

Search for all occurrences

Definition at line 372 of file qmap.h.

                              {
            detach();
            return iterator(e);
        }

const_iterator end | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 376 of file qmap.h.

    { return const_iterator(e); }

const_iterator constEnd | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 377 of file qmap.h.

    { return const_iterator(e); }

Q_OUTOFLINE_TEMPLATE QMap< Key, T >::iterator erase | ( | iterator | it | ) |

Search for all occurrences

Definition at line 713 of file qmap.h.

    {
        QMapData::Node *update[QMapData::LastLevel + 1];
        QMapData::Node *cur = e;
        QMapData::Node *next = e;

        if (it == iterator(e))
            return it;

        for (int i = d->topLevel; i >= 0; i--) {
            while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
                cur = next;
            update[i] = cur;
        }

        while (next != e) {
            cur = next;
            next = cur->forward[0];
            if (cur == it) {
                concrete(cur)->key.~Key();
                concrete(cur)->value.~T();
                d->node_delete(update, payload(), cur);
                return iterator(next);
            }

            for (int i = 0; i <= d->topLevel; ++i) {
                if (update[i]->forward[i] != cur)
                    break;
                update[i] = cur;
            }
        }
        return end();
    }

int count | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 387 of file qmap.h.

    { return d->size; }

Q_INLINE_TEMPLATE QMap< Key, T >::iterator find | ( | const Key & | key | ) |

Search for all occurrences

Definition at line 615 of file qmap.h.

    {
        detach();
        return iterator(findNode(akey));
    }

Q_INLINE_TEMPLATE QMap< Key, T >::const_iterator find | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 603 of file qmap.h.

    {
        return const_iterator(findNode(akey));
    }

Q_INLINE_TEMPLATE QMap< Key, T >::const_iterator constFind | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 609 of file qmap.h.

    {
        return const_iterator(findNode(akey));
    }

Q_INLINE_TEMPLATE QMap< Key, T >::iterator lowerBound | ( | const Key & | key | ) |

Search for all occurrences

Definition at line 895 of file qmap.h.

    {
        detach();
        return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
    }

Q_INLINE_TEMPLATE QMap< Key, T >::const_iterator lowerBound | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 887 of file qmap.h.

    {
        QMapData::Node *update[QMapData::LastLevel + 1];
        mutableFindNode(update, akey);
        return const_iterator(update[0]->forward[0]);
    }

Q_INLINE_TEMPLATE QMap< Key, T >::iterator upperBound | ( | const Key & | key | ) |

Search for all occurrences

Definition at line 914 of file qmap.h.

    {
        detach();
        return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
    }

Q_INLINE_TEMPLATE QMap< Key, T >::const_iterator upperBound | ( | const Key & | key | ) | const

Search for all occurrences

Definition at line 903 of file qmap.h.

    {
        QMapData::Node *update[QMapData::LastLevel + 1];
        mutableFindNode(update, akey);
        QMapData::Node *node = update[0]->forward[0];
        while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
            node = node->forward[0];
        return const_iterator(node);
    }

Q_INLINE_TEMPLATE QMap< Key, T >::iterator insert | ( | const Key & | key,
|  | const T & | value
| ) |  |

Search for all occurrences

Reimplemented in QMultiMap< Key, T >.

Definition at line 556 of file qmap.h.

    {
        detach();

        QMapData::Node *update[QMapData::LastLevel + 1];
        QMapData::Node *node = mutableFindNode(update, akey);
        if (node == e) {
            node = node_create(d, update, akey, avalue);
        } else {
            concrete(node)->value = avalue;
        }
        return iterator(node);
    }

Q_INLINE_TEMPLATE QMap< Key, T >::iterator insertMulti | ( | const Key & | key,
|  | const T & | value
| ) |  |

Search for all occurrences

Definition at line 592 of file qmap.h.

    {
        detach();

        QMapData::Node *update[QMapData::LastLevel + 1];
        mutableFindNode(update, akey);
        return iterator(node_create(d, update, akey, avalue));
    }

Q_INLINE_TEMPLATE QMap< Key, T > & unite | ( | const QMap< Key, T > & | other | ) |

Search for all occurrences

Definition at line 622 of file qmap.h.

    {
        QMap<Key, T> copy(other);
        const_iterator it = copy.constEnd();
        const const_iterator b = copy.constBegin();
        while (it != b) {
            --it;
            insertMulti(it.key(), it.value());
        }
        return *this;
    }

bool empty | ( |  | ) | const `[inline]`

Search for all occurrences

Definition at line 410 of file qmap.h.

    { return isEmpty(); }

## Friends And Related Function Documentation

friend class iterator `[friend]`

Search for all occurrences

Definition at line 296 of file qmap.h.

friend class const_iterator `[friend]`

Search for all occurrences

Definition at line 366 of file qmap.h.

## Member Data Documentation

QMapData* d

Search for all occurrences

Definition at line 167 of file qmap.h.

QMapData::Node* e

Search for all occurrences

Definition at line 168 of file qmap.h.

The documentation for this class was generated from the following file:

- QtCore/qmap.h