17.2. Les séquences

17.2.1.1. Construction et initialisation

La construction et l'initialisation d'une séquence peuvent se faire de multiples manières. Les séquences disposent en effet de plusieurs constructeurs et de deux surcharges de la méthode assign qui permet de leur affecter un certain nombre d'éléments. Le constructeur le plus simple ne prend aucun paramètre, hormis un allocateur standard à utiliser pour la gestion de la séquence, et permet de construire une séquence vide. Le deuxième constructeur prend en paramètre le nombre d'éléments initial de la séquence et la valeur de ces éléments. Ce constructeur permet donc de créer une séquence contenant déjà un certain nombre de copies d'un objet donné. Enfin, le troisième constructeur prend deux itérateurs sur une autre séquence d'objets qui devront être copiés dans la séquence en cours de construction. Ce constructeur peut être utilisé pour initialiser une séquence à partir d'une autre séquence ou d'un sous-ensemble de séquence.

Les surcharges de la méthode assign se comportent un peu comme les deux derniers constructeurs, à ceci près qu'elles ne prennent pas d'allocateur en paramètre. La première méthode permet donc de réinitialiser la liste et de la remplir avec un certain nombre de copies d'un objet donné, et la deuxième permet de réinitialiser la liste et de la remplir avec une séquence d'objets définie par deux itérateurs.

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " " ;
        ++i;
    }
    cout << endl;
}

int main(void)
{
    // Initialise une liste avec trois éléments valant 5 :
    li l1(3, 5);
    print(l1);
    // Initialise une autre liste à partir de la première
    // (en fait on devrait appeler le constructeur de copie) :
    li l2(l1.begin(), l1.end());
    print(l2);
    // Affecte 4 éléments valant 2 à l1 :
    l1.assign(4, 2);
    print(l1);
    // Affecte l1 à l2 (de même, on devrait normalement
    // utiliser l'opérateur d'affectation) :
    l2.assign(l1.begin(), l1.end());
    print(l2);
    return 0;
}

Bien entendu, il existe également un constructeur et un opérateur de copie capables d'initialiser une séquence à partir d'une autre séquence du même type. Ainsi, il n'est pas nécessaire d'utiliser les constructeurs vus précédemment ni les méthodes assign pour initialiser une séquence à partir d'une autre séquence de même type.

17.2.1.2. Ajout et suppression d'éléments

L'insertion de nouveaux éléments dans une séquence se fait normalement à l'aide de l'une des surcharges de la méthode insert. Bien entendu, il existe d'autres méthodes spécifiques à chaque conteneur de type séquence et qui leur sont plus appropriées, mais ces méthodes ne seront décrites que dans les sections consacrées à ces conteneurs. Les différentes versions de la méthode insert sont récapitulées ci-dessous :

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " " ;
        ++i;
    }
    cout << endl;
    return ;
}

int main(void)
{
    li l1;
    // Ajoute 5 à la liste :
    li::iterator i = l1.insert(l1.begin(), 5);
    print(l1);
    // Ajoute deux 3 à la liste :
    l1.insert(i, 2, 3);
    print(l1);
    // Insère le contenu de l1 dans une autre liste :
    li l2;
    l2.insert(l2.begin(), l1.begin(), l1.end());
    print(l2);
    return 0;
}

De manière similaire, il existe deux surcharges de la méthode erase qui permettent de spécifier de différentes manières les éléments qui doivent être supprimés d'une séquence. La première méthode prend en paramètre un itérateur sur l'élément à supprimer, et la deuxième un couple d'itérateurs donnant l'intervalle des éléments de la séquence qui doivent être supprimés. Ces deux méthodes retournent un itérateur sur l'élément suivant le dernier élément supprimé ou l'itérateur de fin de séquence s'il n'existe pas de tel élément. Par exemple, la suppression de tous les éléments d'une liste peut être réalisée de la manière suivante :

// Récupère un itérateur sur le premier
// élément de la liste :
list<int>::iterator i = instance.begin();
while (i != instance.end())
{
    i = instance.erase(i);
}

Vous noterez que la suppression d'un élément dans une séquence rend invalide tous les itérateurs sur cet élément. Il est à la charge du programmeur de s'assurer qu'il n'utilisera plus les itérateurs ainsi invalidés. La bibliothèque standard ne fournit aucun support pour le diagnostic de ce genre d'erreur.

La complexité de toutes ces méthodes dépend directement du type de séquence sur lequel elles sont appliquées. Les avantages et les inconvénients de chaque séquence seront décrits dans la Section 17.2.2.

17.2.2.1. Les listes

La classe template list est certainement l'une des plus importantes car, comme son nom l'indique, elle implémente une structure de liste chaînée d'éléments, ce qui est sans doute l'une des structures les plus utilisées en informatique. Cette structure est particulièrement adaptée pour les algorithmes qui parcourent les données dans un ordre séquentiel.

Les propriétés fondamentales des listes sont les suivantes :

• elles implémentent des itérateurs bidirectionnels. Cela signifie qu'il est facile de passer d'un élément au suivant ou au précédent, mais qu'il n'est pas possible d'accéder aux éléments de la liste de manière aléatoire ;

• elles permettent l'insertion et la suppression d'un élément avec un coût constant, et sans invalider les itérateurs ou les références sur les éléments de la liste existants. Dans le cas d'une suppression, seuls les itérateurs et les références sur les éléments supprimés sont invalidés.

Les listes offrent donc la plus grande souplesse possible sur les opérations d'insertion et de suppression des éléments, en contrepartie de quoi les accès sont restreints à un accès séquentiel.

Comme l'insertion et la suppression des éléments en tête et en queue de liste peuvent se faire sans recherche, ce sont évidemment les opérations les plus courantes. Par conséquent, la classe template list propose des méthodes spécifiques permettant de manipuler les éléments qui se trouvent en ces positions. L'insertion d'un élément peut donc être réalisée respectivement en tête et en queue de liste avec les méthodes push_front et push_back. Inversement, la suppression des éléments situés en ces emplacements est réalisée avec les méthodes pop_front et pop_back. Toutes ces méthodes ne renvoient aucune valeur, aussi l'accès aux deux éléments situés en tête et en queue de liste peut-il être réalisé respectivement par l'intermédiaire des accesseurs front et back, qui renvoient tous deux une référence (éventuellement constante si la liste est elle-même constante) sur ces éléments.

#include <iostream>
#include <list>

using namespace std;

typedef list<int> li;

int main(void)
{
    li l1;
    l1.push_back(2);
    l1.push_back(5);
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    l1.push_front(7);
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    l1.pop_back();
    cout << "Tête : " << l1.front() << endl;
    cout << "Queue : " << l1.back() << endl;
    return 0;
}

Les listes disposent également de méthodes spécifiques qui permettent de leur appliquer des traitements qui leur sont propres. Ces méthodes sont décrites dans le tableau ci-dessous :

#include <iostream>
#include <functional>
#include <list>

using namespace std;

typedef list<int> li;

void print(li &l)
{
    li::iterator i = l.begin();
    while (i != l.end())
    {
        cout << *i << " ";
        ++i;
    }
    cout << endl;
    return ;
}

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

int main(void)
{
    // Construit une liste exemple :
    li l;
    l.push_back(2);
    l.push_back(5);
    l.push_back(7);
    l.push_back(7);
    l.push_back(3);
    l.push_back(3);
    l.push_back(2);
    l.push_back(6);
    l.push_back(6);
    l.push_back(6);
    l.push_back(3);
    l.push_back(4);
    cout << "Liste de départ :" << endl;
    print(l);
    li l1;
    // Liste en ordre inverse :
    l1 = l;
    l1.reverse();
    cout << "Liste inverse :" << endl;
    print(l1);
    // Trie la liste :
    l1 = l;
    l1.sort();
    cout << "Liste triée : " << endl;
    print(l1);
    // Supprime tous les 3 :
    l1 = l;
    l1.remove(3);
    cout << "Liste sans 3 :" << endl;
    print(l1);
    // Supprime les doublons :
    l1 = l;
    l1.unique();
    cout << "Liste sans doublon :" << endl;
    print(l1);
    // Retire tous les nombres pairs :
    l1 = l;
    l1.remove_if(ptr_fun(&parity_even));
    cout << "Liste sans nombre pair :" << endl;
    print(l1);
    // Injecte une autre liste entre les 7 :
    l1 = l;
    li::iterator i = l1.begin();
    ++i; ++i; ++i;
    li l2;
    l2.push_back(35);
    l2.push_back(36);
    l2.push_back(37);
    l1.splice(i, l2, l2.begin(), l2.end());
    cout << "Fusion des deux listes :" << endl;
    print(l1);
    if (l2.size() == 0)
        cout << "l2 est vide" << endl;
    return 0;
}

17.2.2.2. Les vecteurs

La classe template vector de la bibliothèque standard fournit une structure de données dont la sémantique est proche de celle des tableaux de données classiques du langage C/C++. L'accès aux données de manière aléatoire est donc réalisable en un coût constant, mais l'insertion et la suppression des éléments dans un vecteur ont des conséquences nettement plus lourdes que dans le cas des listes.

Les propriétés des vecteurs sont les suivantes :

• les itérateurs permettent les accès aléatoires aux éléments du vecteur ;

• l'insertion ou la suppression d'un élément à la fin du vecteur se fait avec une complexité constante, mais l'insertion ou la suppression en tout autre point du vecteur se fait avec une complexité linéaire. Autrement dit, les opérations d'insertion ou de suppression nécessitent a priori de déplacer tous les éléments suivants, sauf si l'élément inséré ou supprimé se trouve en dernière position ;

• dans tous les cas, l'insertion d'un élément peut nécessiter une réallocation de mémoire. Cela a pour conséquence qu'en général, les données du vecteur peuvent être déplacées en mémoire et que les itérateurs et les références sur les éléments d'un vecteur sont a priori invalidés à la suite d'une insertion. Cependant, si aucune réallocation n'a lieu, les itérateurs et les références ne sont pas invalidés pour tous les éléments situés avant l'élément inséré ;

• la suppression d'un élément ne provoquant pas de réallocation, seuls les itérateurs et les références sur les éléments suivant l'élément supprimé sont invalidés.

Tout comme la classe list, la classe template vector dispose de méthodes front et back qui permettent d'accéder respectivement au premier et au dernier élément des vecteurs. Cependant, contrairement aux listes, seule les méthodes push_back et pop_back sont définies, car les vecteurs ne permettent pas d'insérer et de supprimer leurs premiers éléments de manière rapide.

En revanche, comme nous l'avons déjà dit, les vecteurs ont la même sémantique que les tableaux et permettent donc un accès rapide à tous leurs éléments. La classe vector définit donc une méthode at qui prend en paramètre l'indice d'un élément dans le vecteur et qui renvoie une référence, éventuellement constante si le vecteur l'est lui-même, sur cet élément. Si l'indice fourni en paramètre référence un élément situé en dehors du vecteur, la méthode at lance une exception out_of_range. De même, il est possible d'appliquer l'opérateur [] utilisé habituellement pour accéder aux éléments des tableaux. Cet opérateur se comporte exactement comme la méthode at, et est donc susceptible de lancer une exception out_of_range.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    typedef vector<int> vi;
    // Crée un vecteur de 10 éléments :
    vi v(10);
    // Modifie quelques éléments :
    v.at(2) = 2;
    v.at(5) = 7;
    // Redimensionne le vecteur :
    v.resize(11);
    v.at(10) = 5;
    // Ajoute un élément à la fin du vecteur :
    v.push_back(13);
    // Affiche le vecteur en utilisant l'opérateur [] :
    for (int i=0; i<v.size(); ++i)
    {
        cout << v[i] << endl;
    }
    return 0;
}

Par ailleurs, la bibliothèque standard définit une spécialisation de la classe template vector pour le type bool. Cette spécialisation a essentiellement pour but de réduire la consommation mémoire des vecteurs de booléens, en codant ceux-ci à raison d'un bit par booléen seulement. Les références des éléments des vecteurs de booléens ne sont donc pas réellement des booléens, mais plutôt une classe spéciale qui simule ces booléens tout en manipulant les bits réellement stockés dans ces vecteurs. Ce mécanisme est donc complètement transparent pour l'utilisateur, et les vecteurs de booléens se manipulent exactement comme les vecteurs classiques.

17.2.2.3. Les deques

Pour ceux à qui les listes et les vecteurs ne conviennent pas, la bibliothèque standard fournit un conteneur plus évolué qui offre un autre compromis entre la rapidité d'accès aux éléments et la souplesse dans les opérations d'ajout ou de suppression. Il s'agit de la classe template deque, qui implémente une forme de tampon circulaire dynamique.

Les propriétés des deques sont les suivantes :

• les itérateurs des deques permettent les accès aléatoires à leurs éléments ;

• l'insertion et la suppression des éléments en première et en dernière position se fait avec un coût constant. Notez ici que ce coût est toujours le même, et que, contrairement aux vecteurs, il ne s'agit pas d'un coût amorti (autrement dit, ce n'est pas une moyenne). En revanche, tout comme pour les vecteurs, l'insertion et la suppression aux autres positions se fait avec une complexité linéaire ;

• contrairement aux vecteurs, tous les itérateurs et toutes les références sur les éléments de la deque deviennent systématiquement invalides lors d'une insertion ou d'une suppression d'élément aux autres positions que la première et la dernière ;

• de même, l'insertion d'un élément en première et dernière position invalide tous les itérateurs sur les éléments de la deque. En revanche, les références sur les éléments restent valides. Remarquez que la suppression d'un élément en première et en dernière position n'a aucun impact sur les itérateurs et les références des éléments autres que ceux qui sont supprimés.

Comme vous pouvez le constater, les deques sont donc extrêmement bien adaptés aux opérations d'insertion et de suppression en première et en dernière position, tout en fournissant un accès rapide à leurs éléments. En revanche, les itérateurs existants sont systématiquement invalidés, quel que soit le type d'opération effectuée, hormis la suppression en tête et en fin de deque.

Comme elle permet un accès rapide à tous ses éléments, la classe template deque dispose de toutes les méthodes d'insertion et de suppression d'éléments des listes et des vecteurs. Outre les méthodes push_front, pop_front, push_back, pop_back et les accesseurs front et back, la classe deque définit donc la méthode at, ainsi que l'opérateur d'accès aux éléments de tableaux []. L'utilisation de ces méthodes est strictement identique à celle des méthodes homonymes des classes list et vector et ne devrait donc pas poser de problème particulier.

17.2.2.4. Les adaptateurs de séquences

Les classes des séquences de base list, vector et deque sont supposées satisfaire à la plupart des besoins courants des programmeurs. Cependant, la bibliothèque standard fournit des adaptateurs pour transformer ces classes en d'autres structures de données plus classiques. Ces adaptateurs permettent de construire des piles, des files et des files de priorité.

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
    typedef stack<int> si;
    // Crée une pile :
    si s;
    // Empile quelques éléments :
    s.push(2);
    s.push(5);
    s.push(8);
    // Affiche les éléments en ordre inverse :
    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
    typedef queue<int> qi;
    // Crée une file :
    qi q;
    // Ajoute quelques éléments :
    q.push(2);
    q.push(5);
    q.push(8);
    // Affiche récupère et affiche les éléments :
    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    return 0;
}

#include <iostream>
#include <queue>

using namespace std;

// Type des données stockées dans la file :
struct A
{
    int k;         // Priorité
    const char *t; // Valeur
    A() : k(0), t(0) {}
    A(int k, const char *t) : k(k), t(t) {}
};

// Foncteur de comparaison selon les priorités :
class C
{
public:
    bool operator()(const A &a1, const A &a2)
    {
        return a1.k < a2.k ;
    }
};

int main(void)
{
    // Construit quelques objets :
    A a1(1, "Priorité faible");
    A a2(2, "Priorité moyenne 1");
    A a3(2, "Priorité moyenne 2");
    A a4(3, "Priorité haute 1");
    A a5(3, "Priorité haute 2");
    // Construit une file de priorité :
    priority_queue<A, vector<A>, C> pq;
    // Ajoute les éléments :
    pq.push(a5);
    pq.push(a3);
    pq.push(a1);
    pq.push(a2);
    pq.push(a4);
    // Récupère les éléments par ordre de priorité :
    while (!pq.empty())
    {
        cout << pq.top().t << endl;
        pq.pop();
    }
    return 0;
}