L' std::sort algorithme (et ses cousins std::partial_sort et std::nth_element) de la Norme C++ de la Bibliothèque est dans la plupart des implémentations un complexe et hybride amalgation de plus élémentaires algorithmes de tri, tels que la sélection du tri, de l'instertion de tri, tri rapide, de fusion et de tri, ou d'un segment de tri.
Il y a beaucoup de questions ici et sur les sites partenaires tels que http://codereview.stackexchange.com/ liés à des bugs, de la complexité et des autres aspects de la mise en œuvre classique algorithmes de tri. La plupart des implémentations sont constitués de matières premières boucles, utilisez l'index de la manipulation et de types de béton, et sont généralement non négligeable pour l'analyser en termes d'exactitude et d'efficacité.
Question: comment le ci-dessus mentionné classique algorithmes de tri être mis en œuvre à l'aide de C++moderne?
-
pas de matières boucles, mais la combinaison de la Bibliothèque Standard de l'algorithmique blocs de construction de
<algorithm> - l'interface iterator et l'utilisation de modèles au lieu de l'indice de la manipulation et de types de béton
-
C++14 de style, y compris l'intégralité de la Bibliothèque Standard, ainsi que syntaxique bruit des réducteurs tels que l'
auto, modèle alias, transparant comparateurs et polymorphe lambdas.
Notes:
- pour plus de références sur des implémentations des algorithmes de tri, voir Wikipedia, Rosetta Code ou http://www.sorting-algorithms.com/
- selon Sean Parent conventions (diapositive 39), un brut de la boucle est un
for-boucle plus longue que la composition de deux fonctions avec un opérateur. Donc,f(g(x));ouf(x); g(x);ouf(x) + g(x);ne sont pas premières boucles, et ne sont ni les boucles enselection_sortetinsertion_sortci-dessous. - J'ai suivi Scott Meyers, la terminologie pour désigner l'actuel C++1y déjà que le C++14, et pour désigner C++98 et C++03, tant que C++98, afin de ne pas la flamme de moi pour cela.
- Comme suggéré dans les commentaires de @Mehrdad, j'ai quatre implémentations comme un Exemple vivant à la fin de la réponse: C++14, C++11, C++98 et de Stimuler et C++98.
- La réponse elle-même est présentée en termes de C++14. Le cas échéant, je dénoter la syntaxe et de la bibliothèque de différences où les différentes versions linguistiques différentes.
