Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. General talk
  3. The Lounge
  4. Quiz Time! Prepending items to QVector
Forum Updated to NodeBB v4.3 + New Features

Quiz Time! Prepending items to QVector

Scheduled Pinned Locked Moved Solved The Lounge
22 Posts 12 Posters 4.5k Views 7 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • Chris KawaC Offline
    Chris KawaC Offline
    Chris Kawa
    Lifetime Qt Champion
    wrote on last edited by
    #6

    How many elements? can I use reserve? Are we talking 32 or 64 bits?
    My cheat answer would by - it depends ;)

    VRoninV 1 Reply Last reply
    0
    • jeremy_kJ Online
      jeremy_kJ Online
      jeremy_k
      wrote on last edited by
      #7

      Am I misreading the problem, or does this also need to have the initial sequence reversed prior to the append + reverse operation?

      Asking a question about code? http://eel.is/iso-c++/testcase/

      Chris KawaC 1 Reply Last reply
      0
      • jeremy_kJ jeremy_k

        Am I misreading the problem, or does this also need to have the initial sequence reversed prior to the append + reverse operation?

        Chris KawaC Offline
        Chris KawaC Offline
        Chris Kawa
        Lifetime Qt Champion
        wrote on last edited by
        #8

        @jeremy_k My understanding was that we're starting from an empty container and only need it in correct order after everything is in, otherwise you'd need to do that double reversal on each addition. I could be wrong though.

        1 Reply Last reply
        1
        • fcarneyF Offline
          fcarneyF Offline
          fcarney
          wrote on last edited by
          #9

          It depends, I think.
          I don't know, but I am putting on depends in case the answer is shocking.

          C++ is a perfectly valid school of magic.

          1 Reply Last reply
          1
          • jeremy_kJ Online
            jeremy_kJ Online
            jeremy_k
            wrote on last edited by jeremy_k
            #10

            If the container starts empty, I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post. Unless QVector has become a single linked list (edit: or the consumer demands a QVector).

            Asking a question about code? http://eel.is/iso-c++/testcase/

            1 Reply Last reply
            0
            • Kent-DorfmanK Offline
              Kent-DorfmanK Offline
              Kent-Dorfman
              wrote on last edited by Kent-Dorfman
              #11

              My knowledge base is more in line with stl containers, but making the asusmption that QVector works the same, there is implicit preallocation ie reserve(n) involved in append+reverse that probably doesn't exist with the prepend call, so it stands to reason that few memory reallocations may be necesary using append+reverse.

              but the larger issue is whether O(1) random access is needed or guaranteeed continuous element allocation...if not, the QList would be a much more efficient container.

              1 Reply Last reply
              0
              • J.HilkJ Offline
                J.HilkJ Offline
                J.Hilk
                Moderators
                wrote on last edited by
                #12

                In case you do not reserve memory for the QVector beforehand, I would say append + std::reverse is faster

                Because I think, that prepend does not reserve additional memory, compared to append(size / 2 more IIRC). So you end up with an allocation and memory move/copy on each prepend


                Be aware of the Qt Code of Conduct, when posting : https://forum.qt.io/topic/113070/qt-code-of-conduct


                Q: What's that?
                A: It's blue light.
                Q: What does it do?
                A: It turns blue.

                1 Reply Last reply
                0
                • Chris KawaC Chris Kawa

                  How many elements? can I use reserve? Are we talking 32 or 64 bits?
                  My cheat answer would by - it depends ;)

                  VRoninV Offline
                  VRoninV Offline
                  VRonin
                  wrote on last edited by
                  #13

                  How many elements?

                  The benchmark tested 10, 50, 100, 500, 1000, 5000 but turns out the answer doesn't change with size

                  can I use reserve?

                  Yes, in both cases I first called QVector::reserve

                  Are we talking 32 or 64 bits?

                  64

                  I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post.

                  Yes, this is obvious but in my use case I can't read with reverse iterator

                  or does this also need to have the initial sequence reversed prior to the append + reverse operation?

                  To make it more explicit: If I have the sequence 1, 3, 2, 5 (that I can't reverse iterate) I want the vector to store those as 5, 2, 3, 1

                  "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                  ~Napoleon Bonaparte

                  On a crusade to banish setIndexWidget() from the holy land of Qt

                  1 Reply Last reply
                  0
                  • VRoninV Offline
                    VRoninV Offline
                    VRonin
                    wrote on last edited by VRonin
                    #14

                    And the answer is:
                    In Qt5 append+std::reverse is vastly superior, In Qt6 prepend is the much faster one.

                    Qt5.PNG
                    Qt6.PNG

                    "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                    ~Napoleon Bonaparte

                    On a crusade to banish setIndexWidget() from the holy land of Qt

                    1 Reply Last reply
                    6
                    • fcarneyF Offline
                      fcarneyF Offline
                      fcarney
                      wrote on last edited by
                      #15

                      What about just starting at the end of the data first and only appending?

                      C++ is a perfectly valid school of magic.

                      VRoninV 1 Reply Last reply
                      0
                      • fcarneyF fcarney

                        What about just starting at the end of the data first and only appending?

                        VRoninV Offline
                        VRoninV Offline
                        VRonin
                        wrote on last edited by
                        #16

                        @fcarney said in Quiz Time! Prepending items to QVector:

                        What about just starting at the end of the data first and only appending?

                        I guess you mean in Qt6. In that case append is slightly better but the difference is really tiny

                        "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                        ~Napoleon Bonaparte

                        On a crusade to banish setIndexWidget() from the holy land of Qt

                        1 Reply Last reply
                        0
                        • S Offline
                          S Offline
                          SimonSchroeder
                          wrote on last edited by
                          #17

                          Is there any article about these specific changes in Qt 6 that I can read? What exactly has changed between Qt 5 and 6?

                          Christian EhrlicherC 1 Reply Last reply
                          0
                          • S SimonSchroeder

                            Is there any article about these specific changes in Qt 6 that I can read? What exactly has changed between Qt 5 and 6?

                            Christian EhrlicherC Offline
                            Christian EhrlicherC Offline
                            Christian Ehrlicher
                            Lifetime Qt Champion
                            wrote on last edited by
                            #18

                            @SimonSchroeder said in Quiz Time! Prepending items to QVector:

                            What exactly has changed between Qt 5 and 6?

                            QVector is no longer in Qt6 and an alias for QList. I would guess QList in Qt5 will also show the same fast results for prepend since QList has an optimization for this usecase since ages.

                            Qt Online Installer direct download: https://download.qt.io/official_releases/online_installers/
                            Visit the Qt Academy at https://academy.qt.io/catalog

                            1 Reply Last reply
                            2
                            • VRoninV Offline
                              VRoninV Offline
                              VRonin
                              wrote on last edited by
                              #19

                              From https://wiki.qt.io/New_Features_in_Qt_6.0

                              QVector and QList are unified. QList is updated and should be used by default when array-like behaviour is needed
                              QList, QString and QByteArray now have optimized complexity of insertion at the beginning (a.k.a. prepend)

                              "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                              ~Napoleon Bonaparte

                              On a crusade to banish setIndexWidget() from the holy land of Qt

                              1 Reply Last reply
                              0
                              • VRoninV VRonin

                                I had a case where I found myself with a loop that had to prepend items to a QVector<MyClass*> and I asked myself what would be more efficient:

                                1. repeatedly calling QVector::prepend
                                2. repeatedly calling QVector::append and then std::reverse at the end

                                I actually benchmarked it but before sharing the results let's make it a challenge.
                                The person who gets it right will be praised as holder of infinite wisdom forever.

                                Before you ask, no this is still not peak nerd!

                                kshegunovK Offline
                                kshegunovK Offline
                                kshegunov
                                Moderators
                                wrote on last edited by kshegunov
                                #20

                                @VRonin I'm late to the party, as usual ...
                                ... and also as usual I probably sound like a broken record, but what your task sounds like is actually a stack, not a vector ... ;)

                                Read and abide by the Qt Code of Conduct

                                VRoninV 1 Reply Last reply
                                2
                                • kshegunovK kshegunov

                                  @VRonin I'm late to the party, as usual ...
                                  ... and also as usual I probably sound like a broken record, but what your task sounds like is actually a stack, not a vector ... ;)

                                  VRoninV Offline
                                  VRoninV Offline
                                  VRonin
                                  wrote on last edited by VRonin
                                  #21

                                  @kshegunov said in Quiz Time! Prepending items to QVector:

                                  but what your task sounds like is actually a stack, not a vector

                                  Indeed, this was an iper-semplification of my problem to solve the academic dilemma.
                                  I agree that a stack or, as @jeremy_k already pointed out, using reverse iterators would achieve the same

                                  "La mort n'est rien, mais vivre vaincu et sans gloire, c'est mourir tous les jours"
                                  ~Napoleon Bonaparte

                                  On a crusade to banish setIndexWidget() from the holy land of Qt

                                  1 Reply Last reply
                                  2
                                  • D Offline
                                    D Offline
                                    Dixon154
                                    Banned
                                    wrote on last edited by
                                    #22
                                    This post is deleted!
                                    1 Reply Last reply
                                    0

                                    • Login

                                    • Login or register to search.
                                    • First post
                                      Last post
                                    0
                                    • Categories
                                    • Recent
                                    • Tags
                                    • Popular
                                    • Users
                                    • Groups
                                    • Search
                                    • Get Qt Extensions
                                    • Unsolved