Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Conteneur séquentiel et transformation

35 réponses
Avatar
Mickaël Wolff
Bonjour,

Quelle est la raison fondamentale pour laquelle std::transform
nécessite une séquence de sortie pré-dimensionnée ?

Par exemple:

#include <vector>

int main()
{
int ref[] = { 1, 36, 69, 42 } ;

std::vector<int> reference ;
reference.resize(sizeof ref / sizeof *ref) ;

std::transform(ref, ref + reference.size(), reference.begin()) ;
}

Si je n'ajuste pas reference, il reste vide. Dans un exemple plus
complexe, j'ai du segfault: avec des shared_ptr, swap tente d'échanger
le pointeur courant avec le pointeur courant d'un emplacement mémoire
qui n'est pas un shared_ptr.

Je comprends que std::transform ne redimensionne pas mon std::vector
de destination. La raison est-elle qu'on paye pour ce qu'on utilises ?

Au plaisir de vous lire.
--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

10 réponses

1 2 3 4
Avatar
Fabien LE LEZ
On Sun, 08 Aug 2010 03:52:58 +0100, Mickaël Wolff
:

Je comprends que std::transform ne redimensionne pas mon std::vector
de destination.



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

Jette un coup d'oeil là-dessus :
http://www.cplusplus.com/reference/std/iterator/back_inserter/
Avatar
Gabriel Dos Reis
Mickaël Wolff writes:

| Bonjour,
|
| Quelle est la raison fondamentale pour laquelle std::transform
| nécessite une séquence de sortie pré-dimensionnée ?
|
| Par exemple:
|
| #include <vector>
|
| int main()
| {
| int ref[] = { 1, 36, 69, 42 } ;
|
| std::vector<int> reference ;
| reference.resize(sizeof ref / sizeof *ref) ;
|
| std::transform(ref, ref + reference.size(), reference.begin()) ;
| }

template<typename T, int N>
int size(const T(&) [N]) { return N; }

template<typename T, int N>
T* begin(const T(&ary) [N]) { return &ary[0]; }

template<typename T, int N>
T* end(const T(&ary) [N]) { return &ary[0] + N; }

int main()
{
int ref[] = { 1, 36, 69, 42 } ;

std::vector<int> reference(size(ref));
std::copy(begin(ref), end(ref), reference.begin());
}


|
| Si je n'ajuste pas reference, il reste vide. Dans un exemple plus
| complexe, j'ai du segfault: avec des shared_ptr, swap tente d'échang er
| le pointeur courant avec le pointeur courant d'un emplacement mémoire
| qui n'est pas un shared_ptr.

std::vector<int> reference;
std::copy(begin(ref), end(ref), std::back_inserter(reference));

| Je comprends que std::transform ne redimensionne pas mon std::vector
| de destination. La raison est-elle qu'on paye pour ce qu'on utilises ?

Orthogonalité.
La fonction de transform, c'est de transformer les éléments de la suite,
pas de changer la taille de la destination.

-- Gaby
Avatar
Mickaël Wolff
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 ?

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 ?

Merci !

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Avatar
Mickaël Wolff
Il semblerait que ce message ne soit pas passé. Je réitère donc.

Le 08/08/2010 16:53, Gabriel Dos Reis a écrit :

template<typename T, int N>
int size(const T(&) [N]) { return N; }



Rien que pour ça j'ai bien fait de poser la question. Je n'y aurais
pas pensé.

std::vector<int> reference;
std::copy(begin(ref), end(ref), std::back_inserter(reference));



En fait, j'ai trouvé cette réponse quelques minutes après avoir posé
la question dans le bouquin (Effective STL, Scott Meyers) que je lis (et
qui m'a mené à l'observation de std::transform). Mais ça ne répondait
toujours pas à mon interrogation profonde.


| Je comprends que std::transform ne redimensionne pas mon std::vector
| de destination. La raison est-elle qu'on paye pour ce qu'on utilises ?

Orthogonalité.
La fonction de transform, c'est de transformer les éléments de la suite,
pas de changer la taille de la destination.



Ok, c'est ce que je pensais : un problème de responsabilité. Bon, ben
c'est le memcpy du C++ :)

Merci!

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Avatar
Alexandre Bacquart
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 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 ?



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 rappelle rien ?

Dans l'implémentation, un itérateur doit bien conserver des références
vers le conteneur.



Ha bon ? Pourquoi ?

Rien que pour pouvoir progresser dans la collection.



Un pointeur a-t-il besoin de référencer le tableau contenant l'élément
pointé pour progresser dans ce tableau ?

Du coup, à l'instar d'un pointeur habile, il pourrait fournir une
fonction membre vers le conteneur itéré ?



Ca, c'est un pointeur très habile !

Ou encore une fois c'est une question de découplage ?



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


--
Alex
Avatar
Gabriel Dos Reis
Mickaël Wolff writes:

| 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 e t ne pas y avoir
| accès ?

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 »

-- Gaby
Avatar
Gabriel Dos Reis
Alexandre Bacquart 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 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 ?
|
| Un iterator référence un élément du conteneur, pas le conteneur
| lui-même.

Ça on sait pas. Tout ce qu'on sait, c'est que l'itérareur rà ©férence
conceptuellement le conteneur. Que cette référence soit concrete ou non
est un détail d'implémentation. En mode debug, certaines implà ©mentations
font des vérifications d'accès. En mode non-debug, certaines
implémentations utilisent le type du conteneur pour refuser des
opérations douteuses.

-- Gaby
Avatar
Mickaël Wolff
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 rappelle rien ?



Justement, les itérateurs ne sont pas des pointeurs. Sauf dans les
cas particuliers de std::vector et std::string.

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

Rien que pour pouvoir progresser dans la collection.



Un pointeur a-t-il besoin de référencer le tableau contenant l'élément
pointé pour progresser dans ce tableau ?



Un pointeur sur un tableau référence une zone de mémoire contigüe sur
laquelle ont peut appliquer l'algèbre sur les pointeurs. 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.

Ou encore une fois c'est une question de découplage ?



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.

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org
Avatar
Fabien LE LEZ
On Sun, 08 Aug 2010 19:43:29 +0100, Mickaël Wolff
:

Dans l'implémentation, un itérateur doit bien conserver des
références vers le conteneur.



Pas forcément. Certaines implémentations utilisaient un T* comme
itérateur sur un vector<T>. Ça fonctionnait plutôt bien dans la
plupart des cas.
Avatar
Fabien LE LEZ
On Mon, 09 Aug 2010 02:47:20 +0100, Mickaël Wolff
:

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.
1 2 3 4