How to reverse a QList?

Question

I see qCopy, and qCopybackward but neither seems to let me make a copy in reverse order. qCopybackward only copies it in reverse order, but keeps the darn elements in the same order! All I want to do is return a copy of the list in reverse order. There has to be a function for that, right?

Answer 1

As of Qt 5.14 (circa 2020), QList provides a constructor that takes iterators, so you can just construct a reversed copy of the list with the reverse iterators of the source:

QList<int> backwards(forwards.rbegin(), forwards.rend());

Or if you want to be able to inline it, more generically (replace QList<I> with just I if you want to be super duper generic):

template <typename I> QList<I> reversed (const QList<I> &forwards) {
    return QList<I>(forwards.rbegin(), forwards.rend());
}

Which lets you do fun one-liners with temporaries like:

QString badDay = "reporter covers whale exploding";
QString worseDay = reversed(badDay.split(' ')).join(' ');

Answer 2

Reverse your QList with a single line:

for(int k = 0; k < (list.size()/2); k++) list.swap(k,list.size()-(1+k));

Answer 3

For standard library lists it would look like this

std::list<X> result;
std::copy(list.rbegin(), list.rend(), std::back_inserter(result));

Unfortunately, Qt doesn't have rbegin and rend functions that return reverse iterators (the ones that go from the end of the container to its begnning). You may write them, or you can just write copying function on your own -- reversing a list is a nice excersize. Or you can note that QList is actually an array, what makes writing such a function trivial. Or you can convert the list to std::list, and use rbegin and rend. Choose whatever you like.

Answer 4

[Rewrite from original]

It's not clear if OP wants to know "How [do I] reverse a QList?" or actually wants a reversed copy. User mmutz gave the correct answer for a reversed copy, but if you just want to reverse the QList in place, there's this:

#include <algorithm>

And then

std::reverse(list.begin(), list.end());

Or in C++11:

std::reverse(std::begin(list), std::end(list));

The beauty of the C++ standard library (and templates in general) is that the algorithms and containers are separate. At first it may seem annoying that the standard containers (and to a lesser extent the Qt containers) don't have convenience functions like list.reverse(), but consider the alternatives: Which is more elegant: Provide reverse() methods for all containers, or define a standard interface for all containers that allow bidirectional iteration and provide one reverse() implementation that works for all containers that support bidirectional iteration?

To illustrate why this is an elegant approach, consider the answers to some similar questions:

"How do you reverse a std::vector<int>?":

std::reverse(std::begin(vec), std::end(vec));

"How do you reverse a std::deque<int>?":

std::reverse(std::begin(deq), std::end(deq));

What about portions of the container?

"How do you reverse the first seven elements of a QList?": Even if the QList authors had given us a convenience .reverse() method, they probably wouldn't have given us this functionality, but here it is:

if (list.size() >= 7) {
    std::reverse(std::begin(list), std::next(std::begin(list), 7));
} 

But it gets better: Because the iterator interface is the same as C pointer syntax, and because C++11 added the free std::begin() and std::end functions, you can do these:

"How do you reverse an array float x[10]?":

std::reverse(std::begin(x), std::end(x));

or pre C++11:

std::reverse(x, x + sizeof(x) / sizeof(x[0])); 

(That is the ugliness that std::end() hides for us.)

Let's go on: "How do you reverse a buffer float* x of size n?":

std::reverse(x, x + n);

"How do you reverse a null-terminated string char* s?":

std::reverse(s, s + strlen(s));

"How do you reverse a not-necessarily-null-terminated string char* s in a buffer of size n?":

std::reverse(s, std::find(s, s + n, '\0'));

Note that std::reverse uses swap() so even this will perform pretty much as well as it possibly could:

QList<QList<int> > bigListOfBigLists;
....
std::reverse(std::begin(bigListOfBigLists), std::end(bigListOfBigLists));

Also note that these should all perform as well as a hand-written loop since, when possible, the compiler will turn these into pointer arithmetic. Also, you can't cleanly write a reusable, generic, high-performance reverse function like this C.

Answer 5

You can use the Java style iterator. Complete example here (http://doc.qt.digia.com/3.2/collection.html). Look for the word "reverse".

QList<int> list; // initial list

list << 1;
list << 2;
list << 3;

QList<int> rlist; // reverse list+

QListIterator<int> it(list);
while (it.hasPrevious()) {
    rlist << it.previous();
}

Answer 6

If you don't like the QTL, just use the STL. They might not have a Qt-ish API, but the STL API is rock-stable :) That said, qCopyBackward is just std::copy_backward, so at least they're consistent.

Answering your question:

template <typename T>
QList<T> reversed( const QList<T> & in ) {
    QList<T> result;
    result.reserve( in.size() ); // reserve is new in Qt 4.7
    std::reverse_copy( in.begin(), in.end(), std::back_inserter( result ) );
    return result;
}

EDIT 2015-07-21: Obviously (or maybe not), if you want a one-liner (and people seem to prefer that, looking at the relative upvotes of different answers after five years) and you have a non-const list the above collapses to

std::reverse(list.begin(), list.end());

But I guess the index fiddling stuff is better for job security :)

Answer 7

@Marc Jentsch's answer is good. And if you want to get an additional 30% performance boost you can change his one-liner to:

for(int k=0, s=list.size(), max=(s/2); k<max; k++) list.swap(k,s-(1+k));

One a ThinkPad W520 with a QList of 10 million QTimers I got these numbers:

• reversing list stack overflow took 194 ms
• reversing list stack overflow with max and size took 136 ms

The boost is a result of

• the expression (list.size()/2) being calculated only once when initializing the loop and not after every step
• the expression list.size() in swap() is called only once when initializing the loop and not after every step

Answer 8

Reversing a QList is going to be O(n) however you do it, since QList isn't guaranteed to have its data stored contiguously in memory (unlike QVector). You might consider just traversing the list in backwards order where you need to, or use something like a QStack which lets you retrieve the elements in the opposite order they were added.