18.5. Opérations ensemblistes

18.5.1. Opérations d'inclusion

L'inclusion d'un ensemble dans un autre peut être réalisée à l'aide de l'algorithme includes. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2);

template <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2, Compare c);

L'algorithme includes prend en paramètre deux couples d'itérateurs permettant de définir les séquences d'éléments des deux ensembles sur lesquels il doit travailler. La valeur retournée par cet algorithme est true si tous les éléments de la séquence identifiée par les itérateurs premier2 et dernier2 sont également présents dans la séquence identifiée par les itérateurs premier1 et dernier1. L'algorithme considère qu'un élément est présent dans un ensemble s'il existe au moins un élément de cet ensemble qui lui est identique. Chaque élément utilisé de l'ensemble ne l'est qu'une seule fois, ainsi, si l'ensemble dont on teste l'inclusion dispose de plusieurs copies du même élément, il faut qu'il y en ait autant dans l'ensemble conteneur pour que le test d'inclusion soit valide.

Bien entendu, il est possible d'utiliser une autre relation que l'égalité pour déterminer l'appartenance d'un élément à un ensemble, pour cela, il suffit de fournir un foncteur binaire en dernier paramètre. Ce prédicat doit prendre deux éléments en paramètre et renvoyer true si le premier élément est inférieur au second, et false dans le cas contraire.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int t2[3] = {4, 5, 6};
    if (includes(t1, t1+10, t2, t2+3))
        cout << "t1 contient t2" << endl;
    return 0;
}

La complexité de l'algorithme includes est n+m, où n et m sont respectivement les tailles des deux conteneurs qui lui sont fournis en paramètre.

18.5.2. Opérations d'intersection

L'intersection de deux ensembles peut être réalisée à l'aide de l'algorithme set_intersection. Cet algorithme est déclaré de la manière suivante dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_intersection(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);

template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);

Cet algorithme prend en paramètre les itérateurs de début et de fin des deux conteneurs dont l'intersection doit être déterminée, ainsi qu'un itérateur référençant l'emplacement destination où les éléments de l'intersection doivent être stockés. Pour ceux qui le désirent, il est également possible de spécifier un foncteur que l'algorithme utilisera pour effectuer les comparaisons d'infériorité entre les éléments des deux conteneurs fournis en paramètre. Ce foncteur devra bien entendu être compatible avec la relation d'ordre selon laquelle les conteneurs passés en paramètre sont triés.

L'algorithme copie à l'emplacement destination tous les éléments du premier conteneur qui font également partie du deuxième. Le critère d'appartenance à un ensemble est, comme pour l'algorithme includes, le fait qu'il existe au moins un élément dans le deuxième ensemble égal à l'élément considéré. De même, si plusieurs copies d'un même élément se trouvent dans chaque ensemble, le nombre de copies de l'intersection sera le plus petit nombre de copies de l'élément dans les deux ensembles sources.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[10] = {2, 4, 6, 8, 9, 10, 15, 15, 15, 17};
    int t2[10] = {1, 4, 5, 8, 11, 15, 15, 16, 18, 19};
    int t[10];
    // Effectue l'intersection de t1 et de t2 :
    int *fin = set_intersection(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}

La complexité de l'algorithme est n+m, où n et m sont respectivement les tailles des deux conteneurs qui lui sont fournis en paramètre.

18.5.3. Opérations d'union et de fusion

La bibliothèque standard fournit plusieurs algorithmes permettant de réaliser l'union de deux ensembles. Ces variantes se distinguent par la manière qu'elles ont de traiter le cas des éléments en multiples exemplaires.

L'algorithme set_union considère que les éléments équivalents des deux ensembles sont les mêmes entités et ne les place qu'une seule fois dans l'ensemble résultat de l'union. Toutefois, si ces éléments sont en plusieurs exemplaires dans un des ensembles source, ils apparaîtront également en plusieurs exemplaires dans le résultat. Autrement dit, le nombre d'éléments présents dans l'ensemble destination est le nombre maximum du compte de ses occurrences dans chacun des deux ensembles source.

Inversement, l'algorithme merge effectue une union au sens large et ajoute les éléments de chaque ensemble dans l'ensemble résultat sans considérer leurs valeurs. Ainsi, le nombre d'éléments du résultat est strictement égal à la somme des nombres des éléments de chaque conteneur source.

Afin de distinguer ces deux comportements, on peut dire que l'algorithme set_union réalise l'union des deux ensembles, alors que l'algorithme merge réalise leur fusion.

Tous ces algorithmes sont déclarés comme suit dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_union(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);

template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);

template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 dernier2, InputIterator2 premier2,
    OutputIterator destination, Compare c);

Comme vous pouvez le constater, ils prennent tous en paramètre les itérateurs permettant de spécifier les deux ensembles ainsi qu'un itérateur destination indiquant l'emplacement où les éléments de l'union ou de la fusion doivent être stockés. Enfin, si le programmeur le désire, il peut également donner le foncteur définissant la relation d'ordre selon laquelle les ensembles sont triés.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[4] = {1, 2, 5, 5};
    int t2[6] = {3, 4, 5, 5, 5, 7};
    int t[10];
    // Effectue l'union de t1 et de t2 :
    int *fin = set_union(t1, t1+4, t2, t2+6, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Effectue la fusion de t1 et de t2 :
    fin = merge(t1, t1+4, t2, t2+6, t);
    // Affiche le résultat :
    p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}

La bibliothèque standard fournit également une version modifiée de l'algorithme merge dont le but est de fusionner deux parties d'une même séquence d'éléments triées indépendamment l'une de l'autre. Cet algorithme permet d'effectuer la fusion sur place, et ne travaille donc que sur un seul conteneur. Il s'agit de l'algorithme inplace_merge, qui est déclaré comme suit :

template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator premier,
    BidirectionalIterator separation,
    BidirectionalIterator dernier);

template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator premier,
    BidirectionalIterator separation,
    BidirectionalIterator dernier, Compare c);

Cet algorithme effectue la fusion des deux ensembles identifiés respectivement par les itérateurs premier et separation d'une part, et par les itérateurs separation et dernier d'autre part. Enfin, si besoin est, il est possible de spécifier le foncteur selon lequel ces deux ensembles sont triés.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t[10] = {1, 5, 9, 0, 2, 3, 4, 6, 7, 8};
    // Fusionne les deux sous-ensembles de t
    // (la séparation est au troisième élément) :
    inplace_merge(t, t+3, t+10);
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
    {
        cout << t[i] << " ";
    }
    cout << endl;
    return 0;
}

Tous les algorithmes d'union et de fusion ont une complexité n+m, où n et m sont les tailles des deux ensembles à fusionner ou à réunir.

18.5.4. Opérations de différence

La différence entre deux ensembles peut être réalisée avec l'algorithme set_difference. Cet algorithme supprime du premier ensemble tous les éléments du second, si nécessaire. Chaque élément n'est supprimé qu'une seule fois, ainsi, si le premier ensemble contient plusieurs éléments identiques et que le deuxième ensemble en contient moins, les éléments résiduels après suppression seront présents dans la différence.

La bibliothèque standard fournit également un algorithme de suppression symétrique, l'algorithme set_symmetric_difference, qui construit un nouvel ensemble contenant tous les éléments des deux ensembles qui ne se trouvent pas dans l'autre. Il s'agit en fait de l'union des deux différences des deux ensembles.

Les algorithmes set_difference et set_symmetric_difference sont déclarés comme suit dans l'en-tête algorithm :

template <class InputIterator1, class InputIterator2,
    class OutputIterator>
OutputIterator set_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination);

template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(
    InputIterator1 premier, InputIterator1 dernier,
    InputIterator2 premier, InputIterator2 dernier2,
    OutputIterator destination);

template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
    InputIterator1 premier1, InputIterator1 dernier1,
    InputIterator2 premier2, InputIterator2 dernier2,
    OutputIterator destination, Compare c);

Ils prennent tous deux paires d'itérateurs identifiant les deux ensembles dont la différence doit être calculée ainsi qu'un itérateur référençant l'emplacement destination dans lequel le résultat doit être placé. Comme à l'accoutumée, il est possible d'indiquer le foncteur permettant à l'algorithme de réaliser les tests d'infériorité entre deux éléments et selon lequel les ensembles sont triés. La complexité de ces algorithmes est n+m, où n et m sont les nombres d'éléments des deux ensembles sur lesquels les algorithmes opèrent.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int t1[10] = {0, 1, 5, 7, 7, 7, 8, 8, 9, 10};
    int t2[10] = {0, 2, 3, 7, 9, 11, 12, 12, 13, 14};
    int t[20];
    // Calcule la différence de t1 et de t2 :
    int *fin = set_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Calcule la différence symétrique de t1 et t2 :
    fin = set_symmetric_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    int *p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    // Calcule la différence symétrique de t1 et t2 :
    fin = set_symmetric_difference(t1, t1+10, t2, t2+10, t);
    // Affiche le résultat :
    p = t;
    while (p != fin)
    {
        cout << *p << " ";
        ++p;
    }
    cout << endl;
    return 0;
}

18.5.5. Opérations de partitionnement

L'algorithme partition de la bibliothèque standard permet de séparer les éléments d'un ensemble en deux sous-ensembles selon un critère donné. Les éléments vérifiant ce critère sont placés en tête de l'ensemble, et les éléments qui ne le vérifient pas sont placés à la fin. Cet algorithme est déclaré comme suit dans l'en-tête algorithm :

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator premier,
    ForwardIterator dernier, Predicate p);

Les paramètres qui doivent être fournis à cet algorithme sont les itérateurs référençant le premier et le dernier élément de l'ensemble à partitionner, ainsi qu'un foncteur unaire permettant de déterminer si un élément vérifie le critère de partitionnement ou non. La valeur retournée est la position de la séparation entre les deux sous-ensembles générés par l'opération de partition.

#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

bool parity_even(int i)
{
    return (i & 1) == 0;
}

int main(void)
{
    int t[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    // Partitionne le tableau en nombre pairs
    // et nombre impairs :
    partition(t, t+10, ptr_fun(&parity_even));
    // Affiche le résultat :
    int i;
    for (i=0; i<10; ++i)
        cout << t[i] << " ";
    cout << endl;
    return 0;
}

La complexité de l'algorithme partition est linéaire en fonction du nombre d'éléments de l'ensemble à partitionner. Cependant, l'opération de partitionnement n'est pas stable, c'est-à-dire que l'ordre relatif des éléments de même valeur et sur lesquels le prédicat du critère de partitionnement donne le même résultat n'est pas conservé. La bibliothèque standard fournit donc un autre algorithme, stable celui-là, mais qui s'exécute avec une complexité légèrement supérieure. Il s'agit de l'algorithme stable_partition, qui est déclaré comme suit dans l'en-tête algorithm :

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator premier,
    ForwardIterator dernier, Predicate p);

Comme vous pouvez le constater, cet algorithme s'utilise exactement de la même manière que l'algorithme partition. Toutefois, il garantit l'ordre relatif des éléments au sein des sous-ensembles générés par l'opération de partitionnement. La complexité de cet algorithme est n s'il dispose de suffisamment de mémoire, et n×ln(n) dans le cas contraire (n étant la taille de l'ensemble à partitionner).