Différences

Cette page vous donne les différences entre la révision choisie et la version actuelle de la page.

--- rechercher [2016/01/07 20:07]
gbdivers
+++ rechercher [2017/01/16 19:27] (Version actuelle)
gbdivers
@@ Ligne 1: / Ligne 1: @@
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[comparer|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[iterateurs|Chapitre suivant]] ^
-====== Algorithmes et itérateurs ======
+====== Les catégories d'algorithmes standards ======
 La [[http://en.cppreference.com/w/cpp/algorithm|page de documentation]] sur les algorithmes de la bibliothèque standard fournit une liste d'une centaine de fonctions différentes. À cela, il faut ajouter le fait que chaque fonction peut avoir plusieurs signatures (listes de paramètres différents, en particulier des versions avec et sans prédicat personnalisé).
@@ Ligne 8: / Ligne 9: @@
 Ce cours ne va pas détailler tous ces algorithmes. Cela serait purement descriptif et vous n'apprendrez pas grand chose de plus qu'en lisant la documentation. Ce qui est important est d'avoir une vision d'ensemble des algorithmes proposés, savoir où trouver l'algorithme qui vous intéresse lorsque vous êtes face à une problématique.
-Vous allez voir dans ce chapitre quelques algorithmes notables, ce qui va permettre d'introduire quelques notions importantes, vous apprendre à utiliser au mieux les algorithmes à lire la page de documentation.
+Pour organiser un peu les algorithmes de la bibliothèque standard, la [[http://en.cppreference.com/w/cpp/algorithm|page de documentation sur cppreference.com]] sépare les algorithmes en plusieurs catégories. Vous allez voir dans ce chapitre quelques algorithmes notables, ce qui va permettre d'introduire quelques notions importantes, vous apprendre à utiliser au mieux les algorithmes et à lire la page de documentation.
+Ce chapitre détaille plus particulièrement les algorithmes qui ne retournent pas d'itérateur et qui ne nécessitent donc pas de détailler ce concept. Les itérateurs seront détaillés dans le chapitre suivant, ainsi que d'autres algorithmes de la bibliothèques standard.
 Note : des exercices seront ajoutés par la suite à ce cours. Ils vous permettront d'étudier et pratiquer plus en détail ces algorithmes.
+===== Les algorithmes non modifiants =====
-===== Catégories d'algorithmes =====
+Les algorithmes non modifiants (//non-modifying sequence operations//). Ce sont des algorithmes qui ne modifient pas les collections sur les quelles ils sont utilisés. Vous allez trouver dans cette catégorie par exemple l'algorithme d'égalité ''std::equal'' que vous avez déjà vu, ainsi que les algorithmes de recherche (en premier lieu ''std::find''), les algorithmes de comptage (''std::count'') et l'algorithme ''std::for_each'' (qui permet d'appeler une fonction sur chaque élément d'une collection).
-Pour organiser un peu les algorithmes de la bibliothèque standard, la [[http://en.cppreference.com/w/cpp/algorithm|page de documentation sur cppreference.com]] sépare les algorithmes en plusieurs catégories.
+Un algorithme non modifiants va donc prendre une collection sans la modifier et retourner un résultat. La valeur retournée peut être utilisée directement ou enregistrée dans une variable, comme n'importe quelle valeur. Le type de la valeur retournée dépend de l’algorithme et du type de collection, le plus simple est d'utiliser l’inférence de type pour créer une variable (consulter la documentation pour connaitre le type exact).
-Les **algorithmes non modifiants** (//non-modifying sequence operations//). Ce sont des algorithmes qui ne modifient pas les collections sur les quelles ils sont utilisés. Vous allez trouvé dans cette catégorie par exemple l'algorithme d'égalité ''std::equal'' que vous avez déjà vu, ainsi que les algorithmes de recherche (en premier lieu ''std::find''), les algorithmes de comptage (''std::count'') et l'algorithme ''std::for_each'' (qui permet d'appeler une fonction sur chaque élément d'une collection).
+<note>Les exemples de code suivants utilisent une chaîne, pour simplifier l’écriture du code et l'affichage du résultat. N'oubliez pas qu'une chaîne est une collection de caractères.</note>
-Les **algorithmes modifiants** (//modifying sequence operations//), vous l'avez surement deviné, modifient les collections sur les quelles ils sont utilisés. Vous trouverez dans cette catégorie les algorithmes pour ajouter (''std::fill''), supprimer (''std::remove''), remplacer (''std::replace''), copier (''std::copy''), échanger (''std::swap'') ou mélanger (''std::suffle'') des éléments.
-Ces deux premières catégories sont génériques et regroupent les algorithmes qui ne sont pas classés dans les catégories suivantes.
+==== std::all_of, std::any_of et std::none_of ====
-Les **algorithmes de partitionnement** (//partitioning operations//) permettent séparer une collection en deux sous-collections.
-Les **algorithmes de tri** (//sorting operations//) permettent de trier les éléments d'une collection.
-Les **algorithmes binaires de recherche** (//binary search operations//) permettent de rechercher un élément dans une collection triée.
-Les **algorithmes sur les ensembles** (//set operations//) permettent de manipuler une collection comme un ensemble d’éléments (donc sans élément en double).
-Les **algorithmes sur les Tas** (//heap operations//) permettent de manipuler une collection comme un Tas d’éléments.
-Les **algorithmes minimum/maximum** permettent de recherche des éléments minimum ou maximum et réaliser des permutations.
-Les **algorithmes numériques** (//numeric operations//) permettent de travailler sur des collections de nombres.
-==== Quelques exemples d'algorithmes standards ====
-Un algorithme non modifiants va donc prendre une collection sans la modifier et retourner un résultat. La valeur retournée peut être utiliser directement ou enregistrer dans une variable, comme n'importe quelle valeur. Le type de la valeur retournée dépend de l’algorithme et du type de collection, le plus simple est d'utiliser l’inférence de type pour créer une variable (consulter la documentation pour connaitre le type exact).
-<note>Les exemples de code suivants utilisent une chaîne, pour simplifier l’écriture du code et l'affichage du résultat. N'oubliez pas qu'une chaîne est une collection de caractères.</note>
-Les algorithmes ''std::all_of'', ''std::any_of'', ''std::none_of'' permettent de tester respectivement : si tous les éléments d'une collection respectent un prédicat, si au moins un élément respecte un prédicat ou si aucun élément ne respecte un prédicat. Ces trois algorithmes retournent un booléen.
+Les algorithmes [[http://en.cppreference.com/w/cpp/algorithm/all_any_none_of|std::all_of, std::any_of et std::none_of]] permettent de tester respectivement : si tous les éléments d'une collection respectent un prédicat, si au moins un élément respecte un prédicat ou si aucun élément ne respecte un prédicat. Ces trois algorithmes retournent un booléen.
 Par exemple, pour tester si une chaîne possède des majuscules, vous pouvez utiliser les fonctions définies dans [[http://en.cppreference.com/w/cpp/string/byte|l'en-tête <cctype>]], en particulier la fonction ''isupper'' ("est une majuscule").
@@ Ligne 71: / Ligne 53: @@
 </code>
-Les algorithmes ''std::count'' et ''std::count_if'' permettent le nombre d’éléments d'une collection correspondant respectivement a une valeur et un prédicat. Ces algorithmes retournent une valeur entière signée.
+==== std::count et std::count_if ====
+Les algorithmes [[http://en.cppreference.com/w/cpp/algorithm/count|std::count et std::count_if]] retournent le nombre d’éléments d'une collection correspondant respectivement à une valeur et un prédicat. Ces algorithmes retournent une valeur entière signée.
 <code cpp main.cpp>
@@ Ligne 93: / Ligne 78: @@
 </code>
-Et bien sur, vous avez déjà vu l'algorithme ''std::equal''.
+==== std::equal ====
+Et bien sûr, vous avez déjà vu l'algorithme [[http://en.cppreference.com/w/cpp/algorithm/equal|std::equal]].
 <code cpp main.cpp>
@@ Ligne 114: / Ligne 102: @@
 </code>
+===== Les algorithmes modifiants =====
+Les algorithmes modifiants (//modifying sequence operations//), vous l'avez surement deviné, modifient les collections sur les quelles ils sont utilisés. Vous trouverez dans cette catégorie les algorithmes pour ajouter (''std::fill''), supprimer (''std::remove''), remplacer (''std::replace''), copier (''std::copy''), échanger (''std::swap'') ou mélanger (''std::suffle'') des éléments.
 Les algorithmes modifiants sont de deux types : les algorithmes qui modifient directement une collection et les algorithmes qui utilisent une collection et modifient une autre collection.
+Par exemple :
+<code>
+std::fill(begin(in), end(in), value);                       // seulement in
+std::transform(begin(in), end(in), begin(out), operation);  // in et out
+</code>
+Mais il est généralement possible d'utiliser le second type d'algo modifiant avec la même collection en entrée et sortie :
+<code>
+std::transform(begin(in), end(in), begin(in), operation);
+</code>
+Dans le premier cas, transforme les éléments de ''in'' et met le résultat dans ''out''. Dans le second cas, transforme les éléments de ''in'' et met le résultat dans ''in''. (les valeurs initiales sont donc perdues).
+==== std::copy, std::copy_if et std::copy_n ====
+Note : pas de contrôle de dépassement de collection.
+Equivalent : ''std::move'', mais sera vu plus tard.
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    const std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s2       { "........................................" };
+    std::string s3       { "........................................" };
+    std::string s4       { "........................................" };
+    std::copy(cbegin(s1), cend(s1), begin(s2));
+    std::cout << s2 << std::endl;
+    std::copy_if(cbegin(s1), cend(s1), begin(s3), isalpha);
+    std::cout << s3 << std::endl;
+    std::copy_n(cbegin(s1), 10, begin(s4));
+    std::cout << s4 << std::endl;
+}
+</code>
+affiche :
+<code>
+f9c02b6c9da8943feaea4966ba7417d65de2fe7e
+fcbcdafeaeabaddefee.....................
+f9c02b6c9d..............................
+</code>
+==== std::copy_backward ====
+Note : pas de contrôle de dépassement de collection.
+Equivalent : ''std::move_backward'', mais sera vu plus tard.
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    const std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s2       { "........................................" };
+    std::string s3       { "........................................" };
+    std::copy(begin(s1) + 10, begin(s1) + 15, begin(s2) + 10);
+    std::cout << s2 << std::endl;
+    std::copy_backward(begin(s1) + 10, begin(s1) + 15, begin(s3) + 10);
+    std::cout << s3 << std::endl;
+}
+</code>
+affiche :
+<code>
+..........a8943.........................
+.....a8943..............................
+</code>
+==== std::fill et std::fill_n ====
 <code cpp main.cpp>
@@ Ligne 138: / Ligne 216: @@
 </code>
-reverse
+==== std::transform ====
-===== Le concept d'itérateurs =====
+Différent des autres algos, ne prend pas un prédicat (objet appelable qui retourne un booléen), mais prend en paramètre un opérateur unaire ou binaire (selon la version de ''transform'' appelée).
-Pour appeler les algorithmes sur des collections, vous avez vu les fonctions ''begin'' et ''end'' pour parcourir du début à la fin (et leur équivalent "reverse", pour lire de la fin au début, ''rbegin'' et ''rend''). Il est possible d'enregistrer ces positions dans des variables, par exemple en utilisant l'inférence de type avec ''auto'' :
+La documentation précise la signature des fonctions (in = input = entrée, out = output = sortie) :
 <code cpp>
-std::vector&lt;int>; v { 1, 5, 2, 4, 3 };
+// unaire
-auto b = std::begin(v);
+TypeOut fun1(const Type &amp;a);
-auto e = std::end(v);
+std::transform(std::begin(in), std::end(in), std::begin(out), fun1);
-std::sort(b, e);
+// binaire
+TypeOut fun2(const Type1 &a, const Type2 &b);
+std::transform(std::begin(in1), std::end(in1), std::begin(in2), std::begin(out), fun2);
 </code>
-Bien sûr, il est également possible d'écrire explicitement le type des variables ''b'' et ''e'', au lieu d'utiliser l'inférence de type. La syntaxe est dans ce cas :
+Par exemple :
+Version unaire :
 <code cpp>
-std::vector<int>::iterator b = std::begin(v);
+#include <iostream>
-std::vector<int&gt;::iterator e = std::end(v);
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s { "azerty" };
+    std::transform(begin(s), end(s), begin(s), toupper);
+    std::cout <&lt; s <<; std::endl;
+}
 </code>
-Vous verrez par la suite la signification exacte de cette syntaxe, un peu compliquée (c'est la raison pour laquelle on utilise l'inférence de type, c'est plus simple à écrire). Ce qui est important de comprendre, c'est que la position dans une collection est gérée en C++ par le concept d'itérateur. Peu importe pour le moment de savoir à quoi correspondent exactement les itérateurs, retenez qu'ils représentent une position et qu'ils permettent de parcourir les éléments d'un conteneur.
+affiche :
-La paire d'itérateurs ''b'' et ''e'' définit ce que l'on appelle un &quot;range&quot;, un intervalle. Plus généralement, un //range// est une paire d'itérateurs :
+&lt;code&gt;
+AZERTY
+<;/code>
-  * qui proviennent de la même collection ;
+Version binaire :
-  * qui sont ordonnés (la première position est plus petite ou égale à la seconde).
-Ainsi, les paires d'itérateurs ''(begin(v), end(v))'' ou ''(end(v), end(v))'' sont des //ranges//, tandis que les paires ''(begin(v1), end(v2))'' et ''(end(v), begin(v))'' ne le sont pas. Cette notion de //range// est importante, puisque les algorithmes de la bibliothèque standard n'acceptent en argument que des //range//s.
+<code cpp>
+#include <iostream>
+#include <functional>
+#include <algorithm>
+#include <vector>
+int main() {
+    std::vector<int> v1 { 1, 2, 3, 4 };
+    const std::vector<int> v2 { -1, 2, -1, 2 };
+    std::transform(begin(v1), end(v1), begin(v2), begin(v1), std::multiplies<int>());
+    for (auto i: v1) std::cout << i << ' ';
+    std::cout << std::endl;
+}
+</code>
-Attention, si vous n'utilisez pas un //range// valide, cela ne produit pas de message d'erreur, mais un comportement indéfini (//undefined behavior//), ce qui est une erreur très difficile à identifier.
+affiche :
+<code>
+-1 4 -3 8
+</code>
-===== Créer une nouvelle collection =====
+==== std::generate et std::generate_n ====
-Il est possible de créer une nouvelle collection à partir d'un //range//, en passant une paire d'itérateurs en argument (donc entre parenthèses) lors de la définition d'une variable.
+avec rand ?
-<code cpp>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-// définition d'une nouvelle variable
+==== std::remove et std::replace ====
-std::vector<int> v2(std::begin(v1), std::end(v1));
-// avec auto
+<code cpp main.cpp>
-auto v3 = std::vector<int&gt;(std::begin(v1), std::end(v1));
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::remove(begin(s1), end(s1), '7');
+    std::cout <&lt; s1 << std::endl;
+    std::string s2 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::remove_if(begin(s2), end(s2), isdigit);
+    std::cout << s2 << std::endl;
+    const std::string s3 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s4       { "........................................" };
+    std::remove_copy(begin(s3), end(s3), begin(s4), '7');
+    std::cout << s4 << std::endl;
+    const std::string s5 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s6       { "........................................" };
+    std::remove_copy_if(begin(s5), end(s5), begin(s6), isdigit);
+    std::cout << s6<< std::endl;
+}
 </code>
-Il est également possible de créer un nouvel objet et de l'affecter à une variable existante.
+affiche :
-<code cpp>
+<code>
-std::vector<int> v4 {}; // vide
+f9c02b6c9da8943feaea4966ba41d65de2feee7e
-v4 = std::vector<int>(std::begin(v1), std::end(v1));
+fcbcdafeaeabaddefeea4966ba7417d65de2fe7e
+f9c02b6c9da8943feaea4966ba41d65de2fee...
+fcbcdafeaeabaddefee.....................
 </code>
-Bien sûr, en utilisant ''begin'' et ''end'' comme //range//, cela est peu intéressant, on fait l'équivalent d'une copie là où on peut utiliser l'opérateur d'affection :
-<code cpp>
+<code cpp main.cpp>
-std::vector<int&gt; v2 { v1 };
+#include <iostream>
-auto v3 = v1;
+#include <string>
-v4 = v1;
+#include <cctype>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::replace(begin(s1), end(s1), '7', '.');
+    std::cout <&lt; s1 << std::endl;
+    std::string s2 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::replace_if(begin(s2), end(s2), isdigit, '.');
+    std::cout <;< s2 << std::endl;
+    const std::string s3 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s4       { "........................................" };
+    std::replace_copy(begin(s3), end(s3), begin(s4), '7', '.');
+    std::cout << s4 << std::endl;
+    const std::string s5 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::string s6       { "........................................" };
+    std::replace_copy_if(begin(s5), end(s5), begin(s6), isdigit, '.');
+    std::cout << s6<< std::endl;
+}
 </code>
-Contrairement à la copie, il est possible de changer le type de conteneur. Par exemple, pour passer à un ''vector<float>''
+affiche :
-<code cpp>
+<code>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
+f9c02b6c9da8943feaea4966ba.41.d65de2fe.e
+f.c..b.c.da....feaea....ba....d..de.fe.e
-std::vector<float> v2 { v1 };                        // erreur
+f9c02b6c9da8943feaea4966ba.41.d65de2fe.e
-std::vector<float> v2(std::begin(v1), std::end(v1)); // ok
+f.c..b.c.da....feaea....ba....d..de.fe.e
 </code>
-On va également pouvoir créer une sous-collection. Par exemple, pour créer une collection contenant la première moitié des éléments d'une collection :
+==== std::swap etstd::swap_ranges ====
-<code cpp>
+std::swap ne travaille pas sur des collections en particulier.
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-std::vector&lt;float&gt; v2(std::begin(v1), std::end(v1) - v1.size() / 2);
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "azerty" };
+    std::string s2 { &quot;123456&quot; };
+    std::swap(s1, s2);
+    std::cout << s1 << std::endl;
+    std::cout << s2 << std::endl;
+    int x { 123 };
+    int y { 456 };
+    std::swap(x, y);
+    std::cout << x << std::endl;
+    std::cout << y << std::endl;
+}
 </code>
-ou les 2 premiers éléments :
+affiche :
-<code cpp>
+<code>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-std::vector<float> v2(std::begin(v1), std::begin(v1) + 2);
+azerty
+
 </code>
-===== Inclusion et exclusion des bornes dans un range =====
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "azerty" };
+    std::string s2 { "123456" };
+    std::swap_ranges(begin(s1), begin(s1) + 3, begin(s2));
+    std::cout << s1 << std::endl;
+    std::cout << s2 << std::endl;
+}
+</code>
-Pour effectuer une recherche dans une collection, on peut utiliser ''find''. Si on regarde la documentation, elle indique que cette fonction prend un //range// et un élément à chercher, elle retourne l'itérateur (donc une position) de l'élément dans la collection s'il a été trouvé, sinon l'itérateur ''end''.
+affiche :
-<code cpp>
+<code>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
+rty
-auto position = std::find(std::begin(v), std::end(v), 3);
+aze456
 </code>
-On peut alors utiliser cette position pour créer deux sous-collections :
+iter_swap ?
+==== reverse et reverse_copy ====
 <code cpp main.cpp>
 #include <iostream>
-#include <vector>
+#include <string>
 #include <algorithm>
 int main() {
-    std::vector&lt;int&gt; v1 { 1, 2, 3, 4, 5 };
+    std::string s1 { &quot;azerty&quot; };
-    auto p = std::find(std::begin(v1), std::end(v1), 3);
+    std::reverse(begin(s1), end(s1));
+    std::cout <&lt; s1 <<; std::endl;
-    std::vector<float&gt; v2(std::begin(v1), p);
-    for (auto i: v2) std::cout &lt;&lt; i << ' ';
+    const std::string s2 { &quot;azerty&quot; };
-    std::cout &lt;&lt; std::endl;
+    std::string s3       { &quot;......&quot; };
+    std::reverse_copy(begin(s2), end(s2), begin(s3));
-    std::vector<float> v3(p, std::end(v1));
+    std::cout << s3 << std::endl;
-    for (auto i: v3) std::cout << i << ' ';
-    std::cout << endl;
 }
 </code>
@@ Ligne 256: / Ligne 436: @@
 <code>
-2
+ytreza
-4 5
+ytreza
 </code>
-On voit ici une particularité importante des //ranges//. La variable ''p'' correspond à la position de la valeur ''3'' dans la collection. On pourrait croire que la collection ''v2'' qui est créée à partir de ''begin(v1)'' et ''p'' allait contenir les éléments ''{ 1, 2, 3 }'', mais ce n'est pas le cas.
-En effet, un //range// est une paire d'itérateurs dont le premier est inclus et le second exclu.
+==== rotate ====
-<note>On écrira souvent ''[first, last)'' pour désigner un //range//. Cette notation mathématique permet d'écrire un ensemble, avec les crochets droits pour inclure les bornes et les parenthèses pour les exclure. Ainsi, l'ensemble [0, 1) correspond à l'ensemble des réels compris entre 0 inclus et 1 exclu, (0, 1) exclu les valeurs 0 et 1, (0, 1] exclu 0 et inclus 1, etc.</note>
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "azerty" };
+    std::rotate(begin(s1), begin(s1) + 2, end(s1));
+    std::cout << s1 << std::endl;
+    const std::string s2 { "azerty" };
+    std::string s3       { "......" };
+    std::rotate_copy(begin(s2), begin(s2) + 2, end(s2), begin(s3));
+    std::cout << s3 << std::endl;
+}
+</code>
-Revenons sur un code précédent. Lorsque l'on écrit :
+affiche :
-<code cpp>
+<code>
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
+ertyaz
-std::vector<int> v2(std::begin(v1), std::end(v1));
+ertyaz
 </code>
-On a bien une copie complète de ''v1''. Est-ce que cela est compatible avec l'exclusion de la borne supérieure du //range// ? En fait, oui, tout simplement parce que ''end(v1)'' correspond à la fin de la collection, et non au dernier élément de cette collection. Si on crée des sous-collections depuis les premiers et derniers éléments :
-<code cpp>
+==== shuffle ====
-std::vector<int> v1 { 1, 2, 3, 4, 5 };
-// premier élément ?
+<code cpp main.cpp>
-std::vector<int> v2(std::begin(v1), std::begin(v1));
+#include <iostream>
-std::cout << boolalpha << v2.empty() << std::endl; // vide
+#include <string>
+#include <algorithm>
+#include <random>
+int main() {
+    std::string s { "azerty" };
+    std::random_device rd;
+    std::mt19937 g(rd());
+    std::shuffle(begin(s), end(s), g);
+    std::cout << s << std::endl;
+}
+<;/code>
-// premier élément
+affiche par exemple :
-std::vector<int> v3(std::begin(v1), std::begin(v1)+1);
-for (auto i: v3) std::cout << i << ' '; // ok, contient {1}
-// dernier élément ?
+<code>
-std::vector<int> v4(std::end(v1), std::end(v1));
+yazert
-std::cout <&lt; boolalpha << v4.empty() << std::endl; // vide
+</code&gt;
-// dernier élément
-std::vector<int> v5(std::end(v1)-1, std::end(v1));
+==== unique ====
-for (auto i: v5) std::cout << i << ' '; // ok, contient {5}
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::sort(begin(s1), end(s1));
+    auto last = std::unique(begin(s1), end(s1));
+    std::cout << std::string(begin(s1), last) << std::endl;
+}
 </code>
-En pratique, cela signifie que ''end(v)'' ne représente pas le dernier élément d'une collection, mais un élément supplémentaire et imaginaire qui se trouverait après le dernier élément.
+affiche :
-** faire une figure **
+<code>
+0123456789abcdef
+</code>
-===== Tester si une recherche échoue =====
+===== Les algorithmes de partitionnement =====
-Pourquoi cette façon de faire ? Avec ''find'', si aucun élément n'est trouvé, comment indiquer que la recherche a échoué ? Une solution serait que ''find'' retourne un booléen en plus. Mais ce serait compliqué à gérer. La solution choisie est qu'elle retourne ''end()'' si la recherche échoue.
+Les algorithmes de partitionnement (//partitioning operations//) permettent séparer une collection en deux sous-collections.
-Donc tester le résultat de ''find'' :
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::partition(begin(s1), end(s1), isdigit);
+    std::cout << s1 << std::endl;
+}
+</code>
-<code cpp>
+affiche :
-auto p = std::find(begin(v), end(v), 3);
-std::cout << boolalpha << (p == end(v)) << endl;
+<code>
-p = std::find(begin(v), end(v), 10);
+792025669718943476694aeabaefaddcbdecfefe
-std::cout << boolalpha << (p == end(v)) << endl;
 </code>
-Comme ''end(v)'' ne représente pas un élément dans une collection, il est interdit de le manipuler comme les autres positions. Ainsi, il est légal d'écrire ''begin(v)+1'', puisque ''begin(v)'' est une position correspondante à un élément dans la collection (s'il y a au moins un élément dans la collection), on a le droit de le manipuler. Au contraire, ''end(v)+1'' est interdit. C'est pour cela que la notion ''begin(v)+n'' est dangereuse, puisque l'on peut accéder à une position invalide, si ''n > size()''.
-__advance ? next ?__
+===== Les algorithmes de tri =====
-===== Exécuter plusieurs recherches =====
+Les algorithmes de tri (//sorting operations//) permettent de trier les éléments d'une collection.
-Supposons que l'on ait plusieurs fois la même valeur dans une collection. Comment toutes les trouver avec ''find'' ?
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::sort(begin(s1), end(s1));
+    std::cout << s1 << std::endl;
+}
+</code>
-On recherche d'abord sur l'intervalle qui nous intéresse avec ''begin'' et ''end''. Puis, si on trouve un élément (donc si ''p != end''), alors on peut refaire la recherche entre ''p+1'' et ''end'' pour trouver un deuxième élément. Et ainsi de suite, jusqu'à trouver tous les éléments.
+affiche :
+<code>
+012234445666677789999aaaabbccdddeeeeefff
+</code>
-<code cpp>
+===== Les algorithmes binaires de recherche =====
+Les algorithmes binaires de recherche (//binary search operations//) permettent de rechercher un élément dans une collection triée.
+<code cpp main.cpp>
 #include <iostream>
 #include <string>
@@ Ligne 330: / Ligne 570: @@
 int main() {
-    std::string const s { "azertyazerty" };
+    std::string s { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
-    auto position = std::find(std::begin(s), std::end(s), 'e');
+    std::sort(begin(s), end(s));
-    auto const first = std::string(std::begin(s), position);
+    std::cout << s << std::endl;
-    auto const second = std::string(position, std::end(s));
-    std::cout << first << std::endl;
-    std::cout << second << std::endl;
-    position = std::find(position+1, std::end(s), 'e');
+    const auto result = binary_search(begin(s), end(s), 'a');
-    std::cout << std::string(std::begin(s), position) << std::endl;
+    std::cout << std::boolalpha << result << std::endl;
-    std::cout << std::string(position, std::end(s)) << std::endl;
 }
 </code>
@@ Ligne 346: / Ligne 582: @@
 <code>
-az
+012234445666677789999aaaabbccdddeeeeefff
-ertyazerty
+true
-azertyaz
-erty
 </code>
-second ''find'' : recherche à partir du 'e' trouvé
-<note>Pour une collection vide ({} ou ""), il n'y a pas d'élément et ''begin == end''.</note>
+===== Les algorithmes sur les ensembles =====
-===== transform =====
+Les algorithmes sur les ensembles (//set operations//) permettent de manipuler une collection comme un ensemble d’éléments (donc sans élément en double).
-Rôle de cet algorithme : prendre une collection et appliquer une fonction ''fun'' sur chaque élément. Cf. la signature de la documentation. Contrairement aux algorithmes que l'on a déjà vu, il ne faut pas fournir un prédicat (i.e. un foncteur qui retourne un booléen), mais une fonction unaire ou binaire (selon la version de ''transform'' appelée).
-La documentation précise la signature des fonctions :
-<code cpp>
-Ret fun(const Type &a);                  // unaire
-Ret fun(const Type1 &a, const Type2 &b); // binaire
-</code>
-Ce qui est important à comprendre est que les algorithmes peuvent avoir des signatures spécifiques. Il ne faut pas hésiter à consulter la documentation pour savoir la syntaxe exacte à utiliser.
+===== Les algorithmes sur les Tas =====
-Avec les lambda génériques, l'utilisation de ''transform'' est assez proche de ce que l'on a déjà utilisé. Version unaire :
+Les algorithmes sur les Tas (//heap operations//) permettent de manipuler une collection comme un Tas d’éléments.
-<code cpp>
-std::transform(std::begin(v), std::end(v), std::begin(v), [](auto value){ return value + 1; });
-</code>
-incrémente de 1 chaque élément.
+===== Les algorithmes minimum/maximum =====
-Version binaire :
+Les **algorithmes minimum/maximum** permettent de recherche des éléments minimum ou maximum et réaliser des permutations.
-<code cpp>
-std::transform(std::begin(v1), std::end(v1), std::begin(v2), std::begin(v1), [](auto lhs, auto rhs){ return lhs + rhs; });
-</code>
-additionne deux à deux, les éléments des deux vecteurs.
-===== Travaux dirigés =====
-Page de doc : plusieurs catégories d'algorithmes :
+===== Les algorithmes numériques =====
-  * modifiant : l'algo modifie la collection que l'on passe en argument (''sort'', ''transform'', etc.)
+Les **algorithmes numériques** (//numeric operations//) permettent de travailler sur des collections de nombres.
-  * non modifiant : l'algo ne modifie pas la collection (''equal'', ''find'', etc)
-  * partitionning : sépare une collection en sous collections (tous les éléments sont retrouvés dans les sous-collections, sans qu'il y ait de doublon)
-  * sorting et recherche binaire : tris
-  * set, heap,
-  * minmax, numérique
-  * liste d'exos...
-  * ascii art : convertir une image en ASCI ART
+<code cpp main.cpp>
+#include <iostream>
+#include <algorithm>
+#include <vector>
+#include <numeric>
+int main() {
+    std::vector<int> v1(5);
+    std::iota(begin(v1), end(v1), 0);
+    for(const auto i: v1) { std::cout << i << ' '; } std::cout << std::endl;
+    std::cout << std::accumulate(begin(v1), end(v1), 0) << std::endl;
+    const std::vector<int> v2 = { 2, 3, 4, 0, 1 };
+    std::cout << std::inner_product(begin(v1), end(v1), begin(v2), 0) << std::endl;
+    // = 0 * 2 + 1 * 3 + 2 * 4 + 3 * 0 + 4 * 1
+    std::vector<int> v3(v2.size());
+    std::adjacent_difference(begin(v1), end(v1), begin(v3));
+    for(const auto i: v3) { std::cout << i << ' '; } std::cout << std::endl;
+    std::vector<int> v4 { v2 };
+    std::adjacent_difference(begin(v4), end(v4), begin(v4));
+    for(const auto i: v4) { std::cout << i << ' '; } std::cout << std::endl;
+}
+</code>
+affiche :
+<code>
+1 2 3 4
+
+
+1 1 1 1
+1 1 -4 1
+</code>
-^ Chapitre précédent ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ Chapitre suivant ^
+^ [[comparer|Chapitre précédent]] ^ [[programmez_avec_le_langage_c|Sommaire principal]] ^ [[iterateurs|Chapitre suivant]] ^
-{{tag> Cours C++}}

C++, Qt, OpenGL, CUDA

Outils d'utilisateurs

Outils du Site

Différences

Outils de la Page