Conteneur séquentiel et transformation

Mickaël Wolff <mickael.wolff@laposte.net> writes:

| Le 09/08/2010 02:03, Gabriel Dos Reis a écrit :
|
| > L'itérateur a conceptuellement accès au conteneur. Ils ont été inventés
| > justement pour ça : comme lien entre les algorithmes et les conten eurs,
| > de sorte à transformer un problème de complexité « n x p » en un
| > problème de complexité « n + p »
|
| Donc pourquoi ne pas permettre l'accès au conteneur auquel
| l'itérateur est rattaché ?

Tu veux dire une fonction qui retourne une référence sur le conte neur
dont provient l'itérateur ? Mis à part le fait que cela devient une
interface très lourde -- tu es sensé savoir d'où tes ità ©rateurs
viennent -- cela impliquerait que les pointeurs ne seraient pas des
itérateurs....

| Ça pourrait être utile de vérifier qu'un
| itérateur est issu d'un conteneur plutôt qu'un autre.

Oui, mais tu es sensé le savoir et écrire du code qui n'a pas bes oin de
faire un tel test.

Conceptuellement, un itérateur est une abstraction locale. Si tu une
interface oà tu dois te trimbaler des itérateurs de gauche à droite et
tu en es à te demander d'où un itérateur, alors je crois que tu as un
problème de design, et ce n'est pas cette fonction qui va arranger les
choses.

| Par exemple :
|
| std::vector<animal> chats ;
| chats.push_back(animal("Chouette")) ;
| auto miaou = chats.begin() ; // C++1x, je suis une fainéasse :D
|
| std::vector<animal> chiens ;
| chiens.push_back(animal("Roudoudou") ;
| auto woof = chats.begin() ;
|
| // On fait plein de choses intéressantes, et quelque part:
| chats.erase(woof) ; // Paf! le chien.
|
| Certainement un comportement indéfini. Comment puis-je vérifi er
| qu'un itérateur appartient bien à une séquence ? Et je par le de
| l'itérateur, pas de sa valeur. Je dois être passé à c ôté de l'outil
| magique.

Tu ne devrais pas écrire du code comme cela :-)
Encore une fois, un itérateur est une abstraction locale (de bas nivea u.)
Si tu as besoin de manipuler des conteneurs directement, écris une
abstraction qui fait cela. Ne sépare pas l'iérateur du conteneur au
point de te mélanger les pinceaux.

-- Gaby

Alexandre Bacquart <tek512@free.DELETEME.fr> writes:

| On 08/09/2010 03:07 AM, Gabriel Dos Reis wrote:
| > Alexandre Bacquart<tek512@free.DELETEME.fr> writes:
| >
| > | On 08/08/2010 08:43 PM, Mickaël Wolff wrote:
| > |> Le 08/08/2010 06:38, Fabien LE LEZ a écrit :
| > |>
| > |>> Comment le pourrait-il ? Tu ne lui passes pas le vector en questio n,
| > |>> mais juste un itérateur.
| > |>
| > |> Justement, c'est un truc que je ne comprends toujours pas. Comment un
| > |> itérateur peut à la fois référencer un conteneu r et ne pas y avoir accès ?
| > |
| > | Un iterator référence un élément du conteneur, pa s le conteneur
| > | lui-même.
| >
| > Ça on sait pas.
|
| Pourtant, quand je déréférence un itérateur (*it), je n'obtiens jamais
| le conteneur.

et alors ?

| Il y en a qui le font ?

y en a qui font quoi ?

| Si oui, quelle est leur utilité ?

utilité de quoi ?

| Autrement dit, quel termes précis dois-je employer pour faire la
| différence entre les "références" qui semblent être l 'objet de notre
| désaccord ? Plus précisément, moi, je parle de "réf érence" à un

Tu as utiliser le *verbe* « référencer » -- c'est pas p areil :-)

| élément d'un conteneur dans le sens où elle peut être déréférencée (je
| suis pas sûr que ce mot soit français et mon dictionnaire est f oireux,
| désolé) avec (*it), toi tu parles d'une "référence" h ypothétique au

« conceptuel » -- et non « hypothétique. Note que j'ut ilise le
verbe :-)

| conteneur qui serait interne à l'itérateur (sans interface dans
| l'itérateur pour y accéder, donc).

Exact.

-- Gaby

Mickaël Wolff <mickael.wolff@laposte.net> writes:

| Le 08/08/2010 23:50, Alexandre Bacquart a écrit :
|
| > Un iterator référence un élément du conteneur, pas le conteneur
| > lui-même. Tu connais bien C si je ne m'abuse, ça ne te rappel le rien ?
|
| Justement, les itérateurs ne sont pas des pointeurs. Sauf dans les
| cas particuliers de std::vector et std::string.

Et encore.

| >> Dans l'implémentation, un itérateur doit bien conserver des références
| >> vers le conteneur.
| >
| > Ha bon ? Pourquoi ?
|
| En effet, en y réfléchissant, il n'y pas besoin. Si l'ità ©rateur
| garde une référence vers la structure enveloppant la valeur, on a pas
| besoin de référencer le conteneur. Puisqu'on a accès au su ivant ou
| précédent (selon le type d'élément). Du coup ça m'explique même
| pourquoi conteneur ne fournit pas forcément un itérateur à accès
| aléatoire.

Une implémentation peut légitimement implémenter
std::vector<T>::iterator comme une paire de
« reference vers vector, indice » et faire des vérification à chaque
opération. Mais c'est un détail d'implémentation.

-- Gaby

Si on veut demeler tout ca, je crois qu'il faut faire du standardese...

A savoir, il y a une spec (la norme), et des implementations. La spec
demande "un minimum", et les implementations peuvent en faire plus.

Pour le cas de l'iterateur, on a par exemple, std::vector.

Tout ce que la norme demande a l'iterateur, c'est de pouvoir etre
incremente/decremente (ou avance/recule plus bourrinement), et dereference.
Une implementation *peut* rajouter des verifications supplementaires (en
particulier pour le debug, mais ca n'est pas obligatoire.

Si on prend "le modele de base" de std::vector, notre vieux tableau C
int t[10];
une implementation a minima d'un iterateur sera un bete pointeur sur un
element du tableau, e.g., int *p = t + 5;

bonne chance pour retrouver le tableau lui-meme a partir du pointeur.

et pourtant, ca suffit pour avoir un iterateur conforme a la norme.


1/ en oubliant bien sur la couche d'abstraction supplementaire, puisqu'il faut
pouvoir resizer le tableau, mais bon, si on a un pointeur sur le tableau
sous-jacent a vector, l'iterateur peut tres bien etre pointeur sur l'element
du tableau.

2/ et un vector a forcement un tableau C comme implementation sous-jacente.
Pas dans C++98, mais c'est une des precisions du TR1 si ma memoire est bonne...

In article <4c5f5dc8$0$652$426a34cc@news.free.fr>,
Mickaël Wolff <mickael.wolff@laposte.net> wrote:

Le 09/08/2010 02:03, Gabriel Dos Reis a écrit :

L'itérateur a conceptuellement accès au conteneur. Ils ont été inventés
justement pour ça : comme lien entre les algorithmes et les conteneurs,
de sorte à transformer un problème de complexité « n x p » en un
problème de complexité « n + p »

Donc pourquoi ne pas permettre l'accès au conteneur auquel
l'itérateur est rattaché ? Ça pourrait être utile de vérifier qu'un
itérateur est issu d'un conteneur plutôt qu'un autre. Par exemple :

Parce qu'on veut que les gens utilisent la STL !

Si tu imposes a l'implementation qu'on peut retrouver le conteneur a partir
de l'iterateur, ca augmente fortement la taille de l'iterateur. Ca va donc
te faire des implementations bien plus lentes (a chaque fois que tu copies
un iterateur, tu deplaces deux fois plus de memoire). Tu vas me dire qu'un
compilo correct est cense pouvoir optimiser ca et que le passage par
reference n'est pas fait pour les chiens, mais bon, dans l'ensemble, ca
complique (en particulier, peut-etre que le compilo va avoir mal a crane
grace aux iterateurs et oublier d'optimiser d'autres choses... de facon
plus concrete, les compilo ont fait pas mal de progres quant a l'optimisation
des petites structures de donnees ces dernieres annees, mais auparavant,
il y avait de vraies grosses differences en performance entre un scalaire
et une structure a deux champs).

Au final, l'utilisateur un peu soucieux de performance va se retrouver a
reecrire ses propres iterateurs dans les cas ou la STL ne va pas assez
vite.

Vu qu'un des buts de la STL c'est quand meme de fournir une implementation
avec un cout d'abstraction le plus faible possible, ca serait dommage...

Deja, tu peux etre sur que les gens vont revenir sur des tableaux C si la
STL te coute des que tu veux parcourir ton vecteur.

Egalement, rien que le cout des tableaux dynamiques est trop cher pour
certaines applis, d'ou les extensions de Boost et autres pour avoir "la
meme chose" en taille fixe... fort heureusement, le modele des iterateurs
de la STL est suffisamment bien concu (et leger!) pour que tu puisses
utiliser ces tableaux de facon compatible... et donc reserver les tableaux
C aux cas ou tu dois 'interfacer avec du code deja ecrit (et encore, tu
as le choix).

In article <4c5f5c2e$0$29879$426a74cc@news.free.fr>,
Mickaël Wolff <mickael.wolff@laposte.net> wrote:

Le 08/08/2010 23:50, Alexandre Bacquart a écrit :

Comme pour un pointeur. La sémantique est d'ailleurs étrangement proche,
non ? Itérateur ou pointeur, on dirait parfois le même objet, mais
déclaré différemment...

Sauf que ce n'est pas le même concept.

ce que visiblement tu n'as pas l'air de comprendre, c'est que le but
des iterateurs n'est pas de *rajouter* des choses au concept de pointeur,
c'est juste de pondre une abstraction qui permet d'eviter de se
preoccuper de details d'implementation scabreux (et suffisamment robuste
pour avoir des implementations de qualite qui embarquent un mode debug
utilisable)...

On pourrait aussi embarquer trois caravanes, deux chiens savants et un
raton-laveur dans chaque iterateur, ca ferait rire les enfants,
mais ca serait moins efficace.

On Aug 8, 7:43 pm, Mickaël Wolff <mickael.wo...@laposte.net> wrote:

Le 08/08/2010 06:38, Fabien LE LEZ a écrit :

> Comment le pourrait-il ? Tu ne lui passes pas le vector en
> question, mais juste un itérateur.

Justement, c'est un truc que je ne comprends toujours pas.
Comment un itérateur peut à la fois référencer un conteneur et
ne pas y avoir accès ?

Pourquoi faut-il que l'itérateur ait accès à la collection ?
Pourquoi faut-il même qu'il y ait une collection ? L'itérateur
de sortie de std::transform pourrait bien être un
std::ostream_iterator, par exemple.

Dans l'implémentation, un itérateur doit bien conserver des
références vers le conteneur. Rien que pour pouvoir progresser
dans la collection. Du coup, à l'instar d'un pointeur habile,
il pourrait fournir une fonction membre vers le conteneur
itéré ? Ou encore une fois c'est une question de découplage ?

Dans les premières implémentations, std::vector::iterator
n'était qu'un typedef à T*. Comment est-ce qu'il aurait pû
fournir une fonction member vers la collection ? La
« collection » d'un std::ostream_iterator, c'est bien un fichier
sur disque. Est-ce qu'il pourrait fournir un pointeur vers une
collection conforme à la STL ?

--
James Kanze

On Aug 9, 10:07 am, es...@lain.home (Marc Espie) wrote:

Si on veut demeler tout ca, je crois qu'il faut faire du
standardese...

A savoir, il y a une spec (la norme), et des implementations.
La spec demande "un minimum", et les implementations peuvent
en faire plus.

Pour le cas de l'iterateur, on a par exemple, std::vector.

Tout ce que la norme demande a l'iterateur, c'est de pouvoir
etre incremente/decremente (ou avance/recule plus
bourrinement), et dereference.

Et de pouvoir se comparer avec un autre itérateur, afin de
connaître quand on a terminé l'itération.

Une implementation *peut* rajouter des verifications
supplementaires (en particulier pour le debug, mais ca n'est
pas obligatoire.

Si on prend "le modele de base" de std::vector, notre vieux tableau C
int t[10];
une implementation a minima d'un iterateur sera un bete pointeur sur un
element du tableau, e.g., int *p = t + 5;

bonne chance pour retrouver le tableau lui-meme a partir du
pointeur.

et pourtant, ca suffit pour avoir un iterateur conforme a la
norme.

1/ en oubliant bien sur la couche d'abstraction
supplementaire, puisqu'il faut pouvoir resizer le tableau,

Pas à partir de l'itérateur.

mais bon, si on a un pointeur sur le tableau sous-jacent
a vector, l'iterateur peut tres bien etre pointeur sur
l'element du tableau.

2/ et un vector a forcement un tableau C comme implementation
sous-jacente. Pas dans C++98, mais c'est une des precisions
du TR1 si ma memoire est bonne...

Tout à fait. Et c'était le cas de toutes les implémentations
avant. Certaines, même, où l'implémentation de
std::vector::iterator était tout bonnement un typedef à T*.

--
James Kanze

On Aug 9, 6:43 am, Fabien LE LEZ <grams...@gramster.com> wrote:

On Mon, 09 Aug 2010 02:47:20 +0100, Mickaël Wolff
<mickael.wo...@laposte.net>:

>Un itérateur est un objet qui référence un objet dans une
>collection. Et une collection n'est pas forcément contigüe.

Prenons un exemple : std::list<T>, une liste doublement chaînée.

À partir d'un itérateur, on doit pouvoir trouver l'élément
pointé, et construire un itérateur vers l'élément suivant et
l'élément précédent.

En d'autres termes, les données membres peuvent se résumer à :

class iterateur
{
T* element_pointe;
iterateur* precedent;
iterateur* suivant;
};

Ça permet de naviguer sur l'ensemble des éléments contenus,
sans jamais avoir un pointeur sur le std::list<T> proprement
dit.

Ou plutôt :

class iterator
{
std::list<T>::node* current;
// et l'interface public.
} ;

Ensuite, l'itérateur est friend de std::list<>, et toutes les
informations nécessaires se trouvent dans list<>::node.

--
James Kanze

espie@lain.home (Marc Espie) writes:

[...]

| Si tu imposes a l'implementation qu'on peut retrouver le conteneur a part ir
| de l'iterateur, ca augmente fortement la taille de l'iterateur.

Surtout que cela me semble donner lieu à du code spaghetti.

-- Gaby