Qt: qSort без использования конструктора копирования

Насколько я понимаю, быстрая сортировка, если перетасовка членов выполняется с помощью копировального ключа, вы будете очень разочарованы тем, что O(n ln п) действительно означает. Поэтому я решил протестировать qSort с

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

и получил удар с теми

'QObject::QObject(const QObject&)' является приватным

ошибки. Насколько я могу судить, проблема начинается с метода begin(), потому что если у меня есть

list.begin();

ошибка компилятора указывает на то, что эта строка qlist.h каким-то образом пытается использовать копию ctor:

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

Я понимаю, что могу сделать указатели на элементы списка, а затем реализовать lessThan, но это не очень удобно для этой кодовой базы. Итак, как я могу избежать использования copy ctor, когда qSort работает со списком объектов?

Я использую Qt 4.8 в 64-битной и 32-битной Linux.


c++ qt sorting qt4 qt4.8
person Opux    schedule 03.08.2017    source источник
comment
Я не использую qt, но вы можете настроить набор индексов, пронумерованных от 0 до максимального количества элементов - 1. Затем вы сортируете индексы вместо списка и используете их для ссылки на данные.   -  person PaulMcKenzie    schedule 03.08.2017
comment
@PaulMcKenzie Это лучше, чем использование указателей?   -  person Opux    schedule 03.08.2017
comment
Да, это лучше, чем указатели, так как ему не нужны указатели. Я мог бы опубликовать ответ, но он будет ориентирован на использование std::sort и vector, а не Qt (но я полагаю, что тот же принцип будет действовать).   -  person PaulMcKenzie    schedule 03.08.2017
comment
В документации сказано, что требуется, чтобы тип элемента реализовывал оператор‹(). QObject не реализует это. Я не думаю, что это проблема честного копирования. Можете ли вы предоставить минимальный, но полный пример и опубликовать полное сообщение об ошибке?   -  person skypjack    schedule 04.08.2017

Ответы (2)


arrow_upward
1
arrow_downward

Я попробую это, так как я не пользователь Qt.

В общем, если вам нужно отсортировать список объектов, которые нельзя скопировать, или если аспект копирования является дорогостоящим, одним из обходных путей является сортировка списка индексов вместо данных, а после завершения сортировки используйте список индексов. для доступа к данным.

Согласно документам для Qt qSort, что-то вроде этого может работать с использованием описанного выше метода:

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];});
}

Как только это будет сделано, вы получите доступ к отсортированному контейнеру myList следующим образом:

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

Примечание. Я предполагаю, что qSort принимает лямбда-функцию в качестве третьего аргумента. Если есть проблемы, вы можете использовать объект функции.

person PaulMcKenzie    schedule 03.08.2017
comment
По сути, это то же самое, что и сортировка указателей, причем указатели являются индексами, за исключением того, что с указателями меньше косвенности. - person MofX; 04.08.2017

arrow_upward
0
arrow_downward

QObject не имеет ни конструктора копирования, ни оператора присваивания. Это по дизайну.

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

Таким образом, вы просто не можете qSort контейнер с QObject или производными классами, по крайней мере, не в C++ до C++11. Вы можете попробовать включить поддержку С++ 11 (или выше) в своем компиляторе (и убедиться, что ваши библиотеки Qt тоже скомпилированы с этим); если люди Qt так же хороши, как обычно, в этом случае они используют move-semantics.

В противном случае использование указателей или, возможно, одного из классов указателей Qt, таких как QSharedPointer, было бы допустимым способом. И вам в любом случае понадобится оператор или функция lessThan, если вы не хотите, чтобы порядок был по адресу памяти.

person Murphy    schedule 12.08.2017