Les algorithmes
Les algorithmes offerts par la STL regroupent la plupart des opérations que l'on pourrait avoir à réaliser sur des ensembles.
L'accès aux données des conteneurs s'effectue par le biais des itérateurs
Avant d'aller plus loin dans la présentation des algorithmes, je voudrais vous sensibiliser sur le fait que, plus qu'une simple bibliothèque d'outils, le type d'implémentation choisi est le parfait exemple de ce qu'un programmeur devrait toujours faire:
Le fait de complètement séparer les opérations des données réelles assure une parfaite réutilisabilité du code. Pour aller plus loin et sans parler de réutilisabilité, ce type de programmation assure de manière quasi optimale un couplage extrèmement faible entre les classes utilisées.
Si on veut changer d'algorithme, on le change sans modifier le reste. De même, si le conteneur ne nous satisfait plus, on le change sans toucher à l'algorithme.
Il faut voir par là que c'est la présence d'une int;sence d'une interface entre ces deux notions qui rend tout possible. Merci les itératuers!
Revenons en à la STL
Pour avoir une liste détaillée de tous les algorithmes proposés, jeter un coup d'oeil au fichier "algo.h". Pour les principaux, la suite de la page en commente quelques uns des plus utiles et des plus utilisés.
Les algorithmes sont regroupés en quatre grandes famildes familles:
- les "non-mutating", qui effectuent des opérations sur les conteneurs sans transformations
- les "mutating", qui modifient la séquence
A propos des algorithmes de la STL, il n'y a rien d'autre à dire que le fait qu'ils sont mieux écrits que ce que l'on pourrait faire. Dans le cas improbable où leur implémentation ne vous conviendrait pas, libre à vous d'en créer de nouveaux qui répondront mieux à vos attentes, en gardant à l'esprit que le but du jeu est de respecter au maximum le schéma de la STL, à savoir passer par des itérateurs sans avoir connaîssance du conteneur.
Prototype
template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f);Description
For_each applique le foncteur f à chaque élément de l'ensembe first->last. Retourne le foncteur après qu'il ait été appliqué à tous les éléments
Complexité linéaireExemple
L'exemple suivant nous permet d' afficher le contenu d'une séquence à l'aide de l'outil d'enumération "for_each"
// Une simple fonction d'affichage
//On devrait plutôt utiliser un foncteur
f="./Foncteurs.htm">foncteur
void print(int a)
{
cout << a << ' ';
}
void main(){
int numbers[] = { 1, 8, 8, 13, 8, 55 };
const int ARRSIZE = sizeof(numbers) / sizeof(numbers[0]);vector<int> vnums(numbers, numbers + ARRSIZE);
// affiche le contenu de chacune des 2 sequences
for_each(numbers, numbers + ARRSIZE, print);
cout << endl;
for_each(vnums.begin(), vnums.end(), print);
cout << endl;
ndl;
}
Prototype
template <class InputIterator, class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last, const EqualityComparable& value);Description
Retourne le premier itérateur i de l'ensemble first->last tel que *i==value. Retourne last si aucune réponse
Complexité linéaireFind existe aussi sous des formes dérivées : find_if, adjacent_find, find_first_of, find_end
Exemple
list<int> L;
L.push_back(3);
L.push_back(1);
L.push_back(7);list<int>::iterator result = find(L.begin(), L.end(), 7);
assert(result == L.end() || *result == 7); // 2 facons de verifier le resultat
Prototype
Count est surchargé et possède 2 prototypes:
template <class InputIterator, class EqualityComparable>
iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const EqualityComparable& value);template <class InputIterator, class EqualityComparable, class Size>
void count(InputIterator first, InputIterator last, const EqualityComparable& value, Size& n);Description
Count compte le nombre d'éléments quie nombre d'éléments qui sont égaux à value dans l'ensemble first->last. La première version renvoit ce nombre, la deuxième l' ajoute à n
Complexité linéaire
Existe aussi sous la forme count_if
Exemple
int main() {
int A[] = { 2, 0, 4, 6, 0, 3, 1, -7 };
const int N = sizeof(A) / sizeof(int);cout << "Nombre de zeros: "
<< count(A, A + N, 0)
<< endl;
}
Prototype
Equal est surchargé et possède 2 prototypes:
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);Description
Equal retourne vrai si les ensembles first1->last1 et first2->last2 sont identiques élément par élément sinon retourne faux.
La première version regarde le contenu des itérateurs
La deuxième version effectue le test d'égalité par rapport au prédicat donné en paramêtre
Complexité linéaire ( au pire )
Existe sore ( au pire )
Existe sous la forme search (qui cherche la sous-séquence first2->last2 dans l'ensemble first1->last1), search_n
Prototype
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator Iterator result);Description
Copy copie les éléments de l'ensemble first->last vers l'ensemble result->result+first-last. Retourne l'itérateur sur le dernier élement de l'ensemble copié
Complexité linéaire
Existe sous les formes copy_n, copy_backward, unique_copy, reverse_copy, rotate_copy
Exemple
Copie le contenu d'un tableau sur la sortie standard
int main() {
int numbers[] = { 1, 8, 8, 13, 8, 55 };
const int ARRSIZE = sizeof(numbers) / sizeof(numbers[0]);const vector<int> basenums(numbers, numbers + ARRSIZE);
vector<int> vnums;ostream_iterator<int> out(cout, " ");
copy(vnums.begin(), vnums.end(), out);
cout << '\n';
}
Prototype
template <class Assignable>
void swap(Assigna
void swap(Assignable& a, Assignable& b);Description
Intervertit les contenus de a et de b. Cet algorithme est à la base de la plupart des autres!!!
Existe sous la forme iter_swap, swap_ranges
Prototype
Transform est surchargé et possède 2 prototypes:
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op);
template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op);Description
Transform applique l'opération op sur chacun des éléments de l'ensemble first->last et écrit les résultats à partir de l'élément result
La première version permet d'appliquer une fonction unaire, la deuxième une fonction binaire prenant deux paramêtres en entrée.
Complexité linéaire
Exemple
iota() est un algorithme numerique permettant d'initialiser le tableau ( 1ere case a 1, 2eme a 2, ... )
negate est un foncteur, qui renvoit la négation de l'objet passé en parametre ( ici chaque entier du tableau )const int N = 1000;
double A[N];
iota(A, A+N, 1);transform(A, A+N, A, negate<double>());
Prototype
Sort est surchargé et possède 2 prototypes: template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);Description
Sort trie les éléments de l'ensemble first->last de facon ascendante.
Dans la première version , les éléments doivent être comparables ( opérateur < défini )
Dans la deuxième, la façon de comparer est donnée par la fonction comp.
Complexité en O(n log n)
Prototype
Merge est surchargé et possède 2 prototypes:
template <class InputIterator1, class InputIterator2, class OutputIterator>
ator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);Description
Merge combine les deux ensembles first1->last1 et first2->last2 à partir de l'itérateur result. Les deux ensembles doivent être triés
Dans la première version , les éléments doivent être comparables ( opérateur < défini )
Dans la deuxième, la façon de comparer est donnée par la fonction comp.
Retourne le dernier élément copié
Complexité linéaire
&nlockquote>
Prototype
Accumulate est surchargé et possède 2 prototypes:
template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);Description
Accumulate est une version généralisé de la sommation
Accumulate initialise le résultat à init et y ajoute la valeur de chacun des élément de l'ensemble first->last
Dans la deuxième version, l'addition effectuée par défaut est remplacée par la fonction binary_op ( result + = binary_op(result, i); )
Complexité linéexité linéaire
Prototype
template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value);Description
Iota assigne une valeur qui augmente séquentiellement à l'ensemble first->last
l'algorithme est en gros: while (first != last) *first++ = value++;
Complexité linéaire
Prototype
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);Description
Fill remplit chaque élément de l'ensemble first->last avec la valeur value
Complexité linéaire
| << Précédent |