Como reverter uma QList?

votos
24

Vejo qCopy e qCopybackward mas nem parece deixe-me fazer uma cópia em ordem inversa. qCopybackwardapenas copia em ordem inversa, mas mantém os elementos danado na mesma ordem! Tudo o que eu quero fazer é retornar uma cópia da lista em ordem inversa. Não tem que ser uma função para isso, certo?

Publicado 27/08/2009 em 07:07
fonte usuário
Em outras línguas...                            


7 respostas

votos
28

Se você não gosta do QTL, basta usar o STL. Eles podem não ter uma API Qt-ish, mas a API STL é :) rock-estável Dito isto, qCopyBackwardé apenas std::copy_backward, então pelo menos eles são consistentes.

Respondendo sua pergunta:

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: Obviamente (ou talvez não), se você quiser um one-liner (e as pessoas parecem preferir que, olhando para as upvotes relativos de diferentes respostas após cinco anos) e você tem um nãoconst listos colapsos acima para

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

Mas eu acho que o índice mexer material é melhor para a segurança no emprego :)

Respondeu 27/08/2009 em 11:52
fonte usuário

votos
18

Inverter a sua QList com uma única linha:

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

Respondeu 02/11/2010 em 15:59
fonte usuário

votos
9

Você pode usar o iterator estilo Java. Exemplo completo aqui ( http://doc.qt.digia.com/3.2/collection.html ). Procure a palavra "reverso".

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();
}
Respondeu 12/07/2010 em 19:43
fonte usuário

votos
7

[Reescrever do original]

Não está claro se OP quer saber "Como [eu] reverter uma QList?" ou realmente quer uma cópia invertida. mmutz utilizador deu a resposta correta para uma cópia invertida, mas se você só quer reverter a QList no lugar, há esta:

#include <algorithm>

E depois

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

Ou em C ++ 11:

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

A beleza da biblioteca C ++ padrão (e modelos em geral) é que os algoritmos e os recipientes são separados. A princípio pode parecer chato que os contentores normais (e, em menor medida, os recipientes qt) não tem funções de conveniência como list.reverse(), mas considerar as alternativas: o que é mais elegante: Fornecer reverse()métodos para todos os recipientes, ou definir uma interface padrão para todos os recipientes que permitem iteração bidirecional e fornecem uma reverse()aplicação que funciona para todos os recipientes que suportam iteração bidirecional?

Para ilustrar porque esta é uma abordagem elegante, considere as respostas a algumas perguntas semelhantes:

"Como você reverter uma std::vector<int>?":

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

"Como você reverter uma std::deque<int>?":

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

E sobre porções do recipiente?

"Como você inverter os primeiros sete elementos de um QList?": Mesmo que os QListautores nos tinha dado uma conveniência .reverse()método, eles provavelmente não teria nos dado essa funcionalidade, mas aqui está:

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

Mas fica melhor: Como a interface do iterador é o mesmo que C sintaxe ponteiro, e porque C ++ 11 aditados os livres std::begin()e std::endfunções, você pode fazer estes:

"Como você reverter um array float x[10]?":

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

ou pré C ++ 11:

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

(Essa é a feiúra que std::end()esconde para nós.)

Vamos continuar: "Como você reverter um buffer float* xde tamanho n?":

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

"Como você reverter uma string terminada em null char* s?":

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

"Como você inverter uma string não-necessariamente-terminada nula char* sem um buffer de tamanho n?":

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

Note-se que std::reverseusa swap()por isso mesmo este irá executar muito bem, assim como ele poderia possivelmente:

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

Observe também que estes se todos executar, bem como um ciclo de escrita à mão uma vez que, quando possível, o compilador irá transformá-los em aritmética de ponteiro. Além disso, você não pode de forma limpa escrever uma reutilizáveis, genérico, de alto desempenho reversefunção como esta C.

Respondeu 06/06/2014 em 00:52
fonte usuário

votos
7

A resposta de @ Marc Jentsch é bom. E se você quiser obter um adicional de aumento de desempenho de 30% você pode mudar a sua one-liner para:

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

Um um W520 ThinkPad com um QList de 10 milhões de QTimers eu tenho esses números:

  • revertendo estouro lista pilha levou 194 ms
  • revertendo estouro lista de pilha com Max e tamanho levou 136 ms

O aumento é resultado de

  • a expressão (list.size () / 2) ser calculada apenas uma vez quando a inicializar o circuito e não depois de cada etapa
  • o list.size expressão () em swap () é chamado apenas uma vez ao inicializar o loop e não depois de cada etapa
Respondeu 18/12/2013 em 09:12
fonte usuário

votos
5

Revertendo uma QList vai ser O (n), no entanto você fazê-lo, uma vez QList não é garantido para ter seus dados armazenados de forma contígua na memória (ao contrário QVector). Você pode considerar apenas atravessando a lista em ordem para trás onde você precisa, ou usar algo como um QStack que permite recuperar os elementos na ordem inversa em que foram adicionados.

Respondeu 15/01/2010 em 05:10
fonte usuário

votos
5

Para listas de biblioteca padrão que seria parecido com este

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

Infelizmente, Qt não tem funções rbegin e rend que retornam iteradores reversos (as que vão desde a extremidade do recipiente à sua begnning). Você pode escrevê-los, ou você pode escrever apenas copiando função em seu próprio país - revertendo uma lista é uma boa excersize. Ou você pode notar que QList é na verdade uma matriz, o que torna a escrita de tal função trivial. Ou você pode converter a lista para std :: lista e utilize rbegin e rend. Escolha o que quiser.

Respondeu 27/08/2009 em 07:30
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more