Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

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

Le , par dourouc05

0PARTAGES

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

Une erreur dans cette actualité ? Signalez-le nous !

Avatar de 3DArchi
Rédacteur https://www.developpez.com
Le 04/11/2009 à 15:09
Salut,
Une réponse à plusieurs détentes
1/ Les algorithmes de la STL sont une première façon de faire un for_each :
Code : Sélectionner tout
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 : Sélectionner tout
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 : Sélectionner tout
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 : Sélectionner tout
1
2
3
4
int array[5] = { 1, 2, 3, 4, 5 };
for (int& x : array){
   x *= 2;
}
ou encore :
Code : Sélectionner tout
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 : Sélectionner tout
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 :
The range-based for statement
Code : Sélectionner tout
for ( for-range-declaration : expression ) statement
is equivalent to
Code : Sélectionner tout
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 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.
0  0 
Avatar de yan
Rédacteur https://www.developpez.com
Le 04/11/2009 à 15:22
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 : Sélectionner tout
1
2
3
4
5
foreach(const QString & ip, list)
{
    ...
}
0  0 
Avatar de nouknouk
Modérateur https://www.developpez.com
Le 04/11/2009 à 15:47
Citation Envoyé par 3DArchi Voir le message
3/ Mais last but not least, C++0x prévoit l'équivalent d'un foreach :
Code : Sélectionner tout
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
0  0 
Avatar de Luc Hermitte
Expert éminent sénior https://www.developpez.com
Le 18/11/2009 à 14:29
Citation Envoyé par dourouc05  Voir le message
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 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à)

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.
0  0 
Avatar de 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
0  0 
Avatar de 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.
0  0 
Avatar de 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.
0  0 
Avatar de 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é.
0  0 
Avatar de 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.
0  0 
Avatar de 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 ?
0  0