Les conteneurs, hérités d'un autre temps ?

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:

---

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:

---

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é ?

Salut,
Une réponse à plusieurs détentes :mouarf:
1/ Les algorithmes de la STL sont une première façon de faire un for_each :

Code:

---

1 2 3

std::list<int> ma_liste; std::for_each(ma_liste.begin(),ma_liste.end(),action());

---

2/Il existe un boost.Foreach pour C++ actuel :

Code:

---

1 2 3 4 5

std::list<int> list_int; BOOST_FOREACH( int i, list_int ) { // do something with i }

---

3/ Les lambda de C++0x devraient encore faciliter l'écriture des foncteurs dans les algorithmes de la STL

Code:

---

1 2 3 4 5

std::vector<int> someList; int total = 0; std::for_each(someList.begin(), someList.end(), [&total](int x) { total += x; });

---

3/ Mais last but not least, C++0x prévoit l'équivalent d'un foreach :

Code:

---

1 2 3 4

int array[5] = { 1, 2, 3, 4, 5 }; for (int& x : array){ x *= 2; }

---

ou encore :

Code:

---

1 2 3 4

std::list<int> ma_list; for (int x : ma_list){ std::cout<<x <<"<-"; }

---

Il me semble que la seule contrainte de

Code:

---

1 2 3

CONTENEUR un_ensemble; for (TYPE val : un_ensemble){ }

---

est que CONTENEUR aie une spécialisation std::Range<_RangeT>::begin, std::Range<_RangeT>::end. Il existera une version par défaut pour les tableaux, ça prend le premier et le suivant du dernier, pour les autres cela suppose un begin() et un end(). Mais rien n'empêcherait à priori d'avoir sa propre spécialisation de std::Range pour un type maison du moment qu'un std::Range<MonType>::begin() et un std::Range<MonType>::end() retournent quelque chose qui suit un concept d'iterateur.
Mieux dit par la norme :

Citation:

---

The range-based for statement

Code:

---

for ( for-range-declaration : expression ) statement

---

is equivalent to

Code:

---

1 2 3 4 5 6 7 8 9 10

{ auto && __range = ( expression ); for ( auto __begin = std::Range<_RangeT>::begin(__range), __end = std::Range<_RangeT>::end(__range); __begin != __end; ++__begin ) { for-range-declaration = *__begin; statement } }

---

where __range, __begin, and __end are variables defined for exposition only, and _RangeT is the type of
the expression.

---

*****
Les conteneurs STL, les algorithmes de la STL et le nouveau for sont des choses différentes.
Les conteneurs de la STL permettent de s'abstraire de l'implémentation effective du concept qu'ils modélisent : un tableau dynamique (std::vector), une liste simplement chaînée (std::list), etc. Plus besoin de gérer les allocations, libérations, réallocations, enchainement, etc. Ils sont génériques, safe (exception, RAII mais pas thread-safe), fiables car utilisés dans des millions de ligne de code et facilement extensibles (par expl, les allocateurs).
Les algorithmes de la STL sont indépendants des conteneurs et s'appuient sur le concept d'itérateur. C'est là où une critique pertinente a été faite par Andrei Alexandrescu qui prône une disparition des itérateurs au profit du concept de range.
Le 'nouveau' for est effectivement dans le sens d'une simplification du langage sur certaines opérations basiques.


*****
Concernant Qt, mon principal reproche de ce genre de chose est d'être 'absorbant' si on ne fait pas attention. On va faire des QString, QList, QArray etc.. et au final du code (typiquement du code métier) qui pourrait ne pas s'appuyer sur Qt va en fourmiller imposant cette bibliothèque partout :aie: Personnellement, je préfère différencier les parties où je peux rester 100% C++ de celles où j'utilise un framework ou une bibliothèque. Ca permet d'avoir plus de code réutilisable indépendamment des composants utilisés. C'est le genre de problème auquel j'ai été confronté sur différents projets (avec les MFCs mais le principe reste le même) : du code ne pouvait être repris car il dépendait trop du framework de base.

Le foreach existe déjà dans boost ;)

La seule différence, c'est que le foreach de Qt certifie la validité des données qu'il parcoure. En faite, il fait cela :
1- copie du container : avec le COW on y voie que du feux.
2- donne un accès constant sur chaque éléments : soit on fait une copie, soit on fait une référence const.

Je conseil la référence const :

Code:

---

1 2 3 4 5

foreach(const QString & ip, list) { ... }

---

Citation:

---

Envoyé par 3DArchi

3/ Mais last but not least, C++0x prévoit l'équivalent d'un foreach :

Code:

---

1 2 3 4

int array[5] = { 1, 2, 3, 4, 5 }; for (int& x : array){ x *= 2; }

---

---

Java propose la même syntaxe depuis la version 1.5
Et, franchement, une fois qu'on l'a déjà utilisé on ne peut plus s'en passer :ccool:

Citation:

---

Envoyé par dourouc05

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

b- 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 ?

c- 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 ?

d- 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é ?

---

a- Non, on utilise:

Code:

---

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à)

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.

c- J'ai tendance à considérer les itérateurs de la STL comme une petite révolution pas entièrement comprise.
Je t'invite à jeter un coup d'oeil au bouquin d'algorithmique de Stepanov (le code source est librement téléchargeable, même si ce n'est plus le cas du draft d'Element Of Programming), ou à cet article: http://www.developpez.net/forums/d78...o/#post4786766

d- le foreach ne vient pas des conteneurs de Qt, mais de son préprocesseur.
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.
Quant aux itérateurs GoF ... ils ne m'ont jamais vraiment trop convaincu.

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:

---

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:

---

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

J'ai pas tout compris, je parle autant le chameau que le chinois :oops:
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.

Citation:

---

Envoyé par Luc Hermitte

a- Non, on utilise:

Code:

---

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?

Citation:

---

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++?

Citation:

---

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.

Citation:

---

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.

Citation:

---

Envoyé par Luc Hermitte

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

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é.

Citation:

---

Envoyé par Matthieu Brucher

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.

Bonjour,

Bof je pense que la syntaxe :

Code:

---

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 ?

Citation:

---

Envoyé par yan

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)

Citation:

---

Envoyé par Luc Hermitte

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

---

:merci:, il me semblais qu'il recopier les éléments de fin pour être plus rapide.

Citation:

---

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.

Citation:

---

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.

Citation:

---

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.

Salut,

Avec cette syntaxe :

Code:

---

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 ?

Citation:

---

Envoyé par yan

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.

Citation:

---

Envoyé par dj.motte

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