Qt: qSort without using the copy constructor

Question

As I understand the quicksort, if the shuffling of the members is done with the copy ctor, you're going to be pretty disappointed by what O(n ln n) really means. So I decided to test qSort with

QList<QObject> mylist;   //Yes, I know this isn't feasible, I just wanted to find where the copy ctor is being used
qSort(list);

and got hit with those

'QObject::QObject(const QObject&)' is private

errors. From what I can tell, the problem begins with the begin() method, because if I have

list.begin();

the compiler error indicates that this qlist.h line is somehow trying to use the copy ctor:

inline void detach() { if (d->ref != 1) detach_helper(); }

I realize I could make the list's members pointers, then implement the lessThan function, but that's not very convenient for this code base. So how can I avoid using the copy ctor when qSort operates on a list of objects?

I'm using Qt 4.8 on Linux 64-bit and 32-bit.

I don't use qt, but you could set up a set of indices numbered from 0 to the max number of items - 1. Then you sort the indices instead of your list and use that to reference the data. — PaulMcKenzie, Aug 03 '17 at 17:19
Yes it is "better" than pointers, since it doesn't need pointers. I could post an answer, but it will be geared toward using `std::sort` and `vector`, not Qt (but the same principle would hold I would believe). — PaulMcKenzie, Aug 03 '17 at 17:25
Documentation says that it _requires the item type to implement operator<()_. QObject doesn't implement it. I don't think that's a problem of copying honestly. Can you provide a minimal, yet complete example and post the full error message? — skypjack, Aug 03 '17 at 21:25

score 1 · Answer 1 · answered Aug 03 '17 at 17:48

I will take a stab at this, since I am not a Qt user.

In general, if you need to sort a list of objects that cannot be copied, or if the copying aspect is expensive, one workaround is to sort a list of indices instead of the data, and after the sorting is done, use the index list to access the data.

According to the docs for Qt's qSort, something like this may work using the method above:

int doSomething()
{
    QList<QObject> myList;
    //...
    QVector<int> index(myList.size());
    for (int i = 0; i < myList.size(); ++i ) index[i] = i;
    qSort(index.begin(), index.end(), [](int n1, int n2) { return myList[n1] < myList[n2];});
}

Once this is done, you access the sorted myList container thusly:

myList[index[0]]; // First item
myList[index[1]]; // second item
...

Note: I am assuming that qSort accepts a lambda function as the third argument. If there are issues, you can use a function object.

That is essentially the same as sorting pointers, with the pointers being indices, except that there is less indirection with pointers. — MofX, Aug 04 '17 at 05:53

Murphy · Answer 2 · 2017-08-13T00:10:33.877

QObject has neither a copy constructor nor an assignment operator. This is by design.

http://doc.qt.io/qt-4.8/qobject.html#no-copy-constructor-or-assignment-operator

So you just can't qSort a container with QObjects or derived classes, at least not in C++ before C++11. You could try switching on C++11 support (or higher) in your compiler (and make sure your Qt libs are compiled with that, too); if the Qt folks are as good as usual they're using move semantics in this case.

Else using pointers or perhaps one of the Qt pointer classes like QSharedPointer would be a valid way to go. And you'll need a lessThan operator or function anyway if you don't want the order to be by memory address.

Qt: qSort without using the copy constructor

2 Answers2