diff options
author | Thorbjørn Martsum <tmartsum@gmail.com> | 2013-09-24 06:37:41 +0200 |
---|---|---|
committer | The Qt Project <gerrit-noreply@qt-project.org> | 2013-10-15 12:10:09 +0200 |
commit | 5482881b8a7103eb12ec9662dd2198755c6e3c18 (patch) | |
tree | e3d7c75ca7641d11e886aad4bdd49c3a1f17d9ca /src | |
parent | 499957eb8b1c5150823f05f40f32b04ba13b1640 (diff) |
QMap - improve docs a bit (mainly by adding more time complexities)
Change-Id: I8a361ef09c338bbba228fd774b2bfd938869adc5
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qmap.cpp | 15 |
1 files changed, 13 insertions, 2 deletions
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index 4da9669a39..9aebbb7b3c 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -395,7 +395,7 @@ void QMapDataBase::freeData(QMapDataBase *d) differences are: \list - \li QHash provides faster lookups than QMap. (See \l{Algorithmic + \li QHash provides average faster lookups than QMap. (See \l{Algorithmic Complexity} for details.) \li When iterating over a QHash, the items are arbitrarily ordered. With QMap, the items are always sorted by key. @@ -901,6 +901,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Returns a reference to the smallest key in the map. This function assumes that the map is not empty. + This executes in \l{constant time}. + \sa lastKey(), first(), isEmpty() */ @@ -909,6 +911,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Returns a reference to the largest key in the map. This function assumes that the map is not empty. + This executes in \l{logarithmic time}. + \sa firstKey(), last(), isEmpty() */ @@ -917,6 +921,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Returns a reference to the first value in the map, that is the value mapped to the smallest key. This function assumes that the map is not empty. + When unshared (or const version is called), this executes in \l{constant time}. + \sa last(), firstKey(), isEmpty() */ @@ -930,6 +936,8 @@ void QMapDataBase::freeData(QMapDataBase *d) Returns a reference to the last value in the map, that is the value mapped to the largest key. This function assumes that the map is not empty. + When unshared (or const version is called), this executes in \l{logarithmic time}. + \sa first(), lastKey(), isEmpty() */ @@ -1057,8 +1065,11 @@ void QMapDataBase::freeData(QMapDataBase *d) If there are multiple items with the key \a key, then exactly one of them is replaced with \a value. + If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}. + When creating a map from sorted data inserting the largest key first with constBegin() - is faster than inserting in sorted order with constEnd() + is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed + to check if the hint is valid) needs \l{logarithmic time}. \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might crash but there is also a risk that it will silently corrupt both the map and the \a pos map. |