summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qmap.h
Commit message (Collapse)AuthorAgeFilesLines
* Replace Q_NULLPTR with nullptr where possibleKevin Funk2017-09-191-23/+23
| | | | | | | | | | | | | Remaining uses of Q_NULLPTR are in: src/corelib/global/qcompilerdetection.h (definition and documentation of Q_NULLPTR) tests/manual/qcursor/qcursorhighdpi/main.cpp (a test executable compilable both under Qt4 and Qt5) Change-Id: If6b074d91486e9b784138f4514f5c6d072acda9a Reviewed-by: Ville Voutilainen <ville.voutilainen@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* Merge remote-tracking branch 'origin/5.9' into devSimon Hausmann2017-07-191-3/+3
|\ | | | | | | | | | | | | | | Conflicts: src/corelib/io/qwindowspipewriter.cpp src/widgets/styles/qcommonstyle.cpp Change-Id: I0d33efdc4dc256e234abc490a18ccda72cd1d9e6
| * Add missing constexpr specifier to two iteratorsMårten Nordheim2017-07-141-3/+3
| | | | | | | | | | | | | | | | | | | | | | The classes themselves and their equality operators are used in constexpr functions/ctors (in QKeyValueIterator) so Visual Studio 2017 expects them to be marked constexpr as well. Currently this causes a compilation error when instantiating a QKeyValueIterator using either of these iterators. Change-Id: I2e3eeaf3b3f11f381a63875e6575dfd82fe56fcb Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* | Qt containers: use std::move in take*() methodsMarc Mutz2017-05-231-1/+1
| | | | | | | | | | | | | | Move the objects out of the data structure to avoid needless copies. Change-Id: I1a69fccc431e040b229d6ea9ded0e041c208c861 Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* | Implement key-value iteratorSamuel Gaist2017-05-051-0/+8
|/ | | | | | | | | | | | | This patch implements an iterator that returns a pair containing both the key and the value of an entry in QHash/QMap. [ChangeLog][QtCore][Containers] Added an stl-like iterator to go through QHash/QMap returning both the key and the value of the element pointed to. That lets QHash/QMap interoperate better with stl's algorithms like std::set_union. Change-Id: Idbf8a8581510b3493648c34ab04c556de9fa4aa7 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* Merge remote-tracking branch 'origin/5.8' into 5.9Liang Qi2017-04-121-2/+4
|\ | | | | | | Change-Id: I3bd83a839b16822035ed56a5cffe77bd6bc3f08d
| * QMap: fix UB (invalid cast) in QMapData::end()Thiago Macieira2017-04-091-2/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The end() pointer, like in all other containers, is a sentinel value that must never be dereferenced. But unlike array-based containers, end() in QMap is not "last element plus one", but points to a base class of Node, not a full Node. Therefore, the casting from QMapNodeBase to QMapNode must not be a static_cast, reinterpret_cast is required. libstdc++-v3's red-black tree had the exact same problem: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734 Change-Id: I43f05fedf0b44314a2dafffd14b33697861ae589 Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
* | QMap, QHash: make key_iterator satisfy the DefaultConstructible conceptAnton Kudryavtsev2017-03-201-0/+1
| | | | | | | | | | Change-Id: Ifc3f481ddb902b26c217516412c93a4a39a32b1c Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
* | Use std::enable_if instead of QEnableIfAlexander Volkov2017-01-271-2/+2
|/ | | | | | Change-Id: Ideca8283141484cb6da47c50333f5c96e416f082 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* QMap: use std::less for defining an order between pointersGiuseppe D'Angelo2016-12-121-7/+4
| | | | | | | | | | | | | Reinterpret_cast()ing a pointer to a suitably sized integer is not guaranteed to always give the same result for the same pointer (!). Therefore the resulting integers are not comparable in a meaningful way. std::less is supposed to be used to compare arbitrary pointers, so use it. (Hopefully and reasonably, under the hood std::less does exactly what we were doing, so this isn't BiC.) Change-Id: I9960b3d6e35657fe7a25b842054f5d338280e850 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Replace custom type traits with std one'sKai Koehne2016-11-081-4/+3
| | | | | | | | | | | | | | | | | | Remove most type traits from qtypetraits.h, but keep the custom implementation of is_signed/is_unsigned. This gets rid of BSD-3 licensed code from Google in a public header (hugh!). The custom implementations for is_signed/is_unsigned are kept because the implementations in gcc's standard headers do not work as we expect for enums - both is_signed and is_unsigned always returns false there - see also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59027 [ChangeLog][QtCore][General] Qt now relies on type traits from the C++ standard library. Change-Id: I3f2188b46949f04ca4482a6ac9afd3482103f0e1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Merge remote-tracking branch 'origin/5.6' into 5.7Liang Qi2016-05-191-1/+1
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Conflicts: configure src/3rdparty/angle/src/libANGLE/renderer/d3d/d3d11/Renderer11.cpp src/network/access/qnetworkaccessmanager.cpp src/plugins/platforms/cocoa/qcocoacolordialoghelper.mm src/plugins/platforms/eglfs/deviceintegration/eglfs_kms/qeglfskmsgbmcursor.cpp src/plugins/platforms/eglfs/deviceintegration/eglfs_kms/qeglfskmsgbmcursor.h src/widgets/widgets/qlineedit_p.cpp src/widgets/widgets/qlineedit_p.h src/winmain/winmain.pro tests/auto/corelib/io/qstorageinfo/tst_qstorageinfo.cpp tests/auto/dbus/qdbusconnection/tst_qdbusconnection.cpp tests/auto/dbus/qdbusconnection/tst_qdbusconnection.h tests/auto/testlib/selftests/expected_cmptest.teamcity tests/auto/testlib/selftests/expected_cmptest.txt tests/auto/widgets/itemviews/qtableview/tst_qtableview.cpp tools/configure/configureapp.cpp Change-Id: Ib9997b0d0f91946e4081d36c0c6b696c5c983b2a
| * Fix Clang -Wexpansion-to-defined warning by deprecating QT_SUPPORTSThiago Macieira2016-05-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The C and C++ standards say it's undefined whether the preprocessor supports macros that expand to defined() will operate as an ifdef. Clang 3.9 started complaining about that fact. One solution was to change QT_SUPPORTS to check for zero or one, which means we need to change the #defines QT_NO_xxx to #define QT_NO_xxx 1. The C standard says we don't need to #define to 0, as an unknown token is interpreted as zero. However, that might produce a warning (GCC with -Wundef), so changing the macro this way is not recommended. Instead, we deprecate the macro and replace the uses with #ifdef/ndef. Change-Id: Id75834dab9ed466e94c7ffff1444874d5680b96a Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* | Merge remote-tracking branch 'origin/5.6' into 5.7Liang Qi2016-04-251-0/+4
|\| | | | | | | | | | | | | | | | | | | | | | | | | Conflicts: config.tests/unix/compile.test configure src/android/jar/src/org/qtproject/qt5/android/QtMessageDialogHelper.java src/corelib/global/qglobal.cpp src/widgets/kernel/qapplication.cpp src/widgets/styles/qwindowsvistastyle.cpp tests/auto/corelib/kernel/qobject/tst_qobject.cpp Change-Id: I067083f34e5290aa5f7565e40c30a069cc37b83a
| * Work around Clang false-positive warning on returning default parametersThiago Macieira2016-04-131-0/+4
| | | | | | | | | | | | | | | | | | | | | | Clang 3.8 and Apple Clang 7.x seem to think that the parameter is a temporary. See https://llvm.org/bugs/show_bug.cgi?id=26396 Task-number: QTBUG-52134 Change-Id: Id75834dab9ed466e94c7ffff1444b6f2424d7fb7 Reviewed-by: Jake Petroules <jake.petroules@theqtcompany.com>
* | QtCore: use printf-style qWarning/qDebug where possible (I)Marc Mutz2016-03-111-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The printf-style version of QDebug expands to a lot less code than the std::ostream-style version. Of course, you pay in type safety (but compilers warn about it these days), you cannot stream complex Qt types and streaming QStrings is awkward, but in many cases you actually improve on readability. But the main reason is that something that's not supposed to be executed under normal operation has no business bloating executable code size. This is not an attempt at converting all qWarnings() to printf-style, only the low-hanging fruit. In this first part, replace qWarning() << "" with qWarning("..."). Saves ~750b in text size on optimized GCC 5.3 AMD64 builds. Change-Id: I8bf3e46cd5a6b2cae0ceb3e355a50f61925c63d3 Reviewed-by: Kai Koehne <kai.koehne@theqtcompany.com>
* | Updated license headersJani Heikkinen2016-01-151-14/+20
|/ | | | | | | | | | | From Qt 5.7 -> LGPL v2.1 isn't an option anymore, see http://blog.qt.io/blog/2016/01/13/new-agreement-with-the-kde-free-qt-foundation/ Updated license headers to use new LGPL header instead of LGPL21 one (in those files which will be under LGPL v3) Change-Id: I046ec3e47b1876cd7b4b0353a576b352e3a946d9 Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>
* Make container move semantics consistentMarc Mutz2015-10-071-6/+6
| | | | | | | | | | | | | | | Make all containers (excepting QVarLengthArray) - nothrow default-constructible - nothrow move-constructible - nothrow move-assignable - nothrow swappable [ChangeLog][QtCore] All containers (with the exception of QVarLengthArray, but including QSharedPointer) are now nothrow_default_constructible, nothrow_move_constructible, nothrow_move_assignable, and nothrow-swappable. Change-Id: I12138d262f9f7f600f0e1218137da208c12e7c0a Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMulti(Map|Hash): add move ctor from Q(Map|Hash)Marc Mutz2015-10-071-0/+3
| | | | | | | There was a copy ctor, a move ctor was missing. Change-Id: If09a4d4c74682169759eff43b298f6c77702c169 Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* Introduce QMap key iteratorsSérgio Martins2015-07-281-0/+28
| | | | | | | | | | | So we can have interoperability with algorithms. Motivated by inefficient code like qDeleteAll(map.keys()) [ChangeLog][QtCore][QMap] Added key iterators, accessible through keyBegin() and keyEnd(). Change-Id: Ieee2f9ad031e9d1e845a71447746699bbe95b96c Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
* Containers: destroy previous state on move-assignment immediatelyMarc Mutz2015-07-191-1/+1
| | | | | | | | | | | | | | | | [ChangeLog][QtCore] All generic containers (with the exception of QVarLengthArray, but including QSharedPointer) destroy the previous state as part of a move-assignment now. Previously, they would dump it into the right-hand-side object. Note that this is only true for the generic containers. Other implicitly-shared types, as well as the non-generic containers QString, QByteArray, etc. still just swap the contents with the right-hand-side object when move-assigned into, and, for performance reasons, this will not change in the forseeable future. Change-Id: I1f1c684e85400b77bd2e7fba65bde2dce6c1bdde Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@theqtcompany.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QtCore: Use Q_NULLPTR instead of 0 in all public headersMarc Mutz2015-07-011-23/+23
| | | | | | | | | This is in preparation of adding -Wzero-as-null-pointer-constant (or similar) to the headers check. Task-number: QTBUG-45291 Change-Id: I0cc388ef9faf45cbcf425ad0dc77db3060c104a8 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap: use constrained templates instead of static-ifsMarc Mutz2015-06-221-29/+25
| | | | | | | | | Avoids warnings about constant expressions in ifs. Task-number: QTBUG-46649 Change-Id: I56adf8e80091330d2e97327df7751e57411fbd70 Reviewed-by: Friedemann Kleint <Friedemann.Kleint@theqtcompany.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap: add const equal_range() overloadMarc Mutz2015-06-191-0/+10
| | | | | | | | | | ... to prevent detaching. [ChangeLog][QtCore][QMap] Added const equal_range() overload. Change-Id: I4b39abb8ad41ba6eaa8f9a9a74ed74ed10337dd3 Reviewed-by: Sérgio Martins <sergio.martins@kdab.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Update copyright headersJani Heikkinen2015-02-111-7/+7
| | | | | | | | | | | | | | | | | | Qt copyrights are now in The Qt Company, so we could update the source code headers accordingly. In the same go we should also fix the links to point to qt.io. Outdated header.LGPL removed (use header.LGPL21 instead) Old header.LGPL3 renamed to header.LGPL3-COMM to match actual licensing combination. New header.LGPL-COMM taken in the use file which were using old header.LGPL3 (src/plugins/platforms/android/extract.cpp) Added new header.LGPL3 containing Commercial + LGPLv3 + GPLv2 license combination Change-Id: I6f49b819a8a20cc4f88b794a8f6726d975e8ffbe Reviewed-by: Matti Paaso <matti.paaso@theqtcompany.com>
* Remove workarounds for RVCT compiler bugsThiago Macieira2015-01-061-18/+0
| | | | | | | | | | | | | | | This does not try to remove support for RVCT. There has been no report of it working or failing to work, so the status continues to be unknown. In particular, the inline assembly code in atomic_armv[56].h remains in place. This commit only removes workarounds for compiler bugs or bogus warnings, assuming that anyone using this compiler has updated since Qt last tried to use it for Symbian in 2011. Note also how anonymous unions are now part of the language in C++11. Change-Id: Idc4fab092beb31239eb08b7e139bce2602adae81 Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* Remove Q_NO_USING_KEYWORDThiago Macieira2014-12-201-1/+1
| | | | | | | | | | | | | | | | | | | There's a lot of code now requiring it. Any compiler that doesn't support the keyword is too old for Qt now. The last time anyone asked about this macro was for QTBUG-27393 and we don't know which compiler that was. As a necessity, this patch contains a reversal of a0c3a57aed5cde37017733e7cf5e41cc6a1174aa [ChangeLog][Compiler Specific Changes] Qt 5.5 now unconditionally uses the "using" keyword. Compilers that do not support this keyword are deprecated and will not be able to build Qt. Previous versions of Qt may or may not compile, as no testing was done to ensure it worked. Change-Id: Ief042f34aba555a095d1f342a0ee7ee9feadf42d Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@theqtcompany.com>
* Update license headers and add new license filesMatti Paaso2014-09-241-19/+11
| | | | | | | | | - Renamed LICENSE.LGPL to LICENSE.LGPLv21 - Added LICENSE.LGPLv3 - Removed LICENSE.GPL Change-Id: Iec3406e3eb3f133be549092015cefe33d259a3f2 Reviewed-by: Iikka Eklund <iikka.eklund@digia.com>
* Remove unused QMapNode{,Base}::minimumNodeThiago Macieira2014-05-281-6/+0
| | | | | | | | | | | | These functions are not used anywhere. Since the classes are not documented, we're free to remove the inline functions. The implementation of the const function in QMapNode is also bogus: it discards a const qualifier. Task-number: QTBUG-39301 Change-Id: Ib8fd10a4da4b58a62cef17017ea6127c4d964325 Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* Deprecate setSharable in Qt containersThiago Macieira2014-04-241-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | The ability to set a container to be unsharable has very little use and it costs us an extra conditional for every refcount up and possibly down. This change is a no-op for current Qt 5. It shuffles a few things around just so Qt can compile if you define QT_NO_UNSHARABLE_CONTAINERS. That is done to ease the fixing of the code in Qt 6 and to make my life easier: I'll keep that defined in my local Qt build so I can catch any misuses of this deprecated API. The newly deprecated methods are not marked QT_DEPRECATED because the bootstrapped tools wouldn't build -- they're built with QT_NO_DEPRECATED defined, which causes build errors. [ChangeLog][QtCore] The setSharable() and isSharable() functions in Qt containers has been deprecated and will be removed in Qt 6. New applications should not use this feature, while old applications that may be using this (undocumented) feature should port away from it. Discussed-on: http://lists.qt-project.org/pipermail/development/2014-February/015724.html Change-Id: I789771743dcaed6a43eccd99382f8b3ffa61e479 Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@digia.com> Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* Remove level 4 compiler warnings from MSVC.David Schulz2014-03-151-0/+9
| | | | | | | | | | Task-number: QTBUG-7233 Change-Id: I52067e3a22e98a62fd87415906e54a54ff2d6b49 Reviewed-by: Kurt Pattyn <pattyn.kurt@gmail.com> Reviewed-by: Oliver Wolff <oliver.wolff@digia.com> Reviewed-by: Joerg Bornemann <joerg.bornemann@digia.com> Reviewed-by: Dave McClelland
* QMap: don't dereference nullptr IIMarc Mutz2013-09-171-4/+4
| | | | | | | | | | | | | | | | | | | | | root(), leftNode() and rightNode() can be nullptr. These pieces of code happened to work because the first thing lowerBound() does is Node *n = this; // ... while (n) // ... But that is _after_ dereferencing nullptr, which is undefined behavior. So, check first, then deref. This is the completion of I9137bf6e21014cd68404a7e49a748910b1d768cf: all uses of root(), leftNode() and rightNode() have now been manually checked. Change-Id: I3fcb958af9362104f94d6eea9c62da2ae07f1d5e Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap: don't dereference nullptrMarc Mutz2013-09-171-5/+7
| | | | | | | | | | | | | | | | | | root(), leftNode() and rightNode() can be nullptr. These pieces of code happened to work because the first thing lowerBound() does is Node *n = this; // ... while (n) // ... But that is _after_ dereferencing nullptr, which is undefined behavior. So, check first, then deref. Change-Id: I9137bf6e21014cd68404a7e49a748910b1d768cf Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Add first/last accessors to QMapMathias Hasselmann2013-09-081-27/+35
| | | | | | | | | | | | | | | QMap explicitly sorts its entries by key value. For an ordered container it's (often?) useful to access the first or last entry, for instance to quickly compute the next key of the mapping. The first entry is easily accessible by the STL begin() method, but for accessing the last entry pretty ugly iterator arithmetics must be applied: *(end() - 1). With their first() and last() accessors the container classes QList and QVector provide a much nicer method of accessing extrema, so for consistency this syntactical sugar also should be applied to QMap. Change-Id: Ibd544acbad8c3ac16f12a1e74362207ea1694375 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Thorbjørn Lund Martsum <tmartsum@gmail.com>
* QMap - fix erase with iterator when the map is sharedThorbjørn Martsum2013-08-241-0/+21
| | | | | | | | | | | Before a call to erase on a shared instance would imply that the item was removed from the shared data (i.e all instances) This patch improves the behavior to detach and erase the item specified by the iterator (i.e same behavior as QVector) Change-Id: Ia44db84fc1388d92308bf0d2b32539ac4d53850b Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap - check if iterator arguments are valid (in debugmode)Thorbjørn Martsum2013-07-121-0/+18
| | | | | | | | | This patch adds a debug-tests in erase, insert (with hint) and insertMulti (with hint) that ensures the iterator-argument is valid (and e.g not from another map) Change-Id: I7920131bc9712543183cabf13c7603bd0e12880d Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap - add multiInsert with hintThorbjørn Martsum2013-03-061-0/+54
| | | | | | | | This provides a fast multiInsert in QMap (and a fast insert in QMultiMap) when providing a correct hint. Change-Id: I3c864c3a7842765fe63f8ecb4b54d0e8c9fd22d7 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap - add insert overload that provide a hintThorbjørn Lund Martsum2013-03-061-0/+67
| | | | | | | | This adds a fast insert on QMap when providing a correct hint. Change-Id: I256bba342932c1d4f24c6e65074e1bf47b519537 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* Remove QT_{BEGIN,END}_HEADER macro usageSergio Ahumada2013-01-291-4/+0
| | | | | | | | | | | The macro was made empty in ba3dc5f3b56d1fab6fe37fe7ae08096d7dc68bcb and is no longer necessary or used. Discussed-on: http://lists.qt-project.org/pipermail/development/2013-January/009284.html Change-Id: Id2bb2e2cabde059305d4af5f12593344ba30f001 Reviewed-by: Laszlo Papp <lpapp@kde.org> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com> Reviewed-by: hjk <hjk121@nokiamail.com>
* Added initializer list constructors for Qt associative containers.Roman Pasechnik2013-01-241-0/+19
| | | | | | | | | Affected: QSet, QMap, QMultiMap, QHash, QMultiHash. Task-number: QTBUG-25679 Change-Id: I01f3ecfbca805f4c053a75232188bd2a77fdb1f2 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com>
* Update copyright year in Digia's license headersSergio Ahumada2013-01-181-1/+1
| | | | | Change-Id: Ic804938fc352291d011800d21e549c10acac66fb Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap - improve QMap stl-map ctorThorbjørn Lund Martsum2012-10-291-1/+1
| | | | | | | | | | We can insert directly on the most left-most Node. We always enforce an insert here (unlike the insert call), but that is not a problem since the keys in a std::map are unique. Change-Id: Ib409b90ffc57a5a43dab4a4b08d34f6fdabd057f Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap 5.0 - keep track of leftmost node (BIC)Thorbjørn Lund Martsum2012-10-271-2/+6
| | | | | | | | | | | | | | | | | | | | | This suggestion keeps track of the most left node. The point is that constBegin() becomes a lot faster. That speeds up iteration a bit, and makes it O(1) to get the first element. The penalty in insert and remove is very small. On large trees it seems to be less than 1%. It should be noticed that constBegin() is a very common hint on my planned change to 5.1, and this opperation will without this patch cost 2 x log N. One when the user calls the hint with begin - and one where it is compared with begin. Other std::maps has a very fast begin(). E.g http://www.cplusplus.com/reference/stl/map/begin/ (begin with constant time) Change-Id: I221f6755aa8bd16a5189771c5bc8ae56c8ee0fb4 Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap - use hint on insert in QMap::toStdMapThorbjørn Lund Martsum2012-10-271-1/+1
| | | | | | | | | Giving the std-map a hint (normally) improves insert performance. There seems to be no reason not to provide this hint. Change-Id: I4344607ebf54574a3ae9666d87a41a3c14762361 Reviewed-by: Robin Burchell <robin+qt@viroteck.net> Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap - remove unused maximumNode() functionsThorbjørn Lund Martsum2012-10-081-4/+0
| | | | | | | | | QMap has 4 different maximumNode() functions, but they are all unused and just in the way. Change-Id: I012145cfae32898830ec95e229514d9be838ae2f Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Robin Burchell <robin+qt@viroteck.net>
* Change copyrights from Nokia to DigiaIikka Eklund2012-09-221-24/+24
| | | | | | | | Change copyrights and license headers from Nokia to Digia Change-Id: If1cc974286d29fd01ec6c19dd4719a67f4c3f00e Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Sergio Ahumada <sergio.ahumada@digia.com>
* Rename QMapData::free to destroyThiago Macieira2012-08-091-3/+3
| | | | | | | | | | | | | The convention for QMap is that "free" methods simply free memory and that "destroy" ones also run destructors of types affected. Since this function calls destroySubTree, it should be more properly called "destroy". This also gets rid of another function called simply "free" in our headers. Change-Id: I3fa621c78848ede33dd5b78428c704d0423ba4e7 Reviewed-by: Lars Knoll <lars.knoll@nokia.com>
* Remove the unnecessary comment about operator== not being necessaryThiago Macieira2012-05-311-4/+2
| | | | | | | | | | The mysterious comment was just suggesting that they weren't necessary. Turns out the comment is wrong: they are necessary for non-strict iterator modes. Task-number: QTBUG-25063 Change-Id: I20ada17035642ee656c431d6bf2152a5243cecdb Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Remove references to QT_NO_STL from QtCoreThiago Macieira2012-04-071-8/+0
| | | | | | | | QT_NO_STL is now no longer defined, so remove the conditionals and select the STL side. Change-Id: Ieedd248ae16e5a128b4ac287f850b3ebc8fb6181 Reviewed-by: João Abecasis <joao.abecasis@nokia.com>
* Rewrite QMap to use a RB treeLars Knoll2012-03-231-394/+428
| | | | | | | | | | | | | | | | | | | | QMap used to use a skiplist in Qt 4.x, which has variable sized nodes and we can thus not optimise using custom allocators. The rewrite now uses a red-black tree, and all allocations and tree operations happen in the cpp file. This will allow us to introduce custom allocation schemes in later versions of Qt. Added some more tests and a benchmark. Memory consumption of the new QMap implementation is pretty much the same as before. Performance of insertion and lookup has increased by 10-30%. iteration is slower, but still extremely fast and should not matter compared to the work usually done when iterating. Change-Id: I8796c0e4b207d01111e2ead7ae55afb464dd88f5 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 18:07:54 +0000