Ordenar un vector en orden descendente

310

Debería usar

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

o

std::sort(numbers.rbegin(), numbers.rend());   // note: reverse iterators

ordenar un vector en orden descendente? ¿Hay algún beneficio o inconveniente con un enfoque u otro?

flujo libre
fuente
2
+1 Creo que la respuesta es obvia, pero esta pregunta tiene un poco de trivium interesante. :)
wilhelmtell
3
Votaría por la primera opción, solo porque entonces nunca tendré que lidiar con reverse_iteratorla de.
evandrix
2
@wilhelmtell Una pregunta novata, pero ¿por qué la segunda debe clasificarse en orden descendente? Estamos dando la misma matriz como entrada al método de clasificación. Es solo que lo estamos dando en orden inverso, entonces, ¿por qué debería ordenarse en orden descendente y no ascendente, como sería el caso con ar.begin () y ar.end.
shshnk
66
@shshnk std::sort(b, e);pone el mínimo en b(en nuestro caso rbegin, por lo que el último elemento) y el máximo en e(en nuestro caso rend, por lo que el primer elemento).
fredoverflow

Respuestas:

114

En realidad, el primero es una mala idea. Use el segundo o este:

struct greater
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};

std::sort(numbers.begin(), numbers.end(), greater());

De esa manera, su código no se romperá silenciosamente cuando alguien decida que numbersdebería retener longo en long longlugar de int.

usuario541686
fuente
1
@FredOverflow: Hiciste los honores en tu comentario;)
user541686
2
O quédate con el primero. Use un typedef para numberContainer, una buena idea para que alguien PUEDE cambiar por mucho tiempo, y escriba: std :: sort (numbers.begin (), numbers.end (), std :: Greater <numContainer :: value_type> ( ));
RichardHowells
1
+1 El primero es realmente confuso. ¿Qué es greaterel otro? rbeginy rendfueron hechos para un propósito específico.
Abhishek Divekar
66
¿Por qué no solo std::greater<typename decltype(numbers)::value_type>()o algo así?
einpoklum
1
Esta respuesta está desactualizada; puede usarla std::greater<>()desde C ++ 14.
Nikolai
70

Usa el primero:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

Es explícito de lo que está pasando - menos posibilidades de mala interpretación rbeginque begin, incluso con un comentario. Es claro y legible, que es exactamente lo que quieres.

Además, el segundo puede ser menos eficiente que el primero dada la naturaleza de los iteradores inversos, aunque tendría que perfilarlo para estar seguro.

Pubby
fuente
68

Con c ++ 14 puedes hacer esto:

std::sort(numbers.begin(), numbers.end(), std::greater<>());
mrexciting
fuente
30

¿Qué hay de esto?

std::sort(numbers.begin(), numbers.end());
std::reverse(numbers.begin(), numbers.end());
shoumikhin
fuente
13
Una razón podría ser evitar la complejidad adicional: O (n * log (n)) + O (n) vs O (n * log (n))
greg
32
@greg O (n * log (n)) = O (n * log (n) + n). Son dos formas de definir el mismo conjunto. Quiere decir "Esto podría ser más lento".
pjvandehaar
44
@pjvandehaar Greg está bien. Él no dijo explícitamente, O (n * log (n) + n), dijo O (n * log (n)) + O (n). Tienes razón en que su redacción no está clara (especialmente su mal uso de la palabra complejidad), pero podrías haber respondido de una manera más amable. Por ejemplo: Tal vez quisiste usar la palabra "cálculo" en lugar de la palabra "complejidad". Invertir los números es un paso O (n) innecesario a un paso O (n * log (n)) idéntico.
Ofek Gila
3
@OfekGila Entiendo que la notación big-O se trata de conjuntos de funciones, y la notación involucra =y +son solo conveniencias y significado . En ese caso, O(n*log(n)) + O(n)es una notación conveniente para la O(n*log(n)) ∪ O(n)cual es lo mismo que O(n*log(n)). La palabra "cálculo" es una buena sugerencia y tiene razón sobre el tono.
pjvandehaar
22

En lugar de un functor como propuso Mehrdad, podría usar una función Lambda.

sort(numbers.begin(), numbers.end(), [](const int a, const int b) {return a > b; });
Julian Declercq
fuente
16

Según mi máquina, ordenar un long long vector de [1..3000000] usando el primer método toma alrededor de 4 segundos, mientras que usar el segundo toma aproximadamente el doble del tiempo. Eso dice algo, obviamente, pero tampoco entiendo por qué. Solo piensa que esto sería útil.

Lo mismo reportado aquí .

Como dijo Xeo, -O3usan casi el mismo tiempo para terminar.

zw324
fuente
12
¿Quizás no compiló con las optimizaciones activadas? Suena como si las reverse_iteratoroperaciones no estuvieran alineadas, y dado que son solo un contenedor alrededor de los iteradores reales, no es de extrañar que tomen el doble de tiempo sin alinearse.
Xeo
@Xeo Incluso si estuvieran en línea, algunas implementaciones usan una adición por desreferencia.
Pubby
@ildjarn: ¿Porque es así? La base()función miembro, por ejemplo, devuelve el iterador envuelto.
Xeo
1
@Xeo Ahora ambos terminan en un segundo. ¡Gracias!
zw324
3
@Xeo: lo retiro; el estándar realmente exige que std::vector<>::reverse_iteratorse implemente en términos de std::reverse_iterator<>. Extraño; hoy aprendí. :-P
Ildjarn
11

El primer enfoque se refiere:

    std::sort(numbers.begin(), numbers.end(), std::greater<>());

Puede usar el primer enfoque debido a que obtiene más eficiencia que el segundo.
La complejidad temporal del primer enfoque es menor que la segunda.

rashedcs
fuente
Esta es la misma respuesta que la de mrexciting. El comentario sobre la complejidad tampoco me queda claro.
Philipp Claßen
7
bool comp(int i, int j) { return i > j; }
sort(numbers.begin(), numbers.end(), comp);

fuente
44
para ser una respuesta válida, debe considerar escribir algo sobre las ventajas / desventajas de sus métodos de menciones frente a los del OP
Stefan Hegny el
3

TL; DR

Usar cualquier. Son casi lo mismo.

Respuesta aburrida

Como de costumbre, hay pros y contras.

Uso std::reverse_iterator:

  • Cuando está ordenando tipos personalizados y no desea implementar operator>()
  • Cuando eres demasiado vago para escribir std::greater<int>()

Usar std::greatercuando:

  • Cuando quieres tener un código más explícito
  • Cuando desee evitar el uso de iteradores inversos oscuros

En cuanto al rendimiento, ambos métodos son igualmente eficientes. Probé el siguiente punto de referencia:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std::chrono;

/* 64 Megabytes. */
#define VECTOR_SIZE (((1 << 20) * 64) / sizeof(int))
/* Number of elements to sort. */
#define SORT_SIZE 100000

int main(int argc, char **argv) {
    std::vector<int> vec;
    vec.resize(VECTOR_SIZE);

    /* We generate more data here, so the first SORT_SIZE elements are evicted
       from the cache. */
    std::ifstream urandom("/dev/urandom", std::ios::in | std::ifstream::binary);
    urandom.read((char*)vec.data(), vec.size() * sizeof(int));
    urandom.close();

    auto start = steady_clock::now();
#if USE_REVERSE_ITER
    auto it_rbegin = vec.rend() - SORT_SIZE;
    std::sort(it_rbegin, vec.rend());
#else
    auto it_end = vec.begin() + SORT_SIZE;
    std::sort(vec.begin(), it_end, std::greater<int>());
#endif
    auto stop = steady_clock::now();

    std::cout << "Sorting time: "
          << duration_cast<microseconds>(stop - start).count()
          << "us" << std::endl;
    return 0;
}

Con esta línea de comando:

g++ -g -DUSE_REVERSE_ITER=0 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out
g++ -g -DUSE_REVERSE_ITER=1 -std=c++11 -O3 main.cpp \
    && valgrind --cachegrind-out-file=cachegrind.out --tool=cachegrind ./a.out \
    && cg_annotate cachegrind.out

std::greater demo std::reverse_iterator demo

Los tiempos son iguales. Valgrind informa el mismo número de errores de caché.

ivaigult
fuente
2

No creo que deba usar ninguno de los métodos en la pregunta, ya que ambos son confusos, y el segundo es frágil, como sugiere Mehrdad.

Yo recomendaría lo siguiente, ya que parece una función de biblioteca estándar y deja en claro su intención:

#include <iterator>

template <class RandomIt>
void reverse_sort(RandomIt first, RandomIt last)
{
    std::sort(first, last, 
        std::greater<typename std::iterator_traits<RandomIt>::value_type>());
}
Martin Broadhurst
fuente
2
Esto es mil veces más confuso que simplemente usar el std::greatercomparador ...
Apollys apoya a Monica el
@Apollys Estoy de acuerdo en que a partir de C ++ 14, std :: greater <> parece la solución preferida. Si no tiene C ++ 14, aún podría ser útil si desea descartar cualquier sorpresa con std :: Greater <int> (por ejemplo, cuando los tipos en algún momento cambian de int a long).
Philipp Claßen
2

Puede usar el primero o probar el siguiente código, que es igualmente eficiente

sort(&a[0], &a[n], greater<int>());
Krish Munot
fuente