diff options
Diffstat (limited to 'src/corelib/doc/src/containers.qdoc')
-rw-r--r-- | src/corelib/doc/src/containers.qdoc | 234 |
1 files changed, 108 insertions, 126 deletions
diff --git a/src/corelib/doc/src/containers.qdoc b/src/corelib/doc/src/containers.qdoc index 70c22b1407..847be1bff6 100644 --- a/src/corelib/doc/src/containers.qdoc +++ b/src/corelib/doc/src/containers.qdoc @@ -1,29 +1,5 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the documentation of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:FDL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Free Documentation License Usage -** Alternatively, this file may be used under the terms of the GNU Free -** Documentation License version 1.3 as published by the Free Software -** Foundation and appearing in the file included in the packaging of -** this file. Please review the following information to ensure -** the GNU Free Documentation License version 1.3 requirements -** will be met: https://www.gnu.org/licenses/fdl-1.3.html. -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2016 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only /*! \page containers.html @@ -61,12 +37,10 @@ STL's \l{generic algorithms}. \l{Java-style Iterators} are provided for backwards compatibility. - Qt also offers a \l{foreach} keyword that make it very - easy to iterate over all the items stored in a container. - \note Since Qt 5.14, range constructors are available for most of the container classes. QMultiMap is a notable exception. Their use is - encouraged in place of the various from/to methods. For example: + encouraged to replace of the various deprecated from/to methods of Qt 5. + For example: \snippet code/doc_src_containers.cpp 25 @@ -218,7 +192,30 @@ the C++ language doesn't specify any initialization; in those cases, Qt's containers automatically initialize the value to 0. - \section1 The Iterator Classes + \section1 Iterating over Containers + + \section2 Range-based for + + Range-based \c for should preferably be used for containers: + + \snippet code/doc_src_containers.cpp range_for + + Note that when using a Qt container in a non-const context, + \l{implicit sharing} may perform an undesired detach of the container. + To prevent this, use \c std::as_const(): + + \snippet code/doc_src_containers.cpp range_for_as_const + + For associative containers, this will loop over the values. + + \section2 Index-based + + For sequential containers that store their items contiguously in memory + (for example, QList), index-based iteration can be used: + + \snippet code/doc_src_containers.cpp index + + \section2 The Iterator Classes Iterators provide a uniform means to access items in a container. Qt's container classes provide two types of iterators: STL-style @@ -227,7 +224,7 @@ from \l{Implicit Sharing}{implicitly shared copies} due to a call to a non-const member function. - \section2 STL-Style Iterators + \section3 STL-Style Iterators STL-style iterators have been available since the release of Qt 2.0. They are compatible with Qt's and STL's \l{generic @@ -289,12 +286,10 @@ In the code snippets so far, we used the unary \c * operator to retrieve the item (of type QString) stored at a certain iterator - position, and we then called QString::toLower() on it. Most C++ - compilers also allow us to write \c{i->toLower()}, but some - don't. + position, and we then called QString::toLower() on it. - For read-only access, you can use const_iterator, \l{QList::constBegin}{constBegin()}, - and \l{QList::constEnd()}{constEnd()}. For example: + For read-only access, you can use const_iterator, \l{QList::cbegin}{cbegin()}, + and \l{QList::cend()}{cend()}. For example: \snippet code/doc_src_containers.cpp 12 @@ -342,7 +337,7 @@ This problem doesn't occur with functions that return a const or non-const reference to a container. - \section3 Implicit sharing iterator problem + \section4 Implicit sharing iterator problem \l{Implicit sharing} has another consequence on STL-style iterators: you should avoid copying a container while @@ -355,88 +350,68 @@ The above example only shows a problem with QList, but the problem exists for all the implicitly shared Qt containers. - \section2 Java-Style Iterators - \l{java-style-iterators}{Java-Style iterators} were introduced in Qt 4. Their API is modelled + \section3 Java-Style Iterators + \l{java-style-iterators}{Java-Style iterators} + are modelled on Java's iterator classes. - New code should should prefer \l{STL-Style Iterators}. - - \target foreach - \section1 The foreach Keyword + New code should prefer \l{STL-Style Iterators}. - If you just want to iterate over all the items in a container - in order, you can use Qt's \c foreach keyword. The keyword is a - Qt-specific addition to the C++ language, and is implemented - using the preprocessor. + \section1 Qt containers compared with std containers - Its syntax is: \c foreach (\e variable, \e container) \e - statement. For example, here's how to use \c foreach to iterate - over a QList<QString>: - - \snippet code/doc_src_containers.cpp 15 - - The \c foreach code is significantly shorter than the equivalent - code that uses iterators: + \table + \header \li Qt container \li Closest std container - \snippet code/doc_src_containers.cpp 16 + \row \li \l{QList}<T> + \li Similar to std::vector<T> - Unless the data type contains a comma (e.g., \c{QPair<int, - int>}), the variable used for iteration can be defined within the - \c foreach statement: + \l{QList} and \l{QVector} were unified in Qt 6. Both + use the datamodel from QVector. QVector is now an alias to QList. - \snippet code/doc_src_containers.cpp 17 + This means that QList is not implemented as a linked list, so if + you need constant time insert, delete, append or prepend, + consider \c std::list<T>. See \l{QList} for details. - And like any other C++ loop construct, you can use braces around - the body of a \c foreach loop, and you can use \c break to leave - the loop: + \row \li \l{QVarLengthArray}<T, Prealloc> + \li Resembles a mix of std::array<T> and std::vector<T>. - \snippet code/doc_src_containers.cpp 18 + For performance reasons, QVarLengthArray lives on the stack unless + resized. Resizing it automatically causes it to use the heap instead. - With QMap and QHash, \c foreach accesses the value component of - the (key, value) pairs automatically, so you should not call - values() on the container (it would generate an unnecessary copy, - see below). If you want to iterate over both the keys and the - values, you can use iterators (which are faster), or you can - obtain the keys, and use them to get the values too: + \row \li \l{QStack}<T> + \li Similar to std::stack<T>, inherits from \l{QList}. - \snippet code/doc_src_containers.cpp 19 + \row \li \l{QQueue}<T> + \li Similar to std::queue<T>, inherits from \l{QList}. - For a multi-valued map: + \row \li \l{QSet}<T> + \li Similar to std::unordered_set<T>. Internally, \l{QSet} is implemented with a + \l{QHash}. - \snippet code/doc_src_containers.cpp 20 + \row \li \l{QMap}<Key, T> + \li Similar to std::map<Key, T>. - Qt automatically takes a copy of the container when it enters a - \c foreach loop. If you modify the container as you are - iterating, that won't affect the loop. (If you do not modify the - container, the copy still takes place, but thanks to \l{implicit - sharing} copying a container is very fast.) + \row \li \l{QMultiMap}<Key, T> + \li Similar to std::multimap<Key, T>. - Since foreach creates a copy of the container, using a non-const - reference for the variable does not allow you to modify the original - container. It only affects the copy, which is probably not what you - want. + \row \li \l{QHash}<Key, T> + \li Most similar to std::unordered_map<Key, T>. - An alternative to Qt's \c foreach loop is the range-based \c for that is - part of C++ 11 and newer. However, keep in mind that the range-based - \c for might force a Qt container to \l{Implicit Sharing}{detach}, whereas - \c foreach would not. But using \c foreach always copies the container, - which is usually not cheap for STL containers. If in doubt, prefer - \c foreach for Qt containers, and range based \c for for STL ones. + \row \li \l{QMultiHash}<Key, T> + \li Most similar to std::unordered_multimap<Key, T>. - In addition to \c foreach, Qt also provides a \c forever - pseudo-keyword for infinite loops: + \endtable - \snippet code/doc_src_containers.cpp 21 + \section1 Qt containers and std algorithms - If you're worried about namespace pollution, you can disable - these macros by adding the following line to your \c .pro file: + You can use Qt containers with functions from \c{#include <algorithm>}. - \snippet code/doc_src_containers.cpp 22 + \snippet code/doc_src_containers.cpp 26 \section1 Other Container-Like Classes Qt includes other template classes that resemble containers in some respects. These classes don't provide iterators and cannot - be used with the \c foreach keyword. + be used with the \l foreach keyword. \list \li QCache<Key, T> provides a cache to store objects of a certain @@ -527,6 +502,29 @@ with the expected number of items before you insert the items. The next section discusses this topic in more depth. + \section1 Optimizations for Primitive and Relocatable Types + + Qt containers can use optimized code paths if the stored + elements are relocatable or even primitive. + However, whether types are primitive or relocatable + cannot be detected in all cases. + You can declare your types to be primitive or relocatable + by using the Q_DECLARE_TYPEINFO macro with the Q_PRIMITIVE_TYPE + flag or the Q_RELOCATABLE_TYPE flag. See the documentation + of Q_DECLARE_TYPEINFO for further details and usage examples. + + If you do not use Q_DECLARE_TYPEINFO, + Qt will use + \l {https://en.cppreference.com/w/cpp/types/is_trivial} {std::is_trivial_v<T>} + to identify primitive + types and it will require both + \l {https://en.cppreference.com/w/cpp/types/is_trivially_copyable} {std::is_trivially_copyable_v<T>} + and + \l {https://en.cppreference.com/w/cpp/types/is_destructible} {std::is_trivially_destructible_v<T>} + to identify relocatable types. + This is always a safe choice, albeit + of maybe suboptimal performance. + \section1 Growth Strategies QList<T>, QString, and QByteArray store their items @@ -543,39 +541,23 @@ We build the string \c out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to - the QString string. Then the following 18 reallocations (out of a - possible 15000) occur when QString runs out of space: 4, 8, 12, - 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, - 12276, 14324, 16372. At the end, the QString has 16372 Unicode + the QString string. Then the following 11 reallocations (out of a + possible 15000) occur when QString runs out of space: 8, 24, 56, + 120, 248, 504, 1016, 2040, 4088, 8184, 16376. + At the end, the QString has 16376 Unicode characters allocated, 15000 of which are occupied. - The values above may seem a bit strange, but here are the guiding - principles: - \list - \li QString allocates 4 characters at a time until it reaches size 20. - \li From 20 to 4084, it advances by doubling the size each time. - More precisely, it advances to the next power of two, minus - 12. (Some memory allocators perform worst when requested exact - powers of two, because they use a few bytes per block for - book-keeping.) - \li From 4084 on, it advances by blocks of 2048 characters (4096 - bytes). This makes sense because modern operating systems - don't copy the entire data when reallocating a buffer; the - physical memory pages are simply reordered, and only the data - on the first and last pages actually needs to be copied. - \endlist + The values above may seem a bit strange, but there is a guiding + principle. It advances by doubling the size each time. + More precisely, it advances to the next power of two, minus + 16 bytes. 16 bytes corresponds to eight characters, as QString + uses UTF-16 internally. + + QByteArray uses the same algorithm as + QString, but 16 bytes correspond to 16 characters. - QByteArray uses more or less the same algorithm as - QString. - - QList<T> also uses that algorithm for data types that can be - moved around in memory using \c memcpy() (including the basic C++ - types, the pointer types, and Qt's \l{shared classes}) but uses a - different algorithm for data types that can only be moved by - calling the copy constructor and a destructor. Since the cost of - reallocating is higher in that case, QList<T> reduces the - number of reallocations by always doubling the memory when - running out of space. + QList<T> also uses that algorithm, but 16 bytes correspond to + 16/sizeof(T) elements. QHash<Key, T> is a totally different case. QHash's internal hash table grows by powers of two, and each time it grows, the items |