Différences

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

--- rechercher [2014/09/04 00:20]
gbdivers effacée
+++ 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]] ^
-====== Recherche dans les chaînes ======
-===== Rechercher un caractère =====
+====== Les catégories d'algorithmes standards ======
-La recherche d'un caractère dans une chaîne peut également être réalisée en utilisant des fonctions membres et des fonctions libres (comme pour les fonctions ''begin'' et ''end'' dans le chapitre précédent). C'est le cas de la fonction de base pour faire une recherche : ''find'' (//trouver// en anglais). D'autres fonctions de recherche ne sont utilisable qu'en fonction membre :
+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é).
-  * ''rfind'' recherche à partir de la fin (//reverse find//) ;
+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.
-  * ''find_first_of'' recherche la première occurrence d'un caractère ;
-  * ''find_first_not_of'' recherche la première abscence de caractère ??? ;
-  * ''find_last_of'' recherche la dernière occurrence d'un caractère ??? ;
-  * ''find_last_not_of'' recherche la dernière absence d'un caractère ???.
-D'autres fonctions ne sont utilisables que sous forme de fonction libre (ce sont les algorithmes de la bibliothèque standard) :
+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.
-  * ''count'' pour compter le nombre d'occurrence d'un caractère ;
+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.
-Comme pour les algorithmes de la bibliothèque standard vu dans le chapitre précédent (''std::equal'' et ''std::lexicographical_compare''), il existe également une version de ces algorithmes précédents utilisant un prédicat personnalisé. Cependant, ici, les algorithmes change de nom, mais dans tous les cas, le prédicat est le dernier argument donné.
+===== Les algorithmes non modifiants =====
-  * ''find_if''
+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).
-  * ''find_if_not''
-  * ''count_if''
+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).
+<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>
-===== Vérifier qu'une chaîne contient une sous-chaîne =====
+==== std::all_of, std::any_of et std::none_of ====
+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").
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    const std::string s { "abcDEFf" };
+    std::cout << std::boolalpha;
+    std::cout << std::all_of(begin(s), end(s), isupper) << std::endl;
+    std::cout << std::any_of(begin(s), end(s), isupper) << std::endl;
+    std::cout << std::none_of(begin(s), end(s), isupper) << std::endl;
+}
+</code>
+affiche :
 <code>
-string const s { "une petite phrase" };
+false
-cout << s.find("petite") << endl;
+true
-cout << s.find("totot") << endl;
+false
-cout <&lt; s.find('w') << endl;
+</code&gt;
-cout << s.rfind("petite") << endl;
-// réutilisation de pos
+==== std::count et std::count_if ====
-auto pos { s.find('e') }; // trouve le permier e
-cout << pos << endl;
+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.
-cout << s.find('e', pos) << endl;
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    const std::string s { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::cout << std::count(begin(s), end(s), '7') << std::endl;
+    std::cout << std::count_if(begin(s), end(s), isdigit) << std::endl;
+}
 </code>
-find_first_of : 1 caractère dans une liste de caractères
+affiche :
-find_first_not_of : l'inverse
+<code>
+
+
+</code>
-find_last_of
-find_last_not_of
+==== std::equal ====
-parsing : extraire une information
+Et bien sûr, vous avez déjà vu l'algorithme [[http://en.cppreference.com/w/cpp/algorithm/equal|std::equal]].
-parcourir toutes les correspondances
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    const std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    const std::string s2 { "8cc52221d9bd6a3701c90969bcee91be4810c8d5" };
+    std::cout << std::boolalpha;
+    std::cout << std::equal(begin(s1), end(s1), begin(s2), end(s2)) << std::endl;
+}
+</code>
-token : split une chaîne en sous chaines
+affiche :
+<code>
+false
+</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>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s { "1234567890" };
+    std::fill(begin(s), end(s), 'A');
+    std::cout << s << std::endl;
+    std::fill_n(begin(s), 5, '1');
+    std::cout << s << std::endl;
+}
+</code>
+affiche :
+<code>
+AAAAAAAAAA
+AAAAA
+</code>
+==== std::transform ====
+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).
+La documentation précise la signature des fonctions (in = input = entrée, out = output = sortie) :
+<code cpp>
+// unaire
+TypeOut fun1(const Type &a);
+std::transform(std::begin(in), std::end(in), std::begin(out), fun1);
+// 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>
+Par exemple :
+Version unaire :
+<code cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s { "azerty" };
+    std::transform(begin(s), end(s), begin(s), toupper);
+    std::cout << s << std::endl;
+}
+</code>
+affiche :
+<code>
+AZERTY
+</code>
+Version binaire :
+<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>
+affiche :
+<code>
+-1 4 -3 8
+</code>
+==== std::generate et std::generate_n ====
+avec rand ?
+==== std::remove et std::replace ====
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::remove(begin(s1), end(s1), '7');
+    std::cout << 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>
+affiche :
+<code>
+f9c02b6c9da8943feaea4966ba41d65de2feee7e
+fcbcdafeaeabaddefeea4966ba7417d65de2fe7e
+f9c02b6c9da8943feaea4966ba41d65de2fee...
+fcbcdafeaeabaddefee.....................
+</code>
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <cctype>
+#include <algorithm>
+int main() {
+    std::string s1 { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::replace(begin(s1), end(s1), '7', '.');
+    std::cout << 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>
+affiche :
+<code>
+f9c02b6c9da8943feaea4966ba.41.d65de2fe.e
+f.c..b.c.da....feaea....ba....d..de.fe.e
+f9c02b6c9da8943feaea4966ba.41.d65de2fe.e
+f.c..b.c.da....feaea....ba....d..de.fe.e
+</code>
+==== std::swap etstd::swap_ranges ====
+std::swap ne travaille pas sur des collections en particulier.
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "azerty" };
+    std::string s2 { "123456" };
+    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>
+affiche :
+<code>
+azerty
+</code>
+<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>
+affiche :
+<code>
+rty
+aze456
+</code>
+iter_swap ?
+==== reverse et reverse_copy ====
+<code cpp main.cpp>
+#include <iostream>
+#include <string>
+#include <algorithm>
+int main() {
+    std::string s1 { "azerty" };
+    std::reverse(begin(s1), end(s1));
+    std::cout << s1 << std::endl;
+    const std::string s2 { "azerty" };
+    std::string s3       { "......" };
+    std::reverse_copy(begin(s2), end(s2), begin(s3));
+    std::cout << s3 << std::endl;
+}
+</code>
+affiche :
+<code>
+ytreza
+ytreza
+</code>
+==== rotate ====
+<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>
+affiche :
+<code>
+ertyaz
+ertyaz
+</code>
+==== shuffle ====
+<code cpp main.cpp>
+#include <iostream>
+#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>
+affiche par exemple :
+<code>
+yazert
+</code>
+==== unique ====
+<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>
+affiche :
+<code>
+0123456789abcdef
+</code>
+===== Les algorithmes de partitionnement =====
+Les algorithmes de partitionnement (//partitioning operations//) permettent séparer une collection en deux sous-collections.
+<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>
+affiche :
+<code>
+792025669718943476694aeabaefaddcbdecfefe
+</code>
+===== Les algorithmes de tri =====
+Les algorithmes de tri (//sorting operations//) permettent de trier les éléments d'une collection.
+<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>
+affiche :
+<code>
+012234445666677789999aaaabbccdddeeeeefff
+</code>
+===== 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>
+#include <algorithm>
+int main() {
+    std::string s { "f9c02b6c9da8943feaea4966ba7417d65de2fe7e" };
+    std::sort(begin(s), end(s));
+    std::cout << s << std::endl;
+    const auto result = binary_search(begin(s), end(s), 'a');
+    std::cout << std::boolalpha << result << std::endl;
+}
+</code>
+affiche :
+<code>
+012234445666677789999aaaabbccdddeeeeefff
+true
+</code>
+===== Les algorithmes sur les ensembles =====
+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 =====
+Les algorithmes sur les Tas (//heap operations//) permettent de manipuler une collection comme un Tas d’éléments.
+===== Les algorithmes minimum/maximum =====
+Les **algorithmes minimum/maximum** permettent de recherche des éléments minimum ou maximum et réaliser des permutations.
+===== Les algorithmes numériques =====
+Les **algorithmes numériques** (//numeric operations//) permettent de travailler sur des collections de nombres.
+<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