2. C++ Avancé




2.6. Les Containers STL

Un container est une structure de données qui permet de stocker des éléments de même type.

Au sein de la STL on distingue :

2.6.1. array (C++11)

Il permet de modéliser les tableaux de taille constante.

  1. #include <array>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <iterator>
  5. using namespace std;
  6.  
  7. int main() {
  8.     array<int, 10> a;
  9.        
  10.     a.fill(2);
  11.     int sum = 0;
  12.     for (int i=0; i<a.size(); ++i) {
  13.         sum += a[i];
  14.     }
  15.    
  16.     cout << "sum = " << sum << endl;
  17.        
  18.     return 0;
  19. }
  20.  
  21.  

2.6.2. valarray (C++11)

std::valarray and helper classes are defined to be free of certain forms of aliasing, thus allowing operations on these classes to be optimized similar to the effect of the keyword restrict in the C programming language. In addition, functions and operators that take valarray arguments are allowed to return proxy objects to make it possible for the compiler to optimize an expression such as v1 = a*v2 + v3; as a single loop that executes v1[i] = a*v2[i] + v3[i]; avoiding any temporaries or multiple passes.

source cppreference.com/valarray

L'utilisation de valarray se révèle assez différente des autres containers :

  1. #include <iostream>
  2. #include <valarray>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8.  
  9. void test_1() {
  10.     cout << "====== TEST 1 ======" << endl;
  11.    
  12.     // create valarray with initial values
  13.     valarray<float> v(10);
  14.     for (size_t i=0; i<v.size(); ++i) v[i] = sin(i * 4.0);
  15.     for (auto x : v) cout << x << " ";
  16.     cout << endl;
  17.    
  18.     // compute sum, min, max
  19.     cout << "sum = " << v.sum() << endl;
  20.     cout << "min = " << v.min() << endl;
  21.     cout << "max = " << v.max() << endl;
  22.        
  23.    
  24.    
  25.     // define mask_array to be all values greater than 0
  26.     valarray<bool> mask = v > 0.0f;
  27.    
  28.     for (auto x : mask) cout << x << " ";
  29.     cout << endl;
  30.    
  31.     // use mask_array to select values from v and put them
  32.     // in variable 'selected'
  33.     valarray<float> selected = v[mask];
  34.     for (auto x : selected) cout << x << " ";
  35.     cout << endl;
  36.    
  37.     // apply square root on selected values
  38.     valarray<float> vs = sqrt(selected);
  39.     for (auto x : vs) cout << x << " ";
  40.     cout << endl;
  41. }
  42.  
  43. void test_2() {
  44.     cout << "====== TEST 2 ======" << endl;
  45.    
  46.     valarray<double> v1(10), v2(10), v3(10);
  47.    
  48.     for (size_t i=0; i<v1.size(); ++i) {
  49.         v1[i] = i;
  50.         v2[i] = i*i;
  51.     }
  52.    
  53.     v3 = v1 + v2;
  54.    
  55.     for (auto x : v3) cout << x << " ";
  56.     cout << endl;
  57.    
  58. }
  59.  
  60. int main() {
  61.     test_1();
  62.     test_2();  
  63.    
  64.     return EXIT_SUCCESS;
  65. }
  66.  
====== TEST 1 ======
0 -0.756802 0.989358 -0.536573 -0.287903 0.912945 -0.905578 0.270906 0.551427 -0.991779 
sum = -0.754
min = -0.991779
max = 0.989358
0 0 1 0 0 1 0 1 1 0 
0.989358 0.912945 0.270906 0.551427 
0.994665 0.955482 0.520486 0.742581 
====== TEST 2 ======
0 2 6 12 20 30 42 56 72 90

2.6.3. vector

Il permet de modéliser les tableaux de taille variable. Il peut être manipulé comme un tableau ou une pile.

  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <iterator>
  5. using namespace std;
  6.  
  7. /**
  8.  * insert values in to vector and compute sum
  9.  */
  10. void test_1() {
  11.     vector<int> v;
  12.        
  13.     for (int i=0; i<10; ++i) {
  14.         v.push_back(i+1);
  15.     }
  16.    
  17.     int sum = 0;
  18.     for (int i=0; i<v.size(); ++i) {
  19.         sum += v[i];
  20.     }
  21.    
  22.     cout << "sum = " << sum << endl;
  23. }
  24.  
  25. /**
  26.  * create initial vector with 10 values and modify
  27.  */
  28. void test_2() {
  29.     vector<int> v(10);
  30.    
  31.     // 0 0 0 0 0 0 0 0 0 0
  32.     fill(v.begin(), v.end(), 0);
  33.    
  34.     // 1 1 1 1 1 0 0 0 0 0
  35.     fill_n(v.begin(), 5, 1);
  36.    
  37.     // C++11
  38.     // 1 2 3 4 5 6 7 8 9 10
  39.     iota(v.begin(), v.end(), 1);
  40.  
  41.     // 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0
  42.     v.resize(20);
  43.    
  44.     // 1 2 3 4 5 6 7 8 9 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  45.     fill(v.begin() + 10, v.end(), -1);
  46.    
  47. }
  48.  
  49. /**
  50.  * main function
  51.  */
  52. int main() {
  53.     test_1();
  54.     test_2();  
  55.     return 0;
  56. }
  57.  
  58.  

2.6.4. list

le container list permet de modéliser une liste d'éléments. Il peut être manipulé comme un tableau ou une pile.


Warning: file_get_contents(ens/inra/c2_stl_cont_list.cpp): Failed to open stream: No such file or directory in /home/jeanmichel.richer/public_html/html_business.php on line 488
  1.  

2.6.5. set

container associatif qui stocke de manière unique les éléments. Les éléments sont rangés par ordre croissant par défaut. On peut spécifier une fonction de tri utilisée pour l'insertion d'un nouvel élément.

  1. #include <vector>
  2. #include <set>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <iterator>
  6. using namespace std;
  7.  
  8. /**
  9.  * new ordering with reverse order
  10.  */
  11. struct Ordering {
  12.     bool operator()(int a, int b) {
  13.         return a > b;
  14.     }
  15. };
  16.  
  17.  
  18. /**
  19.  * main function
  20.  */
  21. int main() {
  22.     vector<int> v;
  23.    
  24.     srand(19702013);
  25.    
  26.     // -------------------------------------------
  27.     // fill vector with random values between 0 and 19 
  28.     for (int i=0; i<100; ++i) {
  29.         v.push_back(rand() % 20);
  30.     }
  31.    
  32.     // -------------------------------------------
  33.     // print vector
  34.     cout << "v = [";
  35.     for (int i=0; i<v.size(); ++i) {
  36.         cout << v[i] << " ";
  37.     }
  38.     cout << "]" << endl;
  39.    
  40.     // -------------------------------------------
  41.     // create set from vector
  42.     set<int> s1(v.begin(), v.end());
  43.  
  44.     cout << "s1 = {";
  45.     copy(s1.begin(), s1.end(), ostream_iterator<int>(cout, " "));
  46.     cout << "}" << endl;   
  47.  
  48.     // ------------------------------------------- 
  49.     // create set from vector with specific ordering
  50.     set<int, Ordering> s2(v.begin(), v.end());
  51.    
  52.     cout << "s2 = {";
  53.     copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " "));
  54.     cout << "}" << endl;   
  55.        
  56.     return 0;
  57. }
  58.  
  59.  
v = [16 18 7 18 13 17 11 6 6 0 10 12 3 15 0 14 0 14 5 19 5 10 6 19 9 10 9 5 0 0 8 16 19 7 6 12 4 10 18 2 10 0 15 6 7 7 0 7 13 17 18 18 19 4 17 9 7 6 6 7 19 7 3 18 14 1 10 11 11 0 13 14 0 8 12 19 7 12 7 1 2 5 19 1 2 9 2 9 7 1 16 6 8 11 4 2 4 6 13 16 ]
s1 = {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 }
s2 = {19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 }

2.6.6. map

container associatif qui stocke de manière unique les éléments sous forme d'une clé et d'une valeur (paire).

  1. #include <vector>
  2. #include <map>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <iterator>
  6. using namespace std;
  7.  
  8. /**
  9.  * new ordering : reverse order
  10.  */
  11. struct Ordering {
  12.     bool operator()(int a, int b) {
  13.         return a > b;
  14.     }
  15. };
  16.  
  17.  
  18. /**
  19.  * main function
  20.  */
  21. int main() {
  22.     vector<int> v;
  23.    
  24.     srand(19702013);
  25.    
  26.     // -------------------------------------------
  27.     // fill vector with random values between 0 and 19 
  28.     for (int i=0; i<100; ++i) {
  29.         v.push_back(rand() % 20);
  30.     }
  31.    
  32.     // -------------------------------------------
  33.     // print vector
  34.     cout << "v = [";
  35.     for (int i=0; i<v.size(); ++i) {
  36.         cout << v[i] << " ";
  37.     }
  38.     cout << "]" << endl;
  39.    
  40.     // -------------------------------------------
  41.     // create map  to count number of occurrences
  42.     // of each value
  43.     // key = integer value,
  44.     // value = #occurrences in v
  45.     map<int, int> m;
  46.     map<int,int>::iterator it;
  47.    
  48.     for (int i = 0; i<v.size(); ++i) {
  49.         it = m.find(v[i]);
  50.         if (it == m.end()) {
  51.             m[ v[i] ] = 0;
  52.         }
  53.         ++m[ v[i] ];
  54.     }      
  55.    
  56.     for (it = m.begin(); it != m.end(); ++it) {
  57.         cout << (*it).first << " appears " << (*it).second << " times" << endl;
  58.     }
  59.    
  60.     return 0;
  61. }
  62.  
  63.  
v = [16 18 7 18 13 17 11 6 6 0 10 12 3 15 0 14 0 14 5 19 5 10 6 19 9 10 9 5 0 0 8 16 19 7 6 12 4 10 18 2 10 0 15 6 7 7 0 7 13 17 18 18 19 4 17 9 7 6 6 7 19 7 3 18 14 1 10 11 11 0 13 14 0 8 12 19 7 12 7 1 2 5 19 1 2 9 2 9 7 1 16 6 8 11 4 2 4 6 13 16 ]
0 appears 9 times
1 appears 4 times
2 appears 5 times
3 appears 2 times
4 appears 4 times
5 appears 4 times
6 appears 9 times
7 appears 11 times
8 appears 3 times
9 appears 5 times
10 appears 6 times
11 appears 4 times
12 appears 4 times
13 appears 4 times
14 appears 4 times
15 appears 2 times
16 appears 4 times
17 appears 3 times
18 appears 6 times
19 appears 7 times