2. C++ Avancé




2.8. Les Algorithmes de la STL

Les algorithmes de la STL sont des fonctions qui agissent sur les containers.

On distingue les algorithmes :

2.8.1. count, count_if

count permet de compter le nombre de valeurs égales à une constante, count_if permet d'utiliser un prédicat (fonction) pour déterminer si chaque valeur du container vérifie un critère donné.

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. bool is_even(int x) {
  9.     return ((x % 2) == 0);
  10. }
  11.  
  12. int main() {
  13.  
  14.     vector<int> v { 1, 2, 3, 2, 5, 3, 7, 4, 9, 10 };
  15.    
  16.     int how_many_2 = count(v.begin(), v.end(), 2);
  17.     cout << "the value 2 appears " << how_many_2 << " times" << endl;
  18.    
  19.     int how_many_even = count_if(v.begin(), v.end(), is_even);
  20.     cout << "there are " << how_many_even << " even numbers" << endl;
  21.     return 0;
  22. }
  23.  
the value 2 appears 2 times
there are 4 even numbers

2.8.2. find

find permet de trouver la position (itérateur) d'une valeur constante, find_if permet d'utiliser un prédicat (fonction) pour déterminer la position de la valeur qui vérifie un critère donné.

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. bool is_divisible_by_7(int x) {
  9.     return ((x % 7) == 0);
  10. }
  11.  
  12. int main() {
  13.  
  14.     vector<int> v { 1, 2, 3, 2, 5, 3, 14, 4, 9, 10 };
  15.    
  16.     vector<int>::iterator position;
  17.    
  18.     position = find(v.begin(), v.end(), 5);
  19.     if (position == v.end()) {
  20.         cout << "the value 5 was not found" << endl;
  21.     } else {
  22.         cout << "the value 5 was found at position " << position-v.begin() << endl;
  23.     }
  24.    
  25.     position = find_if(v.begin(), v.end(), is_divisible_by_7);
  26.     if (position == v.end()) {
  27.         cout << "no value is divisible by 7" << endl;
  28.     } else {
  29.        
  30.         cout << "the value " << *position << " at " << position-v.begin()
  31.             << " is divisible by 7" << endl;
  32.     }
  33.    
  34.     return 0;
  35. }
  36.  
the value 5 was found at position 4
the value 14 at 6 is divisible by 7

Note : certains containers (set, map) fournissent une methode find() qui est plus efficace que l'algorithme générique find.

2.8.3. for_each

for_each applique une fonction à chaque élément du container. Attention l'algorithme devient mutable si la fonction utilise une référence à la valeur &.

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. void print_cube(int x) {
  9.     cout << (x*x*x) << " ";
  10. }
  11.  
  12. void increase(int &n) {
  13.     n += 10;
  14. }
  15.  
  16. int main() {
  17.  
  18.     vector<int> v { 1, 2, 3, 4, 5 };
  19.    
  20.     // print each element to the cube
  21.     for_each(v.begin(), v.end(), print_cube);
  22.     cout << endl;
  23.    
  24.     // increase all elements by 10
  25.     // Note that increase uses a reference to n to allow the modification
  26.     for_each(v.begin(), v.end(), increase);
  27.    
  28.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  29.     cout << endl;
  30.    
  31.     return 0;
  32. }
  33.  
1 8 27 64 125 
11 12 13 14 15

2.8.4. max_element, min_element, min_max_element (C++11)

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. // ----------------------------------------------
  8. // function used to generate random numbers
  9. // between 0 and 99
  10. // ----------------------------------------------
  11. int my_generator() {
  12.     return rand() % 100;
  13. }
  14.  
  15. // ----------------------------------------------
  16. // main function
  17. // ----------------------------------------------
  18. int main() {
  19.     srand(19702013);
  20.    
  21.     // must define the size of the vector
  22.     vector<int> v(20);
  23.    
  24.     // call user-defined function
  25.     generate(v.begin(), v.end(), my_generator);
  26.    
  27.     // print vector contents
  28.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  29.     cout << endl;
  30.    
  31.     vector<int>::iterator it;
  32.    
  33.     // find minimum element
  34.     it = min_element(v.begin(), v.end());
  35.     cout << "minimum = " << (*it) << endl;
  36.  
  37.     // find maximum element
  38.     it = max_element(v.begin(), v.end());
  39.     cout << "maximum = " << (*it) << endl;
  40.    
  41.     // C++11 minmax_element
  42.     pair<vector<int>::iterator, vector<int>::iterator> result;
  43.     result = minmax_element(v.begin(), v.end());
  44.     cout << "with minmax_elmeent C++11: " << endl;
  45.     cout << "minimum = " << *(result.first) << endl;
  46.     cout << "maximum = " << *(result.second) << endl;
  47.    
  48.    
  49.     return 0;
  50. }
  51.  
36 98 7 18 53 37 91 86 26 60 10 32 3 75 20 14 20 14 5 59 
minimum = 3
maximum = 98
with minmax_elmeent C++11: 
minimum = 3
maximum = 98

2.8.5. accumulate

L'algorithme accumulate réalise la somme des éléments du container.

On peut aussi l'utiliser avec une fonction à deux arguments pour réaliser un produit.

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. int product(int x, int y) {
  9.     return x * y;
  10. }
  11.  
  12. int main() {
  13.  
  14.     vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  15.    
  16.     int sum = accumulate(v.begin(), v.end(), 0);
  17.    
  18.     cout << "sum = " << sum << endl;
  19.    
  20.     int computed = v.size() * (v.size() + 1) / 2;
  21.    
  22.     cout << "computed = " << computed << endl;
  23.    
  24.     // factorial
  25.     int prod = accumulate(v.begin(), v.end(), 1, product);
  26.    
  27.     cout << "product = " << prod << endl;
  28.    
  29.     return 0;
  30. }
  31.  
sum = 55
computed = 55
product = 3628800

2.8.6. generate

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. // ----------------------------------------------
  8. // function used to generate random numbers
  9. // between 0 and 19
  10. // ----------------------------------------------
  11. int my_generator() {
  12.     return rand() % 20;
  13. }
  14.  
  15. // ----------------------------------------------
  16. // main function
  17. // ----------------------------------------------
  18. int main() {
  19.     srand(19702013);
  20.    
  21.     // must define the size of the vector
  22.     vector<int> v(20);
  23.    
  24.     // call existing function
  25.     generate(v.begin(), v.end(), ::rand);
  26.    
  27.     // call user-defined function
  28.     generate(v.begin(), v.end(), my_generator);
  29.    
  30.     // call lambda user-defined function
  31.     generate(v.begin(), v.end(), []() {
  32.         return  rand() % 20;
  33.     });
  34.    
  35.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  36.     cout << endl;
  37.    
  38.     return 0;
  39. }
  40.  

2.8.7. reverse

Permet d'inverser le contenu du container :

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. int main() {
  8.     srand(19702013);
  9.    
  10.     // must define the size of the vector
  11.     vector<int> v(20);
  12.    
  13.     // call existing function
  14.     generate(v.begin(), v.end(), []() {
  15.         return ::rand() % 20;
  16.     });
  17.    
  18.     // initial data
  19.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  20.     cout << endl;
  21.  
  22.    
  23.     // reverse data
  24.     reverse(v.begin(), v.end());
  25.    
  26.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  27.     cout << endl;
  28.    
  29.     return 0;
  30. }
  31.  
16 18 7 18 13 17 11 6 6 0 10 12 3 15 0 14 0 14 5 19 
19 5 14 0 14 0 15 3 12 10 0 6 6 11 17 13 18 7 18 16

2.8.8. sort

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. int main() {
  8.     srand(19702013);
  9.    
  10.     // must define the size of the vector
  11.     vector<int> v(20);
  12.    
  13.     // call existing function
  14.     generate(v.begin(), v.end(), []() {
  15.         return ::rand() % 20;
  16.     });
  17.    
  18.     // initial data
  19.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  20.     cout << endl;
  21.  
  22.     // sort data
  23.     sort(v.begin(), v.end());
  24.    
  25.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  26.     cout << endl;
  27.    
  28.     // sort in reverse order
  29.     sort(v.begin(), v.end(), std::greater<int>());
  30.    
  31.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  32.     cout << endl;
  33.    
  34.     return 0;
  35. }
  36.  
16 18 7 18 13 17 11 6 6 0 10 12 3 15 0 14 0 14 5 19 
0 0 0 3 5 6 6 7 10 11 12 13 14 14 15 16 17 18 18 19 
19 18 18 17 16 15 14 14 13 12 11 10 7 6 6 5 3 0 0 0

2.8.9. transform

  1. #include <vector>
  2. #include <algorithm>
  3. #include <iterator>
  4. #include <iostream>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. int my_generator() {
  9.     return rand() % 20;
  10. }
  11.  
  12. // main
  13. int main() {
  14.     srand(19702013);
  15.    
  16.     // must define the size of the vector
  17.     vector<int> v(20);
  18.    
  19.     // call user-defined function to generate values
  20.     generate(v.begin(), v.end(), my_generator);
  21.  
  22.     // print contents of v
  23.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  24.     cout << endl;
  25.    
  26.     // compute average
  27.     float average1 = static_cast<float>(accumulate(v.begin(), v.end(), 0));
  28.     average1 /= v.size();
  29.    
  30.     cout << "average1 = " << average1 << endl;
  31.    
  32.     // use a user-defined transformer
  33.     transform(v.begin(), v.end(), v.begin(), negate<int>());
  34.  
  35.     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
  36.     cout << endl;
  37.  
  38.     float average2 = static_cast<float>(accumulate(v.begin(), v.end(), 0));
  39.     average2 /= v.size();
  40.    
  41.     cout << "average2 = " << average2 << endl;
  42.    
  43.    
  44.     return 0;
  45. }
  46.  
16 18 7 18 13 17 11 6 6 0 10 12 3 15 0 14 0 14 5 19 
average1 = 10.2
-16 -18 -7 -18 -13 -17 -11 -6 -6 0 -10 -12 -3 -15 0 -14 0 -14 -5 -19 
average2 = -10.2