Как отменить QList?

Question

Я вижу qCopy и qCopybackward , но ни один из них не позволяет мне сделать копию в обратном порядке. qCopybackward только копирует его в обратном порядке, но сохраняет проклятые элементы в том же порядке! Все, что я хочу сделать, это вернуть копию списка в обратном порядке. имеет функцию для этого, верно?

Answer 1

Если вам не нравится QTL, просто используйте STL. У них может не быть API Qt-ish, но STL API стабильно работает :) Тем не менее, qCopyBackward - это просто std::copy_backward, поэтому, по крайней мере, они согласованы.

Отвечая на ваш вопрос:

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

РЕДАКТИРОВАТЬ 2015-07-21: Очевидно (или, может быть, нет), если вы хотите получить одну строку (и люди, кажется, предпочитают это, глядя на относительные отзывы разные ответы через пять лет), и у вас есть не const list вышеизложенное сводится к

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

Но я полагаю, что трюки с индексами лучше для обеспечения безопасности работы:)

Answer 2

Переверните ваш QList одной строкой:

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

Answer 3

@ Марк Марк Йентш хороший ответ. И если вы хотите получить дополнительное повышение производительности 30% , вы можете изменить его однострочник на:

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

Один ThinkPad W520 с QList 10 миллионов QTimers Я получил эти цифры:

• переполнение стека в обратном списке заняло 194 мс
• переполнение стека списка обращений с максимальным и размером заняло 136 мс

Повышение является результатом

• выражение (list.size () / 2) вычисляется только один раз при инициализации цикла, а не после каждого шага
• выражение list.size () в swap () вызывается только один раз при инициализации цикла, а не после каждого шага

Answer 4

Вы можете использовать итератор в стиле Java. Полный пример здесь (http://doc.qt.digia.com/3.2/collection.html). Ищите слово «реверс».

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 5

[Переписать с оригинала]

Непонятно, хочет ли OP узнать, «как [я] обращаю QList?» или на самом деле хочет перевернутую копию. Пользователь mmutz дал правильный ответ для перевернутой копии, но если вы просто хотите перевернуть QList на месте, вот что:

#include <algorithm>

А потом

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

Или в C ++ 11:

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

Прелесть стандартной библиотеки C ++ (и шаблонов в целом) заключается в том, что алгоритмы и контейнеры являются отдельными. Поначалу может показаться раздражающим, что стандартные контейнеры (и в меньшей степени контейнеры Qt) не имеют вспомогательных функций, таких как list.reverse(), но рассмотрим альтернативы: что более элегантно: предоставить методы reverse() для всех контейнеров, или определить стандартный интерфейс для всех контейнеров, которые допускают двунаправленную итерацию, и обеспечить одну реализацию reverse(), которая работает для всех контейнеров, поддерживающих двунаправленную итерацию?

Чтобы проиллюстрировать, почему это элегантный подход, рассмотрим ответы на некоторые похожие вопросы:

«Как перевернуть std::vector<int>?»:

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

«Как перевернуть std::deque<int>?»:

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

А как насчет частей контейнера?

«Как перевернуть первые семь элементов QList?»: Даже если бы авторы QList предоставили нам удобный метод .reverse(), они, вероятно, не дали бы нам эту функциональность, но здесь это:

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

Но это становится лучше: поскольку интерфейс итератора совпадает с синтаксисом указателя C, а C ++ 11 добавил свободные функции std::begin() и std::end, вы можете сделать это:

«Как перевернуть массив float x[10]?»:

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

или до C ++ 11:

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

(Это уродство, которое std::end() скрывает для нас.)

Давайте продолжим: «Как вы реверсируете буфер float* x размером n?»:

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

«Как перевернуть строку с нулевым символом в конце char* s?»:

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

«Как перевернуть необязательно завершающуюся нулем строку char* s в буфере размером n?»:

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

Обратите внимание, что std::reverse использует swap(), поэтому даже это будет работать так же хорошо, как это возможно:

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

Также обратите внимание, что все они должны работать так же, как и рукописный цикл, поскольку, когда это возможно, компилятор превратит их в арифметику указателей. Кроме того, вы не можете просто написать многоразовую, универсальную, высокопроизводительную функцию reverse, подобную этой C.

Answer 6

Реверсировать QList будет O (n), как бы вы это ни делали, поскольку QList не гарантирует непрерывного хранения своих данных в памяти (в отличие от QVector). Вы можете просто просмотреть список в обратном порядке, где вам нужно, или использовать что-то вроде QStack, который позволяет вам извлекать элементы в том порядке, в котором они были добавлены.

Answer 7

Для стандартных списков библиотек это будет выглядеть так

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

К сожалению, в Qt нет функций rbegin и rend, которые возвращают обратные итераторы (те, которые идут от конца контейнера к его началу). Вы можете написать их, или вы можете просто написать функцию копирования самостоятельно - обращение к списку - хороший пример. Или вы можете заметить, что QList на самом деле является массивом, что делает написание такой функции тривиальным. Или вы можете преобразовать список в std :: list и использовать rbegin и rend. Выбирай что хочешь.