Document that keys() and values() run in linear time

keys() and values() can be slower for large containers.
I ran into this recently when profiling, and was surprised that keys()
had to build the list of keys (by appending in a loop).

Pick-to: 5.15 5.12
Change-Id: I73215f5a917790236704ad7ef78cefc4a049cd89
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

3 files changed, 28 insertions, 0 deletions

diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index 0f46e7f113..ff2ae6813c 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -1431,6 +1431,10 @@ size_t qHash(long double key, size_t seed) noexcept
 
     The order is guaranteed to be the same as that used by values().
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyBegin() to
+    \l keyEnd().
+
     \sa values(), key()
 */
 
@@ -1453,6 +1457,10 @@ size_t qHash(long double key, size_t seed) noexcept
 
     The order is guaranteed to be the same as that used by keys().
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyValueBegin() to
+    \l keyValueEnd().
+
     \sa keys(), value()
 */
 
@@ -2518,6 +2526,10 @@ size_t qHash(long double key, size_t seed) noexcept
 
     The order is guaranteed to be the same as that used by values().
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyBegin() to
+    \l keyEnd().
+
     \sa values(), key()
 */
 
@@ -2530,6 +2542,10 @@ size_t qHash(long double key, size_t seed) noexcept
 
     The order is guaranteed to be the same as that used by keys().
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyValueBegin() to
+    \l keyValueEnd().
+
     \sa keys(), value()
 */
 
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp
index fd2136c8ef..279dacda0b 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.cpp
@@ -759,6 +759,10 @@ void QMapDataBase::freeData(QMapDataBase *d)
 
     The order is guaranteed to be the same as that used by values().
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyBegin() to
+    \l keyEnd().
+
     \sa QMultiMap::uniqueKeys(), values(), key()
 */
 
@@ -798,6 +802,10 @@ void QMapDataBase::freeData(QMapDataBase *d)
     all of its values will be in the list, and not just the most
     recently inserted one.
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l keyValueBegin() to
+    \l keyValueEnd().
+
     \sa keys(), value()
 */
 
diff --git a/src/corelib/tools/qset.qdoc b/src/corelib/tools/qset.qdoc
index eb6b542181..b6aae2c7ca 100644
--- a/src/corelib/tools/qset.qdoc
+++ b/src/corelib/tools/qset.qdoc
@@ -1093,6 +1093,10 @@
 
     \include containers-range-constructor.qdocinc
 
+    This function creates a new list, in \l {linear time}. The time and memory
+    use that entails can be avoided by iterating from \l constBegin() to
+    \l constEnd().
+
     \sa fromList(), QList::fromSet()
 */