Newsletter Developpez.com

Inscrivez-vous gratuitement au Club pour recevoir
la newsletter hebdomadaire des développeurs et IT pro

Les conteneurs, hérités d'un autre temps ?
Sont-ils toujours utiles, conseillés ?

Le , par dourouc05, Responsable Qt
Bonjour,

La STL, la bibliothèque standard de templates du C++, fournit un concept très intéressant pour le développement : il s'agit des conteneurs.

Qu'est-ce qu'un conteneur ?

Citation Envoyé par FAQ C++
Un conteneur (container) est, comme son nom l'indique, un objet qui contient d'autres objets.


Il s'agit d'un objet contenant d'autres objets. Il propose toujours quelques fonctionnalités concernant ces objets contenus : au strict minimum, l'ajout et la suppression. Parfois aussi, l'insertion, le tri, la recherche... Ils fournissent aussi des itérateurs, qui permettent de les utiliser dans des boucles en passant par tous les éléments.

Qt fournit aussi des conteneurs, qui reprennent le concept de la STL. Les itérateurs sont aussi disponibles, mais une nouvelle instruction, foreach, est aussi disponible.

Voici le code que vous devez rédiger en C++ :

Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
#include <vector> 
std::vector<int> s; 
for (std::vector<int>::iterator it = s.begin(); it != s.end(); ) 
{ 
    if (*it == 5) 
        it = s.erase(it); 
    else 
        ++it; 
}

Et voici un autre code, qui exploite ce nouveau mot-clé :

Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
QStringList list; 
list << "C" << "C++" << "Qt"; 
QList<QByteArray> ipListEnCharData; 
QList<const char*> ipListEnChar; 
foreach(QString ip, list) 
{ 
      QByteArray adresseIpEncodee = ip.toUtf8(); 
      ipListEnChar << adresseIpEncodee.constData(); 
      ipListEnCharData << adresseIpEncodee; 
} 
foreach(const char *str, ipListEnChar) 
{ 
    printf(str); 
}

Qt apporte ici une grande nouveauté par rapport au C++ standard : la version utilisant les itérateurs n'est pas extrêmement lisible, en comparaison avec la version permise par Qt.

Ceci sera-t-il corrigé par la nouvelle version du C++ ? Je n'en ai personnellement jamais entendu parler. Les conteneurs seraient-ils les grands oubliés de ce nouveau standard ? D'ailleurs, n'était-il pas plus logique de proposer cette construction avant ?

Ceci porte à réflexion.

Si les conteneurs ne bénéficient pas d'une manière standard d'une méthode extrêmement facile et très lisible, n'est-ce pas un signe de non-reconnaissance ? Les enfants mal-aimés du C++ ? Pourquoi en est-il ainsi ? Le concept est-il toujours utile, ou bien d'autres solutions sont-elles à préférer ? Est-il toujours adapté au contexte actuel (les dernières spécifications C++ ont à peu près 10 ans) ? Qu'y manque-t-il encore ?

En conséquence, Qt possède des versions réécrites des conteneurs de la STL. À l'époque, ils y étaient obligés : les STL fournies par les compilateurs ne supportaient pas forcément très bien les conteneurs standard. Ils en ont profité pour ajouter de nouvelles fonctionnalités, comme foreach. Ont-ils bien fait ? Ont-ils fait mieux que la spécification ? Qu'est-ce qui les distingue de cette spécification ? Leur performances ? Leur sûreté ? Leur efficacité ?


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de SpiceGuid SpiceGuid - Membre émérite https://www.developpez.com
le 18/11/2009 à 18:29
J'ai moi aussi un peu réfléchi à cette question des conteneurs et sur la meilleure façon de les traverser en partie ou en totalité.
Je suis d'accord pour dire que la solution retenue par la plupart des langages courants est assez navrante.
À mon avis même la solution retenue par OCaml-Batteries-Included est un peu datée.

Conceptuellement le foreach correspond à un List.iter.
En plus il est inefficace car il traversera toujours tous les éléments même si on n'est intéressé que par une petite fraction d'entre eux.

Voici un exposé succint de la solution que j'ai conçue pour OCaml-Idaho.
Elle utilise les lambdas et le fait que ce que l'on veut extraire c'est essentiellement une séquence puisqu'on ne veut agir sur chaque élément qu'une fois et une seule.
Une façon de construire la séquence à extraire serait de mettre tous les éléments dans une liste chaînée.
Mais ça serait trop coûteux en mémoire.
D'où ma solution: encapsuler la séquence dans une sorte de List.fold.

Exemple avec des conteneurs dictionnaires.
  • map est le type dictionaire
  • key est le type de la clé
  • item est le type des articles
  • ('a,'b)fold est le type de la séquence à extraire
  • la séquence est extraite à l'aide d'une fonction find_all


Code OCaml : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
module type OrderedMap 
  = 
  sig 
    type key 
    type item 
    type map 
    type ('a,'b) fold = 
      map -> (item -> 'a -> 'b) -> 'a -> 'b 
    val find_all:           ('a,'b) fold 
    val find_all_reverse:   ('a,'b) fold 
    val find_all_less:      key -> ('a,'b) fold  
    val find_all_more:      key -> ('a,'b) fold  
    val find_all_interval:  key -> key -> ('a,'b) fold 
  end

On voit la flexibilité de mon approche:
  • find_all extrait la séquence de tous les éléments
  • find_all_reverse extrait la séquence de tous les éléments mais dans l'ordre inverse
  • find_all_less extrait la séquence de tous les éléments de clé inférieure
  • find_all_more extrait la séquence de tous les éléments de clé supérieure
  • find_all_interval extrait la séquence de tous les éléments dans un intervalle de clé


Remarque: il n'y a là aucun filtrage, les éléments non inclus dans la séquence ne sont jamais traversés, même pas de manière silencieuse.

Autre exemple avec un dictionnaire bijectif, cette fois il y a deux types de clé key1 et key2.
Si les deux clés sont entières ou réelles on a une interprétaion géométrique, le dictionnaire bijectif devient un ensemble de points sur une grille ou un plan.

Code OCaml : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
module type BijectiveMap 
  = 
  sig 
    type key1 
    type key2 
    type item 
    type map 
    type ('a,'b) fold = 
      map -> (item -> 'a -> 'b) -> 'a -> 'b 
    val find_all:   ('a,'b) fold 
    val find_all1:  key1 -> ('a,'b) fold 
    val find_all2:  key2 -> ('a,'b) fold 
    val find_all_interval: key1 -> key1 -> key2 -> key2 -> ('a,'b) fold 
  end

Là encore la séquence capturée par une fonction find_all se montre à la fois expressive et efficace :
  • find_all extrait tous les points
  • find_all1 extrait tous les points situés sur une droite parallèle à l'axe des X
  • find_all2 extrait tous les points situés sur une droite parallèle à l'axe des Y
  • find_all_interval extrait tous les points situés dans un rectangle
Avatar de 3DArchi 3DArchi - Rédacteur https://www.developpez.com
le 18/11/2009 à 18:47
J'ai pas tout compris, je parle autant le chameau que le chinois
Néanmoins, j'ai l'impression que ça ressemble grandement au concept de range (cf l'article de Alexandrescu dont on a fait déjà 2 fois référence). Le range peut être vu non pas comme un couple d'itérateur début/itérateur fin, mais bien comme une 'liste' vers les éléments à traverser.
Avatar de yan yan - Rédacteur https://www.developpez.com
le 18/11/2009 à 19:33
Citation Envoyé par Luc Hermitte  Voir le message
a- Non, on utilise:
Code C++ : Sélectionner tout
v.erase(std::remove(v.begin(), v.end(), 5), v.end());
(Et si on avait des ranges, cela serait encore plus simple dans ce cas là)

Par contre on perd l'ordre des éléments d'un vecteur, non?

b- Qt passe par un préprocesseur qui fait plus de choses que le préprocesseur hérité du C, ce code n'est plus du C++. Pour atteindre l'équivalent, le langage doit être amendé.
Ce qui tombe bien car cela sera le cas.

Q_OBJECT, emit, slots , signal, ... ne sont que des macros. Le préproc de Qt ne fait q'implémenter les méthodes liése axu meta data. En quoi cela n'est plus du C++?

d- le foreach ne vient pas des conteneurs de Qt, mais de son préprocesseur.

Le foreach, comme celui de boost peut être utilisé sur n'importe quel conteneur. Celui de Qt est seulement spécialisé au conteneur de Qt et le parcoure est sécurisé (copie du centenaire avant de parcourir les données.

Après, avoir des containers COW avait certainement son intérêt en l'absence de sémantique de mouvement, avec l'arrivée du C++0x, je n'en suis plus aussi certain. Trop cher.

Le but de COW ne s'arrête pas à l'absence de sémantique de mouvement. Mais aussi à partager des données en lecture. Et éviter des copies inutile.
Avatar de Matthieu Brucher Matthieu Brucher - Rédacteur https://www.developpez.com
le 18/11/2009 à 20:00
Citation Envoyé par Luc Hermitte  Voir le message
b- Qt passe par un préprocesseur qui fait plus de choses que le préprocesseur hérité du C, ce code n'est plus du C++. Pour atteindre l'équivalent, le langage doit être amendé.
Ce qui tombe bien car cela sera le cas.
Non seulement il va y avoir un "for (Type e : conteneur)", mais aussi un std::foreach capable de prendre des lambdas functions.

Quelle est la différence d'avec Boost ? On ne passe pas par moc ou n'importe quel autre outil de Qt, on compile et voilà. Je ne comprends pas trop le problème (sauf si j'ai mal compris le foreach de Qt).

Citation Envoyé par yan  Voir le message
Q_OBJECT, emit, slots , signal, ... ne sont que des macros. Le préproc de Qt ne fait q'implémenter les méthodes liése axu meta data. En quoi cela n'est plus du C++?

Parce qu'à partir de ces macros, il faut passer un coup de moc pour générer le code associé.
Avatar de yan yan - Rédacteur https://www.developpez.com
le 18/11/2009 à 20:49
Citation Envoyé par Matthieu Brucher  Voir le message
Parce qu'à partir de ces macros, il faut passer un coup de moc pour générer le code associé.

A ma connaissance, bison et yacc, ou dans des parties de boost on fait la même chose : On utilise un exe qui génère du code.
Avatar de dj.motte dj.motte - Inactif https://www.developpez.com
le 18/11/2009 à 23:40
Bonjour,

Bof je pense que la syntaxe :

Code : Sélectionner tout
1
2
3
  
for ( x : list ) 
..
Fait un truc .

Le seul avantage c'est de parcourir le conteneur de manière sans drapeaux.

C'est ben vrai que sans les itérateurs on ne pourrait plus parcourir un conteneur ?

C'est vrai cela ?
Avatar de Luc Hermitte Luc Hermitte - Expert éminent https://www.developpez.com
le 19/11/2009 à 1:05
Citation Envoyé par yan  Voir le message
a- [erase remove]Par contre on perd l'ordre des éléments d'un vecteur, non?

b- Q_OBJECT, emit, slots , signal, ... ne sont que des macros. Le préproc de Qt ne fait qu'implémenter les méthodes liées aux meta data. En quoi cela n'est plus du C++?

Le foreach, comme celui de boost peut être utilisé sur n'importe quel conteneur. Celui de Qt est seulement spécialisé au conteneur de Qt et le parcourt est sécurisé (copie du centenaire avant de parcourir les données.

c- Le but de COW ne s'arrête pas à l'absence de sémantique de mouvement. Mais aussi à partager des données en lecture. Et éviter des copies inutile.

a- Du tout. L'ordre est conservé.

b- Je parlais du foreach de Qt qui est une addition au langage traitée lors d'une phase de préprocessing propre à Qt.
A partir du moment où un compilateur ne sait plus le traiter avec juste des fichiers d'en-tête, ce n'est plus du C++ -- allez-y, dites moi donc que le C++ est du C car il suffit de passer une couche de CFront.

Pourquoi j'ai soulevé ce point ? Parce que l'OP critique un (soit disant ?) archaïsme de la STL à cause de la lourdeur d'utilisation de sa syntaxe sur les itérations, alors que ... regardez donc Qt, c'est simple.
Ouais, sauf que la STL et par extension la SL s'appuient sur le C++ et uniquement le C++. C++/Qt est lui un langage bâti au dessus du C++ pour lui rajouter certaines constructions (un sucre syntaxique ici (foreach)).
C'est sûr que si la SL s'appuyait sur un C++ avec des trucs en plus, on pourrait alors avoir un "foreach (T e : c)"...
(Vous voyez où je veux en venir ? Je peux descendre du canapé ?)

c- Ce n'est certes pas son but, mais cela représente pourtant l'essentiel de ses utilisations en C++/Qt : pouvoir permettre aux non initiés à "const&" de passer des conteneurs par copie, et de les retourner par copie même là où les (N)RVO ne s'appliquent pas.
De plus quand je veux jouer aux lecteurs/écrivains sur des conteneurs, c'est rare que mes conteneurs ne soient pas des entités entièrement partagées par tous mes threads. Dit autrement, je n'ai pas encore rencontré de situation où je pouvais avoir un besoin avéré d'utiliser du COW (et pas un besoin d'optimiser des transits de données aux frontières de fonctions)
Avatar de yan yan - Rédacteur https://www.developpez.com
le 19/11/2009 à 9:46
Citation Envoyé par Luc Hermitte  Voir le message

, il me semblais qu'il recopier les éléments de fin pour être plus rapide.
b- Je parlais du foreach de Qt qui est une addition au langage traitée lors d'une phase de préprocessing propre à Qt.

ce n'est pas moc qui gère le forecah de Qt mais celui de C++. Comme celui de boost.

Pourquoi j'ai soulevé ce point ? Parce que l'OP critique un (soit disant ?) archaïsme de la STL à cause de la lourdeur d'utilisation de sa syntaxe sur les itérations, alors que ... regardez donc Qt, c'est simple.

Qt as des itérateurs et des algorithm. Ce ne sont que des contenaire à leur sauce qui répond à leur problème et compatible avec la S(T)L. Après la raison d'avoir fait cela, je pense que c'est surtout historique et surement peut des raison de différence entre compilateur. Par exemple, il fallait patcher "à la main" certain entête de la STL de vc 6 pour résoudre des bug : http://www.dinkumware.com/vc_fixes.html. Ou alors utiliser STLPort.

pouvoir permettre aux non initiés à "const&" de passer des conteneurs par copie, et de les retourner par copie même là où les (N)RVO ne s'appliquent pas.

Tu as tout a fait raison. Mais cela, est aussi très utilise dans les partie GUI. Par exemple, tu veut mettre une icône au élément de ta listview. Tu ne peut utiliser la même instance de l'icône sans ré-implémenter ton model. Le COW va permettre un équivalent de manière transparente. C'est aussi le cas dans les partie de traitement de texte.
Je ne dit pas que c'est là meilleur solution, mais une solution pratique.
Avatar de dj.motte dj.motte - Inactif https://www.developpez.com
le 19/11/2009 à 14:23
Salut,

Avec cette syntaxe :

Code : Sélectionner tout
1
2
3
  
for ( x : list )  
do ...

Comment fait-on pour itérer de la 3éme position à la 9éme par exemple ? C'est pas très pratique dans ce cas hein ?
Avatar de Luc Hermitte Luc Hermitte - Expert éminent https://www.developpez.com
le 19/11/2009 à 17:25
Citation Envoyé par yan  Voir le message
ce n'est pas moc qui gère le foreach de Qt mais celui de C++. Comme celui de boost.

OK, j'avais mal lu. Au temps pour moi alors.
Avatar de yan yan - Rédacteur https://www.developpez.com
le 19/11/2009 à 21:51
Citation Envoyé par dj.motte  Voir le message
Comment fait-on pour itérer de la 3éme position à la 9éme par exemple ? C'est pas très pratique dans ce cas hein ?

C'est plutôt la notion de range qui est nouvelle. Si je ne me trompe pas, c'est la même chose que les range de boost.

Y as quelques temps, loufoque as donnée un exemple avec une extension de boost.range (normalement en cours de validation) que j'ai trouvé intéressante :
http://www.developpez.net/forums/d60...s/#post3624830
http://boost-sandbox.sourceforge.net...tml/index.html
Offres d'emploi IT
Ingénieur développement fpga (traitement vidéo) H/F
Safran - Ile de France - 100 rue de Paris 91300 MASSY
Ingénieur H/F
Safran - Ile de France - Moissy-Cramayel (77550)
Spécialiste systèmes informatiques qualité et référent procédure H/F
Safran - Ile de France - Colombes (92700)

Voir plus d'offres Voir la carte des offres IT
Responsable bénévole de la rubrique Qt : Thibaut Cuvelier -