Hay un método de ordenación() para listas en STL. Lo cual es absurdo, porque estaría más inclinado a ordenar una matriz/vector. ¿Por qué no se proporciona sort() para vector? ¿Existe alguna filosofía subyacente detrás de la creación del contenedor vectorial o su uso, ese tipo no está provisto para ello?¿Por qué vector no tiene el método sort() como una función miembro de vector, mientras que la lista lo hace?
Como ya se ha dicho, la biblioteca estándar proporciona una plantilla de función no miembro que puede ordenar cualquier rango dado un par de iteradores de acceso aleatorio.
Sería totalmente redundante tener una función miembro para ordenar un vector. El siguiente tendría el mismo significado:
std::sort(v.begin(), v.end());
v.sort();
Uno de los primeros principios de la STL es que los algoritmos no se acoplan a los contenedores. Cómo se almacenan los datos y cómo se manipulan los datos debe ser lo más parecida posible.
Los iteradores se utilizan como la interfaz entre los contenedores (que almacenan datos) y los algoritmos (que operan con los datos). De esta forma, puede escribir un algoritmo una vez y puede operar en contenedores de varios tipos, y si escribe un contenedor nuevo, los algoritmos genéricos existentes pueden usarse para manipular su contenido.
La razón por la cual std::list proporciona su propia función sort como función miembro es porque no es un contenedor accesible al azar; solo proporciona iteradores bidireccionales (ya que está destinado a representar una lista doblemente vinculada, esto tiene sentido). La función genérica std::sort requiere iteradores de acceso aleatorio, por lo que no puede usarla con un std::list. std::list proporciona su propia función sort para que pueda ser ordenada.
En general, hay dos casos en los que un recipiente debería implementar un algoritmo:
Si el algoritmo genérico no puede operar sobre el recipiente, pero no hay un algoritmo diferente, específica del contenedor que puede proporcionar la misma funcionalidad, como es el caso con std::list::sort.
Si el contenedor puede proporcionar una implementación específica del algoritmo que es más eficiente que el algoritmo genérico, como es el caso con std::map::find, que permite a un elemento que se encuentra en el mapa en tiempo logarítmica (el genérico std::find algoritmo realiza una búsqueda lineal porque no puede asumir que el rango está ordenado).
[Puede haber otras razones para implementar un algoritmo específico del contenedor; esos son solo los dos más grandes que vienen a la mente cuando se revisan los contenedores STL] –
+1, pero seguramente una mejor solución hubiera sido hacer que 'std :: sort()' se transfiriera a una función estática en una clase con plantilla en el tipo de contenedor del iterador. La plantilla de clase base proporcionaría la implementación que requiere acceso aleatorio como valor predeterminado, pero (al ser una plantilla de clase) podría estar parcialmente especializada para 'list
@j_random_hacker: No estoy seguro de que el enfoque sea lo suficientemente genérico como para admitir todos los contenedores posibles. Considere un contenedor donde los iteradores no son suficientes para realizar el ordenamiento y donde necesita acceder al contenedor en sí (no creo que esto sea un problema para una implementación de 'lista' típica, pero definitivamente podría implementar un contenedor de secuencia donde esto era el caso). –
Usted puede clasificar fácilmente un vector con:
sort(v.begin(), v.end());
ACTUALIZACIÓN: (respuesta a la observación): bien, tienen sin duda siempre que por defecto. La diferencia es que no es una función miembro para vector. std::sort es un algoritmo genérico que se supone que funciona para cualquier cosa que proporcione iteradores. Sin embargo, realmente espera que un iterador de acceso aleatorio se ordene eficientemente. std::list, al ser una lista vinculada, no puede proporcionar acceso aleatorio a sus elementos de manera eficiente. Es por eso que proporciona su propio algoritmo de ordenamiento especializado.
Pregunto por qué no lo proporcionaron por defecto para vector, como lo hicieron para la lista. Obviamente hay alguna razón. – Nav
Y la razón es exactamente lo que dice @Mehrdad. se proporciona fuera de la clase. La pregunta que se debería hacer es por qué no hacer lo mismo con 'list';) – jalf
' vector
std::sort() en <algorithm> qué clasificación en los contenedores con los iteradores de acceso aleatorio como std::vector.
También hay std::stable_sort().
edición - ¿por qué std::list tienen su propia función sort() frente std::vector?
std::list es diferente tanto std::vector y std::deque (tanto de acceso aleatorio iterable) en la forma en que está implementado, por lo que contiene su propio algoritmo sort que está especializada para su implementación.
estoy preguntando por qué no proporcionaron ordenar por defecto, como la forma en que lo hicieron para la lista – Nav
@Nav -' std :: list' es diferente tanto de 'std :: vECTOR' y' std :: deque '(tanto el acceso aleatorio iterable) en la forma en que se implementa, por lo que contiene su propio algoritmo 'sort' que está especializado para su implementación. – birryree
Una ordenación específica de vector no proporcionaría ninguna ventaja sobre std::sort de <algorithm>. Sin embargo, std::list proporciona su propio sort porque puede utilizar el conocimiento especial de cómo se implementa list para ordenar elementos manipulando los enlaces en lugar de copiar objetos.
+1, pero seguramente una mejor solución hubiera sido hacer que 'std :: sort()' se transfiriera a una función estática en una clase con plantilla en el tipo de contenedor del iterador. La plantilla de clase base proporcionaría la versión que requiere acceso aleatorio de 'sort()' como valor predeterminado, pero (al ser una plantilla de clase) podría estar parcialmente especializada para 'list
Respondiendo a la pregunta "¿Por qué?"
Un algoritmo de clasificación para std :: vector es lo mismo que ordenar una matriz nativa y es lo mismo (probablemente) que ordenar una clase de vector personalizada.
El STL fue diseñado para separar contenedores y algoritmos, y para tener un mecanismo eficiente para aplicar un algoritmo a los datos que tienen las características correctas.
Esto le permite escribir un contenedor que podría tener características específicas y liberar los algoritmos. Solo cuando hay alguna característica especial de los datos que significa que el algoritmo estándar no es adecuado se proporciona una implementación personalizada, como en el caso de std :: list.
Ya hay elementos interesantes de respuesta, pero en realidad hay más que decir acerca de la pregunta: mientras que la respuesta a "¿por qué std::vector no tiene una función de miembro sort?" es de hecho "porque la biblioteca estándar proporciona funciones miembro solo cuando ofrecen más que algoritmos genéricos", la pregunta realmente interesante es "¿por qué std::list tiene una función miembro sort?", y algunas cosas aún no se han explicado: sí, std::sort sólo funciona con iteradores de acceso aleatorio y std::list sólo proporciona iteradores bidireccionales, pero incluso si std::sort trabajó con iteradores bidireccionales, std::list::sort habría todavía ofrecer más. Y aquí es por qué:
En primer lugar, std::list::sort es estable, mientras que no es std::sort. Por supuesto todavía hay std::stable_sort, pero tampoco funciona con iteradores bidireccionales.
std::list::sort generalmente implementa un mergesort, pero sabe que está ordenando una lista y puede volver a vincular los nodos en lugar de copiar cosas. Un mergesort consciente de la lista puede ordenar la lista en el tiempo O (n log n) con solo O (log n) memoria adicional, mientras que el mergesort típico (como std::stable_sort) usa O (n) memoria adicional o tiene O (n log² n) complejidad.
std::list::sort no invalida los iteradores. Si un iterador estaba apuntando a un objeto específico en la lista, seguirá apuntando al mismo objeto después de la ordenación, incluso si su posición en la lista no es la misma que antes de la ordenación.
Por último pero no menos importante, std::list::sort no mueve ni intercambia los objetos ya que solo vuelve a vincular los nodos. Eso significa que podría ser más performante cuando se necesita para clasificar objetos que son caros de mover/cambiar todo, pero también que puede ordenar una lista de objetos que no son ni siquiera móvil, que es totalmente imposible que std::sort!
Básicamente, incluso si std::sort y std::stable_sort trabajó con iteradores bidireccionales o hacia adelante (y sería totalmente posible, sabemos algoritmos de ordenación que trabajan con ellos), que todavía podría no ofrecer todo std::list::sort tiene que ofrecer, y tampoco pudieron volver a vincular los nodos, ya que los algoritmos de la biblioteca estándar no pueden modificar el contenedor, solo los valores apuntados (los nodos de vinculación cuentan como la modificación del contenedor). Por otro lado, un método dedicado std::vector::sort no ofrecería nada interesante, por lo que la biblioteca estándar no proporciona ninguno.
Tenga en cuenta que todo lo que se ha dicho sobre std::list::sort también es cierto para std::forward_list::sort.
No es exactamente un duplicado, pero la respuesta de AndreyT a [por qué no hay ningún hallazgo para el vector en C++] (http://stackoverflow.com/questions/2994073/why-there-is-no-find-for- vector-in-c) está relacionado. En realidad –
una mejor pregunta sería: "¿? ¿Por qué' list' tienen un método 'sort()' Por qué no puedes simplemente usar 'std :: sort()' 'que con Vector's y matrices" Además, no estoy seguro de por qué cree que es "absurdo" querer ordenar una lista. –
@j_random_hacker: El absurdo es probablemente debido a la forma en que veo la razón para usar una lista, en mi mente. Lo veo como algo así como enlaces de una cadena conectados entre sí, que deben desconectarse antes de volver a organizarlos, en comparación con el vector, que veo como un paquete de tarjetas que se puede barajar fácilmente. Mi percepción ... se aclarará cuando esté familiarizado con la programación con listas. – Nav