implementer un iterateur de X sur un std::vector< std::vector >

meow wrote:

Tout est dit dans le titre.
Pour faire court j'ai une classe qui contient un vector< vector X >
(où X est une classe) et j'aimerai itérer sur tous les X contenus
dans ce vecteur de vecteurs. Je m'interroge donc sur la meilleure
façon de faire. J'imagine que la problématique est classique mais je
n'ai rien trouvé sur le sujet.

Si tu as besoin d'itérer sur tous les éléments d'un coup,
il serait plus simple d'implémenter le tableau 2D à l'aide
d'un simple vector<X> et d'un accès par v[y*colCount + x]
si cela t'es possible.

--
Sylvain Togni

On 11 Jan 2007 07:27:23 -0800, "meow" <schwarz.ben@gmail.com>:

Comment je
teste ma condition d'arret ?

std::vector<std::vector<int> > v;

for (ConstIterVV<int> i (v), fin; i!=fin; ++i)

Ou bien

for (ConstIterVV<int> i; i != ConstIterVV<int>(); ++i)

meow wrote:

Tout est dit dans le titre.
Pour faire court j'ai une classe qui contient un vector< vector X >
(où X est une classe) et j'aimerai itérer sur tous les X contenus
dans ce vecteur de vecteurs. Je m'interroge donc sur la meilleure
façon de faire. J'imagine que la problématique est classique mais je
n'ai rien trouvé sur le sujet.

On m'a soufflé une solution facile : ma classe itérateur contiendrait
un vector< X >, mise à plat du vector<vector<X>> ainsi qu'un
itérateur sur ce vecteur (appellons le it).

Je n'écouterais pas ce genre de soufflement. Ça serait une
bêtise monstre.

Je définirais alors mes opérateurs ++, * et Cie simplement en les
déléguants à it (i.e le ++ de mon itérator fait juste un ++it, et
le * renvoie *it).

Cette solution me parrait lourdingue : si les vector<X> contiennent
beaucoup de X, mon itérateur va bouffer beaucoup de mémoire. En
outre, contrairement aux itérateurs de la stl, si ma structure tombe,
mon itérateur continue à etre valide (est-ce important ? Je suppose
que ça l'est si je veux faire des delete, replace, remove etc... mais
sinon ?) J'ai donc pensé à une autre solution :

Un vrai problème, c'est que les algorithmes, etc., supposent la
copie d'un itérateur « bon marché » ; un itérateur est fait
pour être copié. Or, si c'est vrai qu'on peut copier un vecteur,
c'est une opération assez lourde et assez chère, qu'on doit
éviter de faire trop souvent.

Un autre, c'est que si tu modifies à travers l'itérateur (p.e.
« *iter = quelqueChose ; »), c'est la copie que tu modifies,
et non l'objet initial.

dans mon_iterateur je stockerais un tableaux de paires d'itérateurs
sur X. Chaque paire étant constituée d'un itérateur sur le début et
d'un itérateur sur la fin d'un élément de mon vector<vector<X>>.
J'aurai en outre encore un itérateur sur mon vecteur de paire.
en gros :
class mon_iterateur {
vector<pair<vector<X>::iterator,vector<X>::iterator>> ;
vector<pair<vector<X>::iterator,vector<X>::iterator>> it;
...
mon_iterateur& operator++ {
if ((*it).first == (*it).second) ++it else ++(*it);
return *this;
}
...
};

ça vous semble correct ? y a t'il mieux ?

Je crois qu'à la base, on pourrait le faire avec deux
itérateurs. Il y aurait des cas délicat pour la détection de la
fin, et même l'incrémentation si certains des sous-tableaux
peuvent être vide, mais ça doit être faisable, quitte à
maintenir aussi un pointeur vers le tableau de base dans
l'itérateur aussi, de façon à pouvoir detecter les cas limites
et les traiter correctement. Sinon, rien n'empèche d'utiliser
quelque chose du genre :

size_t column ;
size_t line ;
vector< vector< T > >*
data ;

CompoundIterator& operator++()
{
assert( line < data->size() ) ;
++ column ;
while ( line < data->size()
&& column >= (*data)[ line ].size() ) {
++ line ;
column = 0 ;
}
return *this ;
}

bool operator==( CompoundIterator const& other )
const
{
return line == other.line && column == other.column ;
}

X& operator*() const
{
return (*data)[ line ][ column ] ;
}

et ainsi de suite. (On doit pouvoir faire un itérateur
bidirectionnel assez facilement comme ça. Si toutes les lignes
ont la même taille, et que l'itérateur le connaît, on pourrait
même faire un itérateur à accès aléatoire.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

Fabien LE LEZ wrote:

On 11 Jan 2007 02:04:28 -0800, "meow" <schwarz.ben@gmail.com>:

Pour faire court j'ai une classe qui contient un vector< vector X >
(où X est une classe) et j'aimerai itérer sur tous les X contenus
dans ce vecteur de vecteurs.

Faire un tel const_iterator est simple. Cf code ci-dessous, bricolé en
dix minutes et pas testé.
Pour un iterator, c'est peut-être un peu plus délicat, mais pas très
différent.

Ta solution c'est probablement celle que j'adopterais dans la
pratique. Sauf que je lui donnerais d'abord l'interface d'un
itérateur classique, sans les surcharges abusifs :

void next() ;
X& current() const ;
bool isDone() const ;

(Les noms peuvent varier. Si je l'avais à réfaire, je
remplacerais « current » par « value », et OSE utilise next,
item et isValid.) Dans la mesure que tu n'as pas réelement
besoin du deuxième itérateur pour determiner la fin, pourquoi en
imposer deux à l'utilisateur ? (Ensuite, j'implémente les
conventions STL à peu près comme tu l'as fait, afin que
l'itérateur marche aussi avec les algorithmes standard.)

Aussi, je crois que tu dois pouvoir remplacer le drappeau
« valide » avec « it1 != fin ». Et je crois qu'il y aurait
des problèmes si une des lignes est vide.

Ma version (non-const), donc :

template< typename T >
class CompoundIterator
: public std::iterator< std::forward_iterator_tag, T >
{
public:
typedef std::vector< T >
Line ;
typedef std::vector< T >
Table ;

typedef Line::iterator
ColumnIter ;
typedef Table::iterator
LineIter ;

explicit CompoundIterator( Table& table )
: line( table.begin() )
, end( table.end() )
{
setColumn() ;
}

T& current() const
{
assert( line != end ) ;
return *column ;
}
bool isDone() const
{
return line == end ;
}
void next()
{
assert( ! isDone() ) ;
++ column ;
if ( column == line->end() ) {
++ line ;
setColumn() ;
}
}

// opérateurs STL à peu près comme les tiens, basés
// cependant sur les fonctions ci-dessus...

private:
LineIter line ;
ColumnIter column ;
LineIter end ;

void setColumn()
{
if ( ! isDone() ) {
column = line->begin() ;
if ( column == line->end() ) {
++ line ;
setColumn() ;
}
}
}
} ;

(Je ne suis pas sûr que la récursion dans setColumn soit une
bonne idée. Une suite de quelque millions de lignes vides risque
de faire exploser la pile, au moins que le compilateur reconnaît
que c'est une recursion finale qui le convertit en boucle.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

Fabien LE LEZ wrote:

On 11 Jan 2007 07:27:23 -0800, "meow" <schwarz.ben@gmail.com>:

Comment je
teste ma condition d'arret ?

std::vector<std::vector<int> > v;

for (ConstIterVV<int> i (v), fin; i!=fin; ++i)

Ou bien

for (ConstIterVV<int> i; i != ConstIterVV<int>(); ++i)

Si son tableau de tableaux se trouve dans une classe, cette
classe doit implémenter :

CompoundIterator< T > begin()
{
return CompoundIterator( myData ) ;
}

CompoundIterator< T > end()
{
return CompoundIterator() ;
}

Ensuite, on s'en sert comme une collection STL quelconque.

Sinon, on pourrait bien considérer des fonctions libre :

template< typename T >
CompoundIterator< T >
begin(
std::vector< std::vector< T > >& data )
{
return CompoundIterator< T >( data ) ;
}

template< typename T >
CompoundIterator< T >
end(
std::vector< std::vector< T > >& data )
{
return CompoundIterator< T >() ;
}

Un compilateur moderne doit accepter la même chose si je définis
l'itérateur et les fonctions avec un paramètre templaté :

template< typename T, template< typename U, typename A > class C >
class CompoundIterator // ...

template< typename T, template< typename U, typename A > class C >
CompoundIterator< T, C >
begin( C< C< T, std::allocator< T > >,
std::allocator< C< T, std::allocator< T > > > >& data )
{
return CompoundIterator< T, C >( data ) ;
}

template< typename T, template< typename U, typename A > class C >
CompoundIterator< T, C >
end( C< C< T, std::allocator< T > >,
std::allocator< C< T, std::allocator< T > > > >& data )
{
return CompoundIterator< T, C >() ;
}

(Ça marche et avec g++ et avec VC++.) Comme tu peux voir,
l'allocateur dans les collections standard rend l'écriture assez
penible. G++ l'accept aussi sans le paramètre d'allocateur :

template< typename T, template< typename U > class C >
class CompoundIterator //...

template< typename T, template< typename U > class C >
CompoundIterator< T, C >
begin(
C< C< T > >& data )
{
return CompoundIterator< T, C >( data ) ;
}

template< typename T, template< typename U > class C >
CompoundIterator< T, C >
end(
C< C< T > >& data )
{
return CompoundIterator< T, C >() ;
}

Mais je ne crois pas que de tel code est légal ; je crois que
c'est plutôt une extension g++. (Une extension fort utile, j'en
conviens.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
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

ConstIterVV& operator ++ ()
{
assert (valide);
if (++it2 == (*it1).end())
{

Comme l'a dit James, il y a un problème ici si une des lignes est
vide. Je crois que la modification suivante résoud le problème :

ConstIterVV& operator ++ ()
{
assert (valide);
++it2;
while (valide && it2 == (*it1).end())
{

Mais là encore, je n'ai ni compilé, ni testé.

On 12 Jan 2007 00:47:05 -0800, "James Kanze" <james.kanze@gmail.com>:

Ta solution c'est probablement celle que j'adopterais dans la
pratique. Sauf que je lui donnerais d'abord l'interface d'un
itérateur classique, sans les surcharges abusifs :

Disons que s'il s'agit d'une classe dont l'utilisateur utilise
explicitement un vector<>, j'ai tendance à préférer recopier
l'interface de la STL, même si elle n'est pas la meilleure.

On 12 Jan 2007 01:42:47 -0800, "James Kanze" <james.kanze@gmail.com>:

Sinon, on pourrait bien considérer des fonctions libre :

Pourquoi pas...
Je me suis contenté d'une interface "façon istream_iterator".

Fabien LE LEZ wrote:

On 12 Jan 2007 00:47:05 -0800, "James Kanze" <james.kanze@gmail.com>:

Ta solution c'est probablement celle que j'adopterais dans la
pratique. Sauf que je lui donnerais d'abord l'interface d'un
itérateur classique, sans les surcharges abusifs :

Disons que s'il s'agit d'une classe dont l'utilisateur utilise
explicitement un vector<>, j'ai tendance à préférer recopier
l'interface de la STL, même si elle n'est pas la meilleure.

Je n'écrirai pas d'itérateur aujourd'hui qui n'implémente pas le
modèle STL, c'est clair. En revanche, si j'ai déjà le besoin
interne d'une implémentation classique, comme c'est le cas ici,
je donnerais bien la possibilité à l'utilisateur de s'en servir.
(Ne pas avoir besoin de deux itérateurs, c'est parfois très
avantageux, surtout si on adopte parfois une style un peu
« fonctionnelle ».

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
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

@ Sylvain Togni

il serait plus simple d'implémenter le tableau 2D à l'aide

J'y penserai à l'avenir ;)
La question reste tout de meme valable ne serait-ce que pour comprendre
le fonctionnement général d'un intérateur.

@ Fabien LE LEZ

for (ConstIterVV<int> i; i != ConstIterVV<int>(); ++i)
C'est ce que j'avais cru comprendre, mais ce qui me dérange dans cette

écriture, c'est le fait que le begin se réfère bien à une structure
(celle sur laquelle on itère), alors que ce n'est pas le cas du end().
En fait, je pense au cas où ton VV est masqué à l'intérieur d'une
classe (disons A), et que tu demandes tes itérateurs par a.begin() et
a.end() (avec a, instance de A). Ta condition d'arret en intérrant sur
a fonctionnerait tout aussi bien avec b.end() (b autre instance de A).
Pour "résoudre" ça, il suffirait d'inclure une condition sur
l'adresse du vecteur pointé... Mais meme comme ça, ça me dérange,
bien qu'honnètement je ne saurai dire pourquoi.

@ Kanze & Fabien
En lisant ce que vous avez écrit je me rends compte que finalement mon
problème est plus profond et que pour commencer je ne sais pas trop
bien ce qu'on appelle "itérateur". La "solution" proposée par Kanze
avec des fonctions has_next(), next(), value() m'a été proposée par
un collègue qui fait du Java, et il ne démord pas du fait que c'est
là ce qu'on appelle *itérateur*.
Après cogitation, cette solution me semble plus séduisante, parce
qu'elle colle pls évidemment à ce qu'on a envie d'appeller
itérateur.

Donc -arretez moi si je me trompe- tout le tintouin à coup de "++" et
de "*" aurait été proposé par les cerveaux de la STL dans le soucis
de répondre à un autre type de problématique, connexe à celle des
itérateurs, mais pas tout a fait avec le meme cahier des charges. A
première vue ce que je vois comme différence majeure, c'est le fait
qu'un itérateur (au sens java (faute de trouver un meilleur terme) )
est capable de dire quand il est arrivé au bout de sa structure
(fonction has_next) et qu'il n'a pas besoin d'etre comparé à un autre
itérateur pour ce faire; ce qui n'est pas le cas des itérateurs
STL... Quand à savoir en quoi le design de la stl necessitait ces
modifications au paradigme d'itérateur, pour moi c'est encore flou.
Bref, si je ne me trompe pas, les itérateurs sTL ne sont pas à
proprement parler des itérateurs ?!