From 5482881b8a7103eb12ec9662dd2198755c6e3c18 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Thorbj=C3=B8rn=20Martsum?= Date: Tue, 24 Sep 2013 06:37:41 +0200 Subject: QMap - improve docs a bit (mainly by adding more time complexities) Change-Id: I8a361ef09c338bbba228fd774b2bfd938869adc5 Reviewed-by: Olivier Goffart Reviewed-by: Thiago Macieira --- src/corelib/tools/qmap.cpp | 15 +++++++++++++-- 1 file changed, 13 insertions(+), 2 deletions(-) (limited to 'src') 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. -- cgit v1.2.3