Logo GNT
Actualités Tests & Guides Bons Plans
Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11
Entraide Développement Développement Langage C++ Iterateur sur une collection de collections

Iterateur sur une collection de collections

11 réponses
Avatar
Fabien LE LEZ
Bonjour,

Soit un tableau de tableaux.
Mettons, pour fixer les idées, un vector<string> :

vector<string> v;
v.push_back ("a");
v.push_back ("");
v.push_back ("bc");

J'aimerais créer un itérateur (façon STL) qui visite chaque élément.
Ici, j'aurais donc :

Iterateur it= ....
Iterateur it_fin= ...
assert (*it == 'a');
++it
assert (*it == 'b');
++it
assert (*it == 'c');
++it
assert (it == it_fin);


A priori, c'est relativement simple, mais bizarrement, toutes les
implémentations que j'ai tentées me déplaisent, me paraissent
inutilement compliquées.

Quelqu'un aurait-il une implémentation de référence, testée, fiable et
élégante, que je mettrais une fois pour toutes dans ma boîte à
outils ?

Merci d'avance...
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2
Avatar
Michael DOUBEZ
Bonjour,

Soit un tableau de tableaux.
Mettons, pour fixer les idées, un vector<string> :

vector<string> v;
v.push_back ("a");
v.push_back ("");
v.push_back ("bc");

J'aimerais créer un itérateur (façon STL) qui visite chaque élément.
Ici, j'aurais donc :

Iterateur it= ....
Iterateur it_fin= ...
assert (*it == 'a');
++it
assert (*it == 'b');
++it
assert (*it == 'c');
++it
assert (it == it_fin);


A priori, c'est relativement simple, mais bizarrement, toutes les
implémentations que j'ai tentées me déplaisent, me paraissent
inutilement compliquées.

Quelqu'un aurait-il une implémentation de référence, testée, fiable et
élégante, que je mettrais une fois pour toutes dans ma boîte à
outils ?


Non, je n'en connais pas mais je partirais sur quelque chose du genre:

template< typename T , template <typename> class Container, template
<typename> class Contained >
class container_iterator
{
//helper for iterators
typedef typename Container< Contained<T> >::iterator iterator_c;
typedef typename Contained<T>::iterator iterator_d;


public:
typedef forward_iterator_iterator_tag iterator_category;
typedef typename iterator_d::value_type value_type;
typedef typename iterator_d::pointer pointer;
typedef typename iterator_d::reference reference;


//default construction
container_iterator(){}
//assignement/copy
container_iterator( iterator_c it );
container_iterator( const container_iterator& it
/*, pass container ?*/ );
container_iterator& operator=( const container_iterator& it );

//equality compare
bool operator==(const container_iterator& it );
bool operator!=(const container_iterator& it );
//...
};


Le principal problème serait de savoir quand ++() atteind end() au
moment de la recherche du prochain element valide dans le Container.
Peut être faudrait il garder une reférence sur le container mais ça
rends l'interface moins sympa.

Quelqu'un aurait une idée ?

Michael

Avatar
Fabien LE LEZ
On Tue, 10 Jul 2007 17:11:45 +0200, Michael DOUBEZ
:

Non, je n'en connais pas


Dommage, j'aimerais justement quelque chose de déjà intensivement
testé.

typedef typename Container< Contained<T> >::iterator iterator_c;
typedef typename Contained<T>::iterator iterator_d;


Du coup, il va falloir penser aussi à la version const_iterator...
Argh !

(Cela dit, je n'ai pour l'instant pas eu besoin de version non-const.)

container_iterator( const container_iterator& it
/*, pass container ?*/ );
container_iterator& operator=( const container_iterator& it );


J'ai dans l'idée qu'on devrait pouvoir se contenter des constructeur
et opérateur de copie fournis par le compilo.

D'une manière générale, quand je conçois une classe, je ne définis ces
fonctions que si je n'ai vraiment pas le choix. Ce qui, en pratique,
est très rare.
Et

//...


Le problème est bien dans ce "..." ; plus précisément, dans
l'opérateur ++().

Peut être faudrait il garder une reférence sur le container


Un pointeur, en fait. Sinon l'itérateur ne sera pas assignable.

mais ça rends l'interface moins sympa.


J'ai bien l'impression, effectivement, qu'il va falloir passer le
conteneur lui-même au constructeur de l'itérateur.

Avatar
Sylvain
Fabien LE LEZ wrote on 10/07/2007 12:10:
Bonjour,

Soit un tableau de tableaux.
Mettons, pour fixer les idées, un vector<string> :


ça ne fixe pas, mais peut être ne suis-je équipé pour.
string contient plus ou moins un tableau de caractères, c'est un fait
mais pour autant vector<string> est un vecteur (1D) assez classique.

vector<string> v;
v.push_back ("a");
v.push_back ("");
v.push_back ("bc");

Iterateur it= ....
assert (*it == 'a'); ++it
assert (*it == 'b'); ++it
assert (*it == 'c'); ++it


on parle souvent sur ce forum de sens intrinsèquement contenu et
spontanément compréhensible dans une expression; ici tu donnes
l'impresson de stocker des chaines et veux ensuite les découper par
caractère, pourquoi pas par chaine originale (soit la question ne se
poserait pas), mais aussi pourquoi pas par doublet ou triplet de car,
bref ça parait un peu arbitraire.

pour manipuler un tab. de tab, par exemple - je suis très SQL en ce
moment - n lignes de k colonnes (de types différents) je préfère
réserver l'incrémentation de l'itérateur pour balayer la première
dimension du tableau (le record suivant) et utilise plutôt un operateur
[] (int index) et/ou () (const char* name) pour accéder à un élement de
second niveau (la colonne d'index ou de nom transmis).

ton exemple me parait plutôt linéaire et se résoud par un seul string.

Sylvain.

Avatar
Loïc Joly
Quelqu'un aurait-il une implémentation de référence, testée, fiable et
élégante, que je mettrais une fois pour toutes dans ma boîte à
outils ?


Il y a dans boost::iterator des outils pour créer ses propres itérateurs
en écrivant juste 2/3 fonctions. Ca peut aider à implémenter.

Par contre, je ne connais pas de solution qui fasse directement ce que
tu souhaites.

--
Loïc

Avatar
Jean-Marc Bourguet
Fabien LE LEZ writes:

Le problème est bien dans ce "..." ; plus précisément, dans l'opérateur
++().


Je ne vois pas de probleme:

++currentInner_;
if (currentInner_ == endOuter_) {
++currentOuter__;
if (currentOuter_ != endOuter__)
currentInner_ = currentOuter_->begin();
}
return *this;

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Avatar
Michael DOUBEZ
On Tue, 10 Jul 2007 17:11:45 +0200, Michael DOUBEZ



Le problème est bien dans ce "..." ; plus précisément, dans
l'opérateur ++().

Peut être faudrait il garder une reférence sur le container


Un pointeur, en fait. Sinon l'itérateur ne sera pas assignable.

mais ça rends l'interface moins sympa.


J'ai bien l'impression, effectivement, qu'il va falloir passer le
conteneur lui-même au constructeur de l'itérateur.


Ou alors déléguer la construction de l'iterator à une classe.

template< class Container >
class visit_contained
{
public:
visit_contained( Container& conr );


container_iterator begin()const;
container_iterator end()const;

//

};

Puis:
vector<string> v;
v.push_back ("a");
v.push_back ("");
v.push_back ("bc");

container_iterator it = visit_contained(v).begin();
container_iterator it_middle = visit_contained(v).position(/*
iterators */ );
container_iterator it_end = visit_contained(v).end();

Michael


Avatar
James Kanze
On Jul 11, 1:56 am, Loïc Joly
wrote:

Quelqu'un aurait-il une implémentation de référence, testée, fi able et
élégante, que je mettrais une fois pour toutes dans ma boîte à
outils ?


Il y a dans boost::iterator des outils pour créer ses propres itérate urs
en écrivant juste 2/3 fonctions. Ca peut aider à implémenter.


J'allais conseiller justement la même chose. Ça peut être
énormement.

Par contre, je ne connais pas de solution qui fasse directement ce que
tu souhaites.


En effet, un des problèmes fondamentaux de l'idiome des deux
itérateurs, c'est la difficulté d'implémenter les décorateurs
d'itérateur. L'idiome plus ou moins consacré ici, c'est bien de
passer les deux itérateurs de base au constructeur de
l'itérateur dérivé (ici, les itérateurs begin() et end() de la
collection extérieur).

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


Avatar
Fabien LE LEZ
On 11 Jul 2007 09:03:15 +0200, Jean-Marc Bourguet :

Je ne vois pas de probleme:


Imagine un vector<string> contenant ceci :


"abc"
""
"def"
""
""

Si on est sur 'c', ++() doit faire arriver sur 'd'.
Si on est sur 'f', ++() doit faire arriver sur un itérateur égal à
end.

Avatar
Jean-Marc Bourguet
Fabien LE LEZ writes:

On 11 Jul 2007 09:03:15 +0200, Jean-Marc Bourguet :

Je ne vois pas de probleme:


Imagine un vector<string> contenant ceci :


"abc"
""
"def"
""
""

Si on est sur 'c', ++() doit faire arriver sur 'd'.
Si on est sur 'f', ++() doit faire arriver sur un itérateur égal à
end.


Pas tellement plus complique.

++currentInner_;
while (currentInner_ == endInner_ && currentOuter_ != endOuter_) {
++currentOuter__;
if (currentOuter_ != endOuter__) {
currentInner_ = currentOuter_->begin();
endInner_ = currentInner_->end();
}
}
return *this;

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org


Avatar
James Kanze
On Jul 10, 7:39 pm, Fabien LE LEZ wrote:
On Tue, 10 Jul 2007 17:11:45 +0200, Michael DOUBEZ
:

Non, je n'en connais pas


Dommage, j'aimerais justement quelque chose de déjà intensivement
testé.

typedef typename Container< Contained<T> >::iterator iterator_c;
typedef typename Contained<T>::iterator iterator_d;


Du coup, il va falloir penser aussi à la version const_iterator...
Argh !


Ça se résoud facilement avec des templates.

(Cela dit, je n'ai pour l'instant pas eu besoin de version non-const.)

container_iterator( const container_iterator& it
/*, pass container ?*/ );
container_iterator& operator=( const container_iterator& it );


J'ai dans l'idée qu'on devrait pouvoir se contenter des constructeur
et opérateur de copie fournis par le compilo.

D'une manière générale, quand je conçois une classe, je ne défi nis ces
fonctions que si je n'ai vraiment pas le choix. Ce qui, en pratique,
est très rare.


C'est une question de style. Les versions fournies par le
compilateur sont inline, et si jamais tu décides d'ajouter
quelque chose (l'instrumentation, par exemple), il faut modifier
l'en-tête, et donc déclencher la récompilation de tout le code
client. J'évite donc les défauts en général.

Dans le cas des templates, évidemment, ce deuxième argument ne
vaut pas ; toute l'implémentation se trouve dans l'en-tête de
toute façon.

Et

//...


Le problème est bien dans ce "..." ; plus précisément, dans
l'opérateur ++().


Le problème, c'est d'implémenter une interface qui est en fin de
compte assez mal conçue pour ce genre de choses.

Peut être faudrait il garder une reférence sur le container


Un pointeur, en fait. Sinon l'itérateur ne sera pas assignable.

mais ça rends l'interface moins sympa.


J'ai bien l'impression, effectivement, qu'il va falloir passer le
conteneur lui-même au constructeur de l'itérateur.


Plutôt une paire d'itérateurs, non. Autant être cohérant avec la
philosophie de la STL.

Devant ce genre de problème, je commence en général en
implémentant un itérateur classique (comme décrit dans le GoF),
puis en ajoutant l'interface STL. Dans la plupart des cas (mais
pas ici), l'itérateur de fin est un itérateur « factice »,
comme c'est le cas des itérateurs de flux dans la norme. Et le
véritable problème, c'est l'implémentation de == et de != ;
d'après mes expériences, a.isDone() == b.isDone() marche
toujours, mais je suis loin d'être convaincu que c'est garanti
par la norme.

En reprenant un truc que j'ai écrit il y a un certain temps :

template< typename FwdIterOuter, typename FwdIterInner >
class Iterator2D
{
public:
typedef typename std::iterator_traits< FwdIterInner
::value_type
value_type ;

typedef typename std::iterator_traits< FwdIterInner
::reference
reference ;

typedef typename std::iterator_traits< FwdIterInner >::pointer
pointer ;
typedef typename std::iterator_traits< FwdIterInner
::difference_type
difference_type ; // pas trop sûr ici...

typedef std::forward_iterator_tag
iterator_category ;

Iterator2D()
: myIsDone( true )
{
}
Iterator2D( FwdIterOuter begin,
FwdIterOuter end )
: myIsDone( begin == end )
, myOuterCurrent( begin )
, myOuterEnd( end )
{
if ( ! myIsDone ) {
myInnerCurrent = myOuterCurrent->begin() ;
advance() ;
}
}

bool isDone() const
{
return myIsDone ;
}

reference current() const
{
assert( ! myIsDone ) ;
return *myInnerCurrent ;
}

void next()
{
if ( ! myIsDone ) {
++ myInnerCurrent ;
advance() ;
}
}

bool isEqual( Iterator2D const& other ) const
{
return myIsDone
? other.myIsDone
: ( ! other.myIsDone
&& myOuterCurrent == other.myOuterCurrent
&& myInnerCurrent ==
other.myInnerCurrent ) ;
}

reference operator*() const
{
return current() ;
}

pointer operator->() const
{
return &current() ;
}

Iterator2D& operator++()
{
next() ;
return *this ;
}

Iterator2D operator++( int )
{
Iterator2D result( *this ) ;
next() ;
return result ;
}

private:
bool myIsDone ;
FwdIterOuter myOuterCurrent ;
FwdIterOuter myOuterEnd ;
FwdIterInner myInnerCurrent ;

void advance()
{
while ( ! myIsDone
&& myInnerCurrent == myOuterCurrent->end() ) {
++ myOuterCurrent ;
myIsDone = (myOuterCurrent == myOuterEnd) ;
if ( ! myIsDone ) {
myInnerCurrent = myOuterCurrent->begin() ;
}
}
}
} ;

template< typename FwdIterOuter, typename FwdIterInner >
bool
operator==(
Iterator2D< FwdIterOuter, FwdIterInner > const&
lhs,
Iterator2D< FwdIterOuter, FwdIterInner > const&
rhs )
{
return lhs.isEqual( rhs ) ;
}

template< typename FwdIterOuter, typename FwdIterInner >
bool
operator!=(
Iterator2D< FwdIterOuter, FwdIterInner > const&
lhs,
Iterator2D< FwdIterOuter, FwdIterInner > const&
rhs )
{
return ! lhs.isEqual( rhs ) ;
}

template< typename C >
Iterator2D< typename C::iterator,
typename std::iterator_traits<
typename C::iterator >::value_type::iterator >
begin2D(
C& c )
{
return Iterator2D<
typename C::iterator,
typename std::iterator_traits<
typename C::iterator >::value_type::iterator >(
c.begin(), c.end() ) ;
}

template< typename C >
Iterator2D< typename C::iterator,
typename std::iterator_traits<
typename C::iterator >::value_type::iterator >
end2D(
C& c )
{
return Iterator2D<
typename C::iterator,
typename std::iterator_traits<
typename C::iterator >::value_type::iterator >() ;
}

template< typename C >
Iterator2D< typename C::const_iterator,
typename std::iterator_traits<
typename C::const_iterator
::value_type::const_iterator >
begin2D(

C const& c )
{
return Iterator2D<
typename C::const_iterator,
typename std::iterator_traits<
typename C::const_iterator
::value_type::const_iterator >(
c.begin(), c.end() ) ;

}

template< typename C >
Iterator2D< typename C::const_iterator,
typename std::iterator_traits<
typename C::const_iterator
::value_type::const_iterator >
end2D(

C const& c )
{
return Iterator2D<
typename C::const_iterator,
typename std::iterator_traits<
typename C::const_iterator
::value_type::const_iterator >() ;
}


Je crois qu'en remplaçant systèmatiquement « myIsDone » avec
« myOuterCurrent != myOuterEnd », et en initialisant
l'itérateur avec « c.end(), c.end() » dans end2D(), on
pourrait se passer du member « myIsDone ». Mais il y a tant
d'autres cas où ce n'est pas le cas ; c'est encore un modèle de
conception, de faire comme ceci.

Aussi, si je le faisais aujourd'hui, je ne suis pas sûr que je
ne prendrait un iterator_adapter ou un iterator_fassade de
Boost.

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34


1 2