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++ copie de map dans la STL

copie de map dans la STL

7 réponses
Avatar
Marc G
bonjour,
j'ai une classe X avec une donnée membre de type std::map.
Dans cette map, les clés sont des vector (à peu de chose près) et les
données des pointeurs vers une classe de base d'objets, alloués par new.

Pour simplifier ma prose,
typedef std::map<....> type_map;
type_map data_; // donnée membre


Ma question :

Dans le constructeur de copie de la classe X, comment faire pour "recopier"
la map ?

Choix 1)
X(X const& x)
{
for(type_map::const_iterator it=x.data_.begin();it!=x.data_.end();++it)
data_.insert( /* blablabla */ );
}

ou
Choix 2)
X(X const& x)
{
data_=x.data_;
for(type_map::iterator it1=data_.begin(),
type_map::const_iterator it2=x.data_.begin();
it1!=data_.end();
++it1,++it2)
it1->second=it2->second()->duplicate();
}

je pense que le choix 2 est préférable...mais je voudrais avoir votre avis.
Je ne sais pas comment est implémentée la copie des map dans la STL, mais je
pense qu'elle doit tenir compte du fait que les clés sont déjà triées !

Merci à vous.
Marc
Signaler un problème avec ce contenu

7 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
Avatar
Sylvain Togni

j'ai une classe X avec une donnée membre de type std::map.
Dans cette map, les clés sont des vector (à peu de chose près) et les
données des pointeurs vers une classe de base d'objets, alloués par new.

Pour simplifier ma prose,
typedef std::map<....> type_map;
type_map data_; // donnée membre

Ma question :

Dans le constructeur de copie de la classe X, comment faire pour
"recopier" la map ?

Choix 1)
X(X const& x)
{
for(type_map::const_iterator it=x.data_.begin();it!=x.data_.end();++it)
data_.insert( /* blablabla */ );
}


Ce n'est ni le plus efficace ni le plus élégant.

ou
Choix 2)
X(X const& x)
{
data_=x.data_;
for(type_map::iterator it1Úta_.begin(),
type_map::const_iterator it2=x.data_.begin();
it1!Úta_.end();
++it1,++it2)
it1->second=it2->second()->duplicate();
}


Si les performances sont importantes, pourquoi pas, mais plus simple :

X(X const& x)
: data(x.data)
{
for(type_map::iterator it = data.begin(); it != data.end(); ++it)
it->second = it->second->duplicate();
}

Attention quand même au comportement en cas d'exception.

Si les performances ne sont pas trop importantes, le plus simple
serait d'utiliser des pointeurs intelligents pour stocker les
objets dans la map. Avec un pointeur intelligent qui appelle
duplicate() lors de sa copie, plus besoin de définir de
constructeur de copie pour X.

--
Sylvain Togni

Avatar
Marc G
Si les performances sont importantes, pourquoi pas, mais plus simple :

X(X const& x)
: data(x.data)
{
for(type_map::iterator it = data.begin(); it != data.end(); ++it)
it->second = it->second->duplicate();
}

Attention quand même au comportement en cas d'exception.


je te remercie pour ta simplification :-) !!!
mais si, les performances sont très importantes dans cette application, et
il n'est pas possible pour moi d'utiliser (dans cette portion de code) un
pointeur intelligent, quel qu'il soit ! (et il n'y a pas de risque
d'exception...)

Merci à toi !
Marc

Avatar
James Kanze
On Oct 17, 5:10 pm, "Marc G" wrote:

j'ai une classe X avec une donnée membre de type std::map.
Dans cette map, les clés sont des vector (à peu de chose près) et l es
données des pointeurs vers une classe de base d'objets, alloués par n ew.


Des clés, et non des valeurs ? Parce que des clés, dans un map,
doivent être immutable.

La première question que je me poserais, ici, c'est s'il faut
supporter la copie, parce qu'elle va être chère. (Mais je
suppose que tu t'es déjà posé cette question-là.)

Ensuite, je considèrerais la possibilities de « wrapper »
quelque chose à un niveau plus bas, pour que la copie du map
même soit automatique. Si les objets pointés sont immutable (ce
que j'espère, s'ils servent comme éléments d'une clé dans un
map), un pointeur à comptage de références ferait bien
l'affaire. Si pour une raison quelconque, ça n'est pas
envisagable (mais je ne vois pas quelle raison ça pourrait
être), wrapper le vector dans une classe qui assure la copie
profonde ferait l'affaire.

Pour simplifier ma prose,
typedef std::map<....> type_map;
type_map data_; // donnée membre

Ma question :

Dans le constructeur de copie de la classe X, comment faire pour "recopie r"
la map ?

Choix 1)
X(X const& x)
{
for(type_map::const_iterator it=x.data_.begin();it!=x.data_.end() ;++it)
data_.insert( /* blablabla */ );
}

ou
Choix 2)
X(X const& x)
{
data_=x.data_;
for(type_map::iterator it1Úta_.begin(),
type_map::const_iterator it2=x.data_.begin();
it1!Úta_.end();
++it1,++it2)
it1->second=it2->second()->duplicate();
}


Si c'est les clés que tu veux copier, c'est it->first. Et cette
solution ne marche pas, parce que le type d'it->first est const.

je pense que le choix 2 est préférable...mais je voudrais
avoir votre avis.


J'avoue que pour l'instant, je ne vois pas comment ils
fonctionnent réelement, ni l'un ni l'autre.

Je ne sais pas comment est implémentée la copie des map dans
la STL, mais je pense qu'elle doit tenir compte du fait que
les clés sont déjà triées !


C'est possible. Si j'ai bien compris les sources,
l'implémentation g++ copie directement l'arborescence, sans
faire des insertions. (C-à-d qu'il copie le noeud à la racine,
puis il copie récurisvement les noeuds à gauche et à droite.) Ce
qui argue fort pour s'arranger que la copie de la clé (et de la
valeur) se fait correctement, soit en wrappant le vector, soit
en utilisant des pointeurs intelligents.

En ordre de complexité croissante, donc :

-- Remplacer les pointeurs par un pointeur à comptage de
référence « standard », du genre boost::shared_ptr.

-- Remplacer les pointeurs par un pointeur à comptage de
référence fait sur mesure, avec un compteur invasif. (C'est
la solution la plus rapide en temps d'exécution -- mais
comme la précédente, elle donne une sémantique de référence
à la copie.)

-- Remplacer les pointeurs par un pointeur intelligent à copie
profonde. C'est la plus simple des solutions qui assurent
une vraie copie profonde. C'est aussi probablement la plus
rapide en temps d'exécution.

-- Remplacer le vecteur par une classe qui le wrappe, et qui
assure la copie profonde. Cette solution ne touche pas au
type de vector, et pourrait donc être préférer si la vector
même est visible à l'interface.

-- Implémente la copie profonde complétement dans la classe.
Cette solution implique plus ou moins une boucle imbriquée,
qui itère sur tous les éléments dans le map, puis sur tous
les éléments dans le vecteur, afin d'effectuer une copie
profond du clé, puis insérer le nouveau élément dans le
nouveau map.

Note aussi que techniquement, cette dernière solution se base
sur des comportements indéfinis (bien que j'ai du mal à imaginer
un cas où il fasse problème). Le problème formel, c'est que la
norme exige que les éléments aient des types « Copiable », ce
qui n'est pas réelement le cas d'un vecteur de pointeurs bruts
dont la copie exigerait une copie profonde.

--
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
Christophe Lephay
"James Kanze" a écrit dans le message de news:

On Oct 17, 5:10 pm, "Marc G" wrote:

j'ai une classe X avec une donnée membre de type std::map.
Dans cette map, les clés sont des vector (à peu de chose près) et les
données des pointeurs vers une classe de base d'objets, alloués par new.


Des clés, et non des valeurs ? Parce que des clés, dans un map,
doivent être immutable.


J'ai compris que le pointeur était la donnée et non la clé (la clé étant "un
vector à peu de chose pret").


Avatar
Marc G
La première question que je me poserais, ici, c'est s'il faut
supporter la copie, parce qu'elle va être chère. (Mais je
suppose que tu t'es déjà posé cette question-là.)


oui, il le faut, même si elle sera peu utilisée


Si c'est les clés que tu veux copier, c'est it->first. Et cette
solution ne marche pas, parce que le type d'it->first est const.
J'avoue que pour l'instant, je ne vois pas comment ils
fonctionnent réelement, ni l'un ni l'autre.


je te remercie pour l'effort que tu as fait à me répondre...
Malheureusement, je crois ne pas avoir été assez clair dans ma
formulation...

Voilà plus précisement comment se présente l'ensemble :

class keys {
//......
std::vector<std::string> keys_;
};

class CObject; // c'est une classe de base d'une hiérarchie avec fonctions
virtuelles
class X {
public :
typedef std::map< keys ,CObject*, std::less<keys> > data;

// constructeur de copie
explicit X(Xconst& source)
: data_(source.data_) //<==== ma question était là...
{
for(data_iterator itÚta_.begin();it!Úta_.end();++it)
it->second=it->second->duplicate();
}

~X()
{
for(data_const_iterator itÚta_.begin();it!Úta_.end();++it)
if (it->second) delete it->second;
data_.clear();
}

data data_;
};

je recopie le pointeur avec et ensuite je l'écrase en récupérant l'adresse
de l'objet dupliqué par duplicate().
duplicate() n'a aucun risque de lever une exception...sauf en cas de mémoire
insuffisante.

Si une exception liée à la mémoire est levée, le destructeur est-il appelé ?
Dans ce cas, j'ai plutôt intérêt à écrire

// constructeur de copie
explicit X(Xconst& source)
: data_(source.data_)
{
data_iterator it1Úta_.begin();
data_const_iterator it2=source.data_.begin();
for(;it1!Úta_.end();++it1)
it1->second=NULL;
it1Úta_.begin();
for(;it1!Úta_.end();++it1,++it2)
it1->second=it2->second->duplicate();
}

Qu'en penses-tu ?

Marc

Avatar
James Kanze
On Oct 18, 12:49 pm, "Christophe Lephay" <christophe-
wrote:
"James Kanze" a écrit dans le message de news:

On Oct 17, 5:10 pm, "Marc G" wrote:

j'ai une classe X avec une donnée membre de type std::map.
Dans cette map, les clés sont des vector (à peu de chose près) e t les
données des pointeurs vers une classe de base d'objets, alloués pa r new.


Des clés, et non des valeurs ? Parce que des clés, dans un map,
doivent être immutable.


J'ai compris que le pointeur était la donnée et non la clé (la
clé étant "un vector à peu de chose pret").


En effet. J'avais compris, je ne sais pas pourquoi, que les clés
étaient des vecteurs de pointeurs, mais en ré-regardant ce qu'il
a écrit, je crois m'être trompé. Si le map est bien quelque
chose du genre :
std::map< std::vector< T >, Base* >
, et que les T supporte bien la copie, le problème est bien plus
simple. Encore que si on veut une véritable sémantique de
valeur, je remplacerais des Base* par des pointeurs
intelligents à la sémantique de copie voulue.

--
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
James Kanze
On Oct 18, 11:02 pm, "Marc G" wrote:
La première question que je me poserais, ici, c'est s'il faut
supporter la copie, parce qu'elle va être chère. (Mais je
suppose que tu t'es déjà posé cette question-là.)


oui, il le faut, même si elle sera peu utilisée

Si c'est les clés que tu veux copier, c'est it->first. Et cette
solution ne marche pas, parce que le type d'it->first est const.
J'avoue que pour l'instant, je ne vois pas comment ils
fonctionnent réelement, ni l'un ni l'autre.


je te remercie pour l'effort que tu as fait à me répondre...
Malheureusement, je crois ne pas avoir été assez clair dans ma
formulation...


C'est bien moi qui a mal lu: j'ai lu « les clés sont des vecteurs
des pointeurs », en sautant une partie de ce que tu as écrit.

Voilà plus précisement comment se présente l'ensemble :

class keys {
//......
std::vector<std::string> keys_;
};

class CObject; // c'est une classe de base d'une hiérarchie avec foncti ons
virtuelles
class X {
public :
typedef std::map< keys ,CObject*, std::less<keys> > da ta;


Voilà à mon avis la vraie question : est-ce que ce type fait
partie de l'interface, ou est-ce que tu es libre de le
changer ?

// constructeur de copie
explicit X(Xconst& source)
: data_(source.data_) //<==== ma question était là...


Ça va copier les pointeurs.

{
for(data_iterator itÚta_.begin();it!Úta_.end();++it)
it->second=it->second->duplicate();


En supposant que la fonction second->duplicate() peut lever une
exception (std::bad_alloc, par exemple), ça ne marche pas. En
cas d'exception, le destructeur de X n'est pas appelé, et les
nouveaux objets ne seront jamais detruits. On peut contourner le
problème avec quelque chose du genre :

data::iterator it = data_.begin() ;
try {
while ( it != data_.end() ) {
it->second = it->second->duplicate() ;
++ it ;
}
} catch ( ... ) {
while ( it != data_.begin() ) {
-- it ;
delete it->second ;
}
}

Mais dans l'ensemble, je le trouve peu élégant. Je préfèrerais
de loin un pointeur intelligent, peut-être un qui fait une copie
profond. Voire carrément l'idiom lettre/envéloppe.

}

~X()
{
for(data_const_iterator itÚta_.begin();it!Úta_.end();++it)
if (it->second) delete it->second;


L'if n'est pas nécessaire.

Formellement, laisser le pointeur dans le map après le delete
est un comportement indéfini. Dans la pratique, en revanche, il
ne pose pas de problèmes, et je ne m'y inquièterais pas
outre-mesure.

Et évidemment, avec des pointeurs intelligents, pas besoins de
cette boucle.

data_.clear();


Pas besoin de clear(), non plus. Le destructeur du map s'en
occupe très bien.

}

data data_;
};

je recopie le pointeur avec et ensuite je l'écrase en
récupérant l'adresse de l'objet dupliqué par duplicate().
duplicate() n'a aucun risque de lever une exception...sauf en
cas de mémoire insuffisante.


C-à-d qu'il n'y a aucun risque de lever une exception, sauf dans
les cas où il en lève une:-).

Sérieusement, il y a un problème de fond (peut-être pûrement
théorique) qui me tracasse. C'est que les collections de la
norme exige que les objets dans la collection soit copiables.
Or, si le pointeur est censé être propriétaire de l'objet
pointé (c-à-d que la durée de vie de l'objet est lié à celle du
pointeur, ou à celle de la collection qui contient le pointeur),
un pointeur brut n'est pas copiable, dans le sens de la norme.

Si une exception liée à la mémoire est levée, le destructeur
est-il appelé ?


En cas d'exception, le destructeur de tous les sous-objets
complètement construit est appelé, mais non celui des objets en
cours de construction. Et pour cause : considère ton
constructeur ci-dessus. Si le destructeur d'X serait appelé, il
feras un delete sur des pointeurs qui n'ont pas encore été
dupliqués, ce qui ferait de serieux problèmes dans l'objet qu'on
copie.

La solution classique dans ce genre de cas, c'est d'utiliser un
sous-objet ou classe de base spéciale, genre :


class X
{
struct Data
{
typedef std::map ... data ;

data _data ;
~X_Impl() {
for ( data::iterator it = data.begin() ;
it != data.end() ;
++ it ) {
Base* p = NULL ;
std::swap( it->second, p ) ;
delete p ;
}
} ;
Data _data ;
public:
X( X const& other )
: X_Impl() // Et non le constructeur de copie !
{
for ( Data::data::iterator it = other.data.begin() ;
it != other.data.end() ;
++ it ) {
Data::_data.insert(
Data::data::value_type(
it->first, it->second-
duplicate()) ) ;
}

}
} ;

Du fait que le X::Data a été complètement construit avant de
commencer les insertions, son destructeur sera appelé. Et du
fait qu'il ne contient jamais des pointeurs à des objets qui
appartiennent à l'autre collection, son destructeur fera
toujours exactement ce qu'on veut. (À vrai dire, je ne suis pas
convaincu que cette solution soit préférable à un bloc de try.
Mais les blocs de try, ce n'est pas chic, tandis que tout faire
dans les destructeurs, c'est vraiment in.)

Faire des inserts, plutôt que copier directement, c'est
probablement moins rapide, mais dans ton cas, je préfèrerais
quand même cette solution, jusqu'à ce que le profiler me dit
qu'il ne va pas.

Dans ce cas, j'ai plutôt intérêt à écrire

// constructeur de copie
explicit X(Xconst& source)
: data_(source.data_)
{
data_iterator it1Úta_.begin();
data_const_iterator it2=source.data_.begin();
for(;it1!Úta_.end();++it1)
it1->second=NULL;
it1Úta_.begin();
for(;it1!Úta_.end();++it1,++it2)
it1->second=it2->second->duplicate();
}

Qu'en penses-tu ?


C'est une solution aussi. Mais il me semble un peu subtile, et
assez fragile. Personellement, si l'objet appartient à un X
donné, j'éviterais autant que se peut qu'un autre objet ait un
pointeur à lui, ne serait-ce que de façon passagère. Mais si
vraiment le profiler disait qu'il n'y avait pas le choix,
j'utiliserais un bloc de try, comme ci-dessus.

(En fait, j'imagine que le temps d'exécution va être dominé par
les allocations, et du coup, la différence en temps d'exécution
entre la copie directe et les insertions ne serait pas
apercevable.)

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