summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qflatmap_p.h
Commit message (Collapse)AuthorAgeFilesLines
* QVarLengthArray: give the default Prealloc a nameMarc Mutz2024-02-141-1/+3
| | | | | | | | | | | ... and use that in QVarLengthFlatMap's definition in lieu of a magic constant. Amends d4611ba3a5b46ee790e6c790ef6c3d771d3507ee. Pick-to: 6.7 6.6 6.5 6.2 Change-Id: I369f31b643789075ef6c14669b8b794ed0b3bbb1 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* Resolve symbol ambiguity when building with Unity BuildAmir Masoud Abdol2023-05-041-2/+5
| | | | | | | | | | | | | | | In unity build, we may get `error: reference to 'detail' is ambiguous` between the `detail` namespace defined in `qpropertyprivate.h`, and `qflatmap_p.h`. For now, this causes an issue during the compilation of `qcalendar.cpp` and it may occur in other places where qflatmap is included. Pick-to: 6.5 Task-number: QTBUG-109394 Change-Id: Ie4bbb66543d26a5db58488e924333d98ce0adebf Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
* Add a centralized dependent_false typeGiuseppe D'Angelo2022-12-061-2/+1
| | | | | | | | | | | | | | | | The main use case is to static_assert on it at the end of a if constexpr / else if constexpr chain. See P2593 for a discussion about why this is pretty much the only "allowed" way of doing so, short of running into IFNDR. I'm actually adding two versions: one for TTP and one for NTTP, as Qt code uses both. Apply it in QFlatMap. Change-Id: Iaff97e350784683d0c3994020b1352d5188931d6 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QFlatMap: make nested mock_object SCARYMarc Mutz2022-11-191-15/+19
| | | | | | | | | | | | | Swap the definition of the nested mock_object out of the QFlatMap body into a namespace scope and replace it with a template alias. This way, there's _one_ mock_object<U> for every U, not one for every QFlatMap<K, V, Comp, KeyC, ValueC>::mock_object<U> ("SCARY"). Should reduce compile times, but I didn't measure. Change-Id: I37f7413a49d0424e06ef4e78d65dea5962599e79 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QFlatMap: fix a declval usageGiuseppe D'Angelo2022-11-081-1/+1
| | | | | | | | The comparator object is allowed to reject rvalues. Use a const lvalue ref. Change-Id: Id4ab5e094f3a0f4e6b2549ee5d3105d93faf1d14 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Use SPDX license identifiersLucie Gérard2022-05-161-38/+2
| | | | | | | | | | | | | Replace the current license disclaimer in files by a SPDX-License-Identifier. Files that have to be modified by hand are modified. License files are organized under LICENSES directory. Task-number: QTBUG-67283 Change-Id: Id880c92784c40f3bbde861c0d93f58151c18b9f1 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: make insertion STL-compatibleMarc Mutz2022-03-161-23/+51
| | | | | | | | | | | | | | | | | | | | | | That is, insert() doesn't overwrite an existing entry, and range insert inserts the first of equivalent keys' values, not the last. This allowed this author to optimize the implementation of makeUnique() to a O(N) algorithm (was: O(N²)). Said optimization would have been possible with the old semantics, too, but I wrote the algorithm first and only then noticed the broken insert() behavior is present on QFlatMap, too, so I decided not to let good code go to waste and to fix both problems at the same time. In order to give users a hint of the changed semantics, make the new API opt-in until Qt 6.5, so Qt 6.4 ships with the both the old and the new semantics disabled, where they contradict. Fixes: QTBUG-100092 Change-Id: Ic96d8bfe6bed9068dbe8c0d7171bd8921050fd95 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QFlatMap: fix warning -Wunused-but-set-variable (GCC) in remove_if()Marc Mutz2022-03-111-1/+1
| | | | | | | | Amends 6f5c78fe3d445f1c6c8738f9cedb9dbd847645fa. Change-Id: I01a474f8ccb9de7d7b76a33a950542e38edc78e4 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QFlatMap: add remove_ifMarc Mutz2022-03-031-0/+75
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The existing API of QFlatMap did not allow efficient removal of elements: - std::remove_if does not apply, because it works by moving elements back in the range onto those that need to be removed, which doesn't work in flat_map's case, because, like for all associative containers, the key in value_type is const. - The node-based erase-loop (over it = cond ? c.erase(it) : std::next(it)) works, but, unlike in traditional associative containers, is quadratic, because flat_map::erase is a linear operation. According to Stepanov's principle of Efficient Computational Basis (Elements of Programming, Section 1.4), we're therefore missing API. Add it. I couldn't make up my mind about the calling convention for the predicate and, despite having authored a merged paper about erase_if, can never remember what the predicate is supposed to take, so be fancy and accept all: (*it), (it.key(), it.value()), (it.key()). This means that unary predicates can either not be generic or must be properly constrained to distinguish between pair<const K, V> and K, but that's not necessarily a bad thing. There's no reason to supply a Qt-ified removeIf on top of the standard name, because this is private API and doubling the names would do nothing except double the testing overhead. Fixes: QTBUG-100983 Change-Id: I12545058958fc5d620baa770f92193c8de8b2d26 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Ulf Hermann <ulf.hermann@qt.io> Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
* Make sure all qtbase private headers include at least one otherThiago Macieira2022-02-241-1/+2
| | | | | | | | | | See script in qtbase/util/includeprivate for the rules. Since these files are being touched anyway, I also ran the updatecopyright.pl script too. Change-Id: Ib056b47dde3341ef9a52ffff13ef677e471674b6 Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QFlatMap: temporarily disable some codeMarc Mutz2022-02-141-0/+8
| | | | | | | | | | | | | | ... which implements or assumes something about the broken^Wnon-STL-compliant insertion behavior. Once this has integrated into all module dependencies, we can re-implement these APIs using STL-compatible semantics. Task-number: QTBUG-100092 Change-Id: I54f4f5ce7addd9543866d2c399f48aff50983b88 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QFlatMap: fix is_transparent detectionMarc Mutz2022-01-301-1/+1
| | | | | | | | | | | | | | Add a level of indirection via void_t such that struct is_transparent {}; works, and not just using is_transparent = <unspecified>; Pick-to: 6.3 Change-Id: I3ca2af6a07e6989dc95abc10fb2d0078a5269e5b Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: remove binary_find()Marc Mutz2022-01-301-50/+28
| | | | | | | | | | | The private binary_find() overload set is literally identical to the public find() one, so cut out the middle man. One less level of function templates to compile. Pick-to: 6.3 Change-Id: Ia7b248d883b7bcff39c4f7b470d2567970572885 Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: add full is_transparent support [3/3]: add overloadsMarc Mutz2022-01-301-0/+62
| | | | | | | | | | | Now add the missing overloads for mixed-type lookups, supported by is_transparent Compare objects. Pick-to: 6.3 Change-Id: Ib588b6a4f733d5d9908c8c7d7c209df6e7bd6674 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: add full is_transparent support [2/3]: shuffle functionsMarc Mutz2022-01-291-23/+19
| | | | | | | | | | | Move the do_{remove,take}() functions into the private section, cleaning up after the previous step. Pick-to: 6.3 Change-Id: I3325336458b34e7f376b42bfe68355d93ff4ce70 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: add full is_transparent support [1/3]: split functionsMarc Mutz2022-01-291-2/+14
| | | | | | | | | | | | | | | | | | Extract Methods do_foo(iterator) from their respective foo(Key) methods. This is done in order to separate the common code from the code that will differ in the is_transparent overloads. Leave the function bodies where they previously appeared, for easier reviewing. Pick-to: 6.3 Change-Id: I49f41f9121a047df696f39daeaa0a9da6a16dddb Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: implement mutable op[] via try_emplace()Marc Mutz2022-01-291-12/+2
| | | | | | | | | De-duplicates code. Pick-to: 6.3 Change-Id: Id7841a0717cd66bd56d489e6d2630e9eeb284316 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: use erase() in remove()Marc Mutz2022-01-281-2/+1
| | | | | | | | | | De-duplicates code. Pick-to: 6.3 6.2 Change-Id: I95d3d6f57c2f3716b8f3f549d1cc2a02cde9e996 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: replace manual const_cast<>s with std::as_constMarc Mutz2022-01-281-9/+7
| | | | | | | | | | | | | | Shorter, because it doesn't need to name the type. As a drive-by, replace all remaining uses of the private full_map_t alias with 'QFlatMap', the class name, which, also in templates, refers to the class, not the class template. Pick-to: 6.3 6.2 Change-Id: Ie3bada43d9d28a84543e8baa8a36c522dff80b9e Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: avoid post-(in|de)crement on iteratorsMarc Mutz2022-01-271-4/+4
| | | | | | | | | | | | | | Generic code needs to avoid post-increment and -decrement, because they're less efficient than pre-increment and -decrement when implemented in class types as opposed to scalars (extra copy necessary). Use the common pattern of implementing post- using pre-increment. Pick-to: 6.3 Change-Id: Ida38df04c6c6f877453e5b3a1983457cc7f63f11 Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io> Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* QFlatMap: don't sort already ordered dataMarc Mutz2022-01-141-1/+1
| | | | | | | Pick-to: 6.3 6.2 Change-Id: Id7ab2fe09c01500ca5bd23751ba29ed1394bb9b6 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: re-implement insert() via insert_or_assign()Marc Mutz2022-01-121-33/+4
| | | | | | | | Avoids code duplication. Pick-to: 6.3 6.2 Change-Id: Ic69e46108baf97a0dc9215866d6c707136ee40b2 Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: add insert_or_assignMarc Mutz2022-01-121-0/+18
| | | | | | | | | | | | | | | | This does exactly what insert() on Qt associative containers does, but allows to express the intent of using the STL-incompatible Qt insert() semantics, in an STL-compatible way, instead of leaving the reader of the code wondering what semantics are expected. This is part of a very-long-term goal of fixing Qt associative container's insert() behavior, in which QFlatMap, being an affected, but private-API type, is used for proof-of-concept purposes. Task-number: QTBUG-99651 Pick-to: 6.3 6.2 Change-Id: I69010285438259918aef659d3235180c1b5be696 Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: add an alias for using QVarLengthArraysMarc Mutz2022-01-121-0/+3
| | | | | | | | | | ... in an attempt to foster the use of this data structure by making it less onerous to spell. Pick-to: 6.3 6.2 Change-Id: Ib9d17029c75278edde6ba90f65f68af179a6d230 Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QFlatMap: add try_emplace (w/o hint)Marc Mutz2022-01-121-0/+24
| | | | | | | | | | | | | | | | | | | | | | QFlatMap, like its public brethren, features the broken Qt-style insert() behavior (what the STL calls insert_or_assign()), which makes its insert() unusable for actual STL-style insert() work, with no replacement except the size-check-and-index-operator trick: const auto oldSize = c.size(); auto &e = c[key]; if (c.size() != oldSize) { // inserted } Even though QFlatMap::insert() appears to return the correct info, it's useless, because the old value has been assigned over by the time insert() returns. Pick-to: 6.3 6.2 Change-Id: If4173c42523a128dfd22ab496dde0089ba73f41c Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: optimize construction from existing containersMarc Mutz2022-01-121-14/+7
| | | | | | | | | Use {copy,move} ctors instead of default-ctor, followed by (move|copy)-assignment. Pick-to: 6.3 6.2 Change-Id: Id2fd53050cd353a9374fd065ac25d753d42d1be9 Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: fix pointless reallocations on repeated range-insert()sMarc Mutz2022-01-121-2/+0
| | | | | | | | | | | | When looping over range-insert(), the repeated shrink_to_fit() calls would cause cause reserved (or geometrically-grown) capacity to be shed, breaking the underlying container's growth strategy. Fix by not shedding excess capacity. Pick-to: 6.3 6.2 Change-Id: I10915a06fc9442039c192486a55e48083da7c839 Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* QFlatMap: fix const iterator APIMarc Mutz2022-01-071-8/+8
| | | | | | | | Iterators model pointer, so const must be shallow. Pick-to: 6.3 6.2 Change-Id: I90494c98762f1494efcca4965ee739540333f5d7 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QFlatMap: fix mixed rvalue/lvalue insert overloadsMarc Mutz2022-01-071-2/+2
| | | | | | | | They never worked. Pick-to: 6.3 6.2 Change-Id: I9a15c848416419823f28ea580248fbe93a4365dd Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io>
* Don't allow storing types that throw in the destructor in our containersLars Knoll2020-11-171-0/+2
| | | | | | | | | | | | | | | | | | | | | | Types that throw in their destructors are strongly discouraged in C++, and even the STL doesn't define what happens if such types are stored in their containers. Make this more explicit for Qt and disallow storing those types in our containers. This will hopefully preempty any potential future bug reports about us not handling such a case. It also helps simplify some code in QList and other cases and makes it possible to explicitly mark more methods as noexcept. Some care needs to be taken where to add the static asserts, so that we don't disallow forward declarations of types stored in containers. Place the static assert into the destructor of the container where possible or otherwise into the templated d-pointer. Change-Id: If3aa40888f668d0f1b6c6b3ad4862b169d31280e Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Use QList instead of QVector in corelibJarek Kobus2020-06-251-6/+4
| | | | | | | | | | Applied to headers only. Source file to be changed separately. Omitted statemachine for now to avoid conflicts. Omitted qmetatype.h for now - to be handled later. Task-number: QTBUG-84469 Change-Id: I317376037a62467c313467d92955ad0b7473aa97 Reviewed-by: Sona Kurazyan <sona.kurazyan@qt.io>
* QFlatMap: explicitly include <vector>Vitaly Fanaskov2020-03-061-0/+1
| | | | | | | | | Without this include, it fails to compile the following line on some systems: "std::vector<bool> done(s)", because only a forward declaration is available. Change-Id: I6eac4b7f69dda16e181043eb707f970b21b2dfef Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* Long live QFlatMap!Joerg Bornemann2020-01-021-0/+982
Add a light-weight associative container, API-wise very similar to QMap, that's based on two sorted continuous containers (QVector by default). The class is internal for now. Change-Id: Ife12576c4abb39a3ea2acb0a1ba0faca91b3a4c5 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-26 08:40:50 +0000