Uploaded image for project: 'Qt'
  1. Qt
  2. QTBUG-106175

Q(Multi)Hash is missing range-erase()

    XMLWordPrintable

    Details

    • Type: Suggestion
    • Status: Open
    • Priority: P2: Important
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Labels:
      None
    • Story Points:
      13
    • Sprint:
      Foundation PM Staging

      Description

      Q(Multi)Hash, unlike all other Qt containers, and unlike std::unordered_map, lacks the erase(it, it) function ("range-erase"). Currently, the only option to erase a range of items in QHash is to loop over erase(it), which, however, has algorithmic complexity problems (see QTBUG-103328), so esp. when the range consists of equivalent elements (think QMultiHash), the erase(it) loop is necessarily quadratic.

      Workaround: use removeIf() and hope for QTBUG-103328 to be fixed.

      Acceptance criteria: The following test passes and has complexity linear in N = std::distance(b, e):

      QMultiHash<int, QString> h = {
          {0, "zero"},
          {1, "one"},
          {1, "uno"},
          {2, "two"},
      };
      auto b = h.find(1);
      auto e = std::next(b);
      auto it  = h.erase(b, e);
      static_assert(std::is_same_v<decltype(it), QMultiHash<int, QString>::iterator>);
      QVERIFY(it == h.end() || it.key() == 0 || it.key() == 2);
      QVERIFY(it == h.end() || it.value() == "zero" || it.value() == "two");
      QMultiHash<int, QString> res = {{0, "zero"), {2, "two"}};
      QCOMPARE_EQ(h, res);
      

        Attachments

          Issue Links

          No reviews matched the request. Check your Options in the drop-down menu of this sections header.

            Activity

              People

              Assignee:
              cnn Qt Core & Network
              Reporter:
              mmutz Marc Mutz
              PM Owner:
              Vladimir Minenko Vladimir Minenko
              RnD Owner:
              Alex Blasche Alex Blasche
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

                Dates

                Created:
                Updated:

                  Gerrit Reviews

                  There are no open Gerrit changes