[stl] une map de list

On Tue, 10 Apr 2007 23:53:39 +0200, "Bruno Causse"
<bcausse@lepoint.tm.fr>:

est que cette conception est valide (pseudo code c++)

typedef std::list < A > tList_A;
typedef std::map< const unsigned long long hash_code, tList_A> tMap_A;

Le "const" est en trop ici, si je ne m'abuse.
En prime, un typedef sur le "unsigned long long" ne serait pas de trop
(Mais peut-être est-ce ce que tu as essayé de faire ?)

typedef unsigned long long HashCode;
typedef std::map<HashCode, tList_A> tMap_A;

la gestion des "copies des objets A" (creation, supression, copie, ...) la
stl s'en charge?

À partir du moment où tu mets des objets dans un conteneur de la STL
(et pas des pointeurs), tu n'as pas à te soucier de leur durée de vie.

"Bruno Causse" <bcausse@lepoint.tm.fr> écrivait:

est que cette conception est valide (pseudo code c++)

Seul du non-pseudo code peut-être valide.

typedef std::list < A > tList_A;
typedef std::map< const unsigned long long hash_code, tList_A> tMap_A;

Attention long long n'est pas standard.

class B{
tMap_A = my_map;
A tab[];
.../...

void add(const unsigned long long hash_code);
void restore(const unsigned long long hash_code);
}


/* sauvegarde d'objets de la table dans une liste
1) existante == rewrite
2) absente == creation
*/
void B::add(const unsigned long long hash_code) {

tList_A my_list;

/*creation d'une liste a partir du hash_code
par copie des objets A contenu dans tab

genre:
for(...)
my_list.push_back(tab[...]); //j'ai une copie

*/
initialise(my_list, hash_code);

my_map.erase(hash_code);
my_map.push_back(my_list); //je supose que j'ai une copie :-(

Une copie ? Ça n'a pas de sens ! où sont le "front" et le "back" d'un arbre,
une std::map<> ?
Ce que tu veux c'est, par exemple :

my_map[has_code]= my_list;

Pour éviter la copie tu écris :

tList_A & my_list(my_map[has_code]);
my_list.clear(); // *Do not* chack my_list.size()
initialise(my_list, hash_code);

avec initialise qui prends une référence sur un(e) tList_A.

Le plus simple :

my_map[has_code]= initialise(hash_code);

avec initialise qui retourne un(e) tList_A.
Y'a-t-il copie ? Ça dépend ! mais qu'importe.

}

/* reecrit les objets dans la table */
void B::restore(const unsigned long long hash_code) {

tMap_A::iterator iter_map = my_map.find(hash_code);

ou tMap_A::iterator const iter_map(my_map.find(hash_code));

if(iter_map != my_map.end()) {
tList_A& my_list = iter_map->second; //pas de copie

ou tList_A const & my_list(iter_map->second);
La syntaxe d'initialisation utilisant le symbole = implique une copie.

for(tList_A::const_iterator iter_list = my_list.begin(); iter_list !=
my_list.end(); iter_list++)
tab[...] = *iter_list;
}

my_map.clear(); //on efface tout

N'est-ce pas un peu tôt ? (Je crois avoir *deviné* ce que tu essaies de
faire...)

}

la gestion des "copies des objets A" (creation, supression, copie, ...) la
stl s'en charge?

oui, c'est bien fait hein ;-)

--
Franck Branjonneau

"James Kanze" <james.kanze@gmail.com> a écrit dans le message de news:
1176364274.262780.240790@o5g2000hsb.googlegroups.com...
On Apr 10, 11:53 pm, "Bruno Causse" <bcau...@lepoint.tm.fr> wrote:

Mais il ne serait pas mal que tu nous expliques exactement ce
que tu essaies de faire. Parce que ce que tu nous montre à l'air
un peu lourd.

bon,

j'ai une table de position (jeux de damier, echec, dame, othello...)
implementée sous une forme de table de hashage (une position est representée
par une clef (24 bits) et un verrou (40bits)).

a partir de cette table je peux rejouer la meilleure variation/refutation
trouvée. Malheuresement cette table n'est pas infinie (2^24) et des
positions importantes peuvent etre reecrite. Je souhaite temporairement
sauvegarder celles ci, pour pouvoir les restaurer.

Dans la pratique, std::map ne copie ni n'affecte les éléments
une fois qu'ils y sont. Il m'est arrivé donc d'utiliser des
std::map< xxx, std::map > ou des std::map< xxx, std::vector >
sans trop de problèmes de lourdeur, en m'assurant que j'insérais
toujours un map ou un vecteur vide, et que j'insérais ensuite
dans l'élément dans le map. Typiquement, avec quelque chose du
genre :
map[ xxx ].push_back( nouvelElement ) ;
ou
map[ xxx ].insert( SubmapType::value_type( yyy, zzz ) ) ;
Je ne suis pas un acharné sur les performance, loin de ça, mais
je n'aime pas trop l'idée d'une copie profonde d'une std::list.
(J'ai eu le cas, une fois, où j'avais une fonction qui renvoyait
mon équivalent pré-norme d'une std::list, avec 60000 éléments.
Ça prenait à peu près 20 sécondes sur la machine à l'époque. Vue
que je ne le faisais que 4 fois dans une application qui
tournait bien plus de trois quarts d'heures, ce n'était pas
grave, mais ça donne à penser quand même.)

le nombre de mouvements (coups) possibles pour une position est <32
une variation (suite de coups) est limité par la puissance des machine a <40

donc au max une map de 32 list de 40 elements (== aucun probleme de perf).

maintemant ca fonctionne, (au moins mecaniquement).
merci

"James Kanze" <james.kanze@gmail.com> a écrit dans le message de news:
1176366978.860748.91630@w1g2000hsg.googlegroups.com...
On Apr 11, 7:36 pm, Franck Branjonneau <fra...@tchume.net> wrote:

Personnellement, j'aimerais savoir d'où vient ces list, et
régarder si je ne pourrais pas les construire in situ,
directement dans la map. C-à-d quelque chose du genre :

std::list<A>& tmp = my_map[ hash_code ] ;
tmp.clear() ;
tmp.push_back( ... ) ;
// ...

c'est exactement ce que j'ai fait :-)

Franck Branjonneau wrote:

Attention long long n'est pas standard.
[...]

Rien à voir avec le post initial, mais y a-t-il un moyen de déclarer un
entier 64 bits de manière standard ?

Y

On Apr 10, 11:53 pm, "Bruno Causse" <bcau...@lepoint.tm.fr> wrote:

est que cette conception est valide (pseudo code c++)

typedef std::list < A > tList_A;
typedef std::map< const unsigned long long hash_code, tList_A> tMap_A;

class B{
tMap_A = my_map;

C'est du pseudo-code, j'imagine, mais je ne suis pas sûr ce que
tu veux représenter ici (au moins que ce soit du vrai code, et
que le '=' s'y est glissé par erreur).

A tab[];
.../...

void add(const unsigned long long hash_code);
void restore(const unsigned long long hash_code);
}

/* sauvegarde d'objets de la table dans une liste
1) existante == rewrite
2) absente == creation
*/
void B::add(const unsigned long long hash_code) {

tList_A my_list;

/*creation d'une liste a partir du hash_code
par copie des objets A contenu dans tab

genre:
for(...)
my_list.push_back(tab[...]); //j'ai une copie

*/
initialise(my_list, hash_code);

my_map.erase(hash_code);
my_map.push_back(my_list); //je supose que j'ai une copie :-(

Tout à fait. Les collections de la STL (comme tout le C++, en
général) travaille avec une sémantique de valeur.

}

/* reecrit les objets dans la table */
void B::restore(const unsigned long long hash_code) {

tMap_A::iterator iter_map = my_map.find(hash_code);
if(iter_map != my_map.end()) {
tList_A& my_list = iter_map->second; //pas de copie
for(tList_A::const_iterator iter_list = my_list.begin(); iter_list !=
my_list.end(); iter_list++)
tab[...] = *iter_list;
}

my_map.clear(); //on efface tout
}

la gestion des "copies des objets A" (creation, supression, copie, ...) la
stl s'en charge?

Tout à fait. Il faut que ton objet A supporte la copie et
l'affectation correctement, évidemment. (Et la destruction, mais
ça, il le faut pour prèsque toutes les utilisations.)

Mais il ne serait pas mal que tu nous expliques exactement ce
que tu essaies de faire. Parce que ce que tu nous montre à l'air
un peu lourd.
Dans la pratique, std::map ne copie ni n'affecte les éléments
une fois qu'ils y sont. Il m'est arrivé donc d'utiliser des
std::map< xxx, std::map > ou des std::map< xxx, std::vector >
sans trop de problèmes de lourdeur, en m'assurant que j'insérais
toujours un map ou un vecteur vide, et que j'insérais ensuite
dans l'élément dans le map. Typiquement, avec quelque chose du
genre :
map[ xxx ].push_back( nouvelElement ) ;
ou
map[ xxx ].insert( SubmapType::value_type( yyy, zzz ) ) ;
Je ne suis pas un acharné sur les performance, loin de ça, mais
je n'aime pas trop l'idée d'une copie profonde d'une std::list.
(J'ai eu le cas, une fois, où j'avais une fonction qui renvoyait
mon équivalent pré-norme d'une std::list, avec 60000 éléments.
Ça prenait à peu près 20 sécondes sur la machine à l'époque. Vue
que je ne le faisais que 4 fois dans une application qui
tournait bien plus de trois quarts d'heures, ce n'était pas
grave, mais ça donne à penser quand même.)

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

On Thu, 12 Apr 2007 09:34:35 +0200, Yann Renard
<yann.renard@irisa.fr>:

y a-t-il un moyen de déclarer un
entier 64 bits de manière standard ?

Non. Il n'y a pas moyen de déclarer un entier de N bits de manière
standard, quelque soit N.

On Apr 11, 7:36 pm, Franck Branjonneau <fra...@tchume.net> wrote:

"Bruno Causse" <bcau...@lepoint.tm.fr> écrivait:

est que cette conception est valide (pseudo code c++)

Seul du non-pseudo code peut-être valide.

typedef std::list < A > tList_A;
typedef std::map< const unsigned long long hash_code, tList_A> tMap_A;

Attention long long n'est pas standard.

Mais si. Il n'est pas dans ISO 14882:2003, mais il fait partie
de la norme C (ISO 9899:1999), et il a été adopté par le comité
C++ pour la prochaine version de la norme C++. Et je ne connais
pas de compilateur C++ actuel qui ne le supporte pas déjà.

Parmi les compilateurs plus anciens, il était pratiquement
universel sous Unix, bien avant même que le comité C l'adopte.
Si tu cibles d'anciennes versions de VC++, en revanche, il faut
effectivement utiliser _int64 ou _uint64 ; la solution la plus
simple dans ce cas-là, c'est un typedef. (Pour des raisons
historiques, par exemple, on trouve toujours GB_longlong dans
mon code, bien que je n'essaie plus de supporter les versions
anciennes de VC++.)

class B{
tMap_A = my_map;
A tab[];
.../...

void add(const unsigned long long hash_code);
void restore(const unsigned long long hash_code);
}

/* sauvegarde d'objets de la table dans une liste
1) existante == rewrite
2) absente == creation
*/
void B::add(const unsigned long long hash_code) {

tList_A my_list;

/*creation d'une liste a partir du hash_code
par copie des objets A contenu dans tab

genre:
for(...)
my_list.push_back(tab[...]); //j'ai une copie

*/
initialise(my_list, hash_code);

my_map.erase(hash_code);
my_map.push_back(my_list); //je supose que j'ai une copie :-(

Une copie ? Ça n'a pas de sens ! où sont le "front" et le "back" d'un arbre,
une std::map<> ?

Je crois qu'il parle d'une copie de la liste. Il y a
effectivement ici une copie profonde de la liste, et std::list,
c'est sans doute ce qui est la plus lente à copier dans la STL.
(On pourrait aussi se démander si std::list est la structure la
plus adoptée à son problème ; je trouve qu'elle ne me sers
jamais. Mais il ne nous a pas dit son problème.)

Ce que tu veux c'est, par exemple :

my_map[has_code]= my_list;

Personnellement, j'aimerais savoir d'où vient ces list, et
régarder si je ne pourrais pas les construire in situ,
directement dans la map. C-à-d quelque chose du genre :

std::list<A>& tmp = my_map[ hash_code ] ;
tmp.clear() ;
tmp.push_back( ... ) ;
// ...

à la place d'affecter ou d'insérer une liste complète.

Pour éviter la copie tu écris :

tList_A & my_list(my_map[has_code]);
my_list.clear(); // *Do not* chack my_list.size()
initialise(my_list, hash_code);

Exactement. (Sauf que j'imagine que my_list, c'est la
conventions de nommage pour un membre, et ici, il ne peut pas
être un membre.)

avec initialise qui prends une référence sur un(e) tList_A.

Le plus simple :

my_map[has_code]= initialise(hash_code);

avec initialise qui retourne un(e) tList_A.
Y'a-t-il copie ? Ça dépend ! mais qu'importe.

Il y a copie. Probablement deux fois, au moins. Si la liste est
longue, ça peut très bien importer. Même si elle est
rélativement courte, ça peut mener à une fragmentation de
l'espace libre.

En général, je suis assez soupçonneux des fonctions qui
renvoient des collections. Ça va bien tant qu'il s'agit des
std::string ou des std::vector, pas trop grand (disons quelque
centains d'éléments). Mais c'est à peu près la limite. J'aurais
une tendance à écrire mon code comme si std::list n'avait pas de
constructeur de copie.

(En fait, dans la mesure que les collections ont des fonctions
non const, on pourrait arguer que leur sémantique comporte
l'identité, et qu'elles ne doivent pas supporter la copie et
l'affectation. Seulement, les collections ne sont pas tant des
objets, au sens OO, mais plutôt des composants de base (des
« building blocks », mais je ne trouve pas d'expression
équivalente en français), dont les utilisations sont multiples,
et comprenent aussi des contextes où la copie se comprend et se
justifie.)

}

/* reecrit les objets dans la table */
void B::restore(const unsigned long long hash_code) {

tMap_A::iterator iter_map = my_map.find(hash_code);

ou tMap_A::iterator const iter_map(my_map.find(hash_code));

if(iter_map != my_map.end()) {
tList_A& my_list = iter_map->second; //pas de copie

ou tList_A const & my_list(iter_map->second);
La syntaxe d'initialisation utilisant le symbole = implique une copie.

Pas quand on initialise une référence. (Pas forcément autrement
non plus.)

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

"James Kanze" <james.kanze@gmail.com> écrivait:

Attention long long n'est pas standard.

Mais si. Il n'est pas dans ISO 14882:2003,

N'est-ce pas contradictoire ?

mais il fait partie de la norme C (ISO 9899:1999), et il a été adopté par le
comité C++ pour la prochaine version de la norme C++.

Ma machine à voyager dans le temps est en panne, je n'arrrive pas à me
projeter en 0x.

Et je ne connais pas de compilateur C++ actuel qui ne le supporte pas déjà.

En le documentant comme un extension ?

echo "int main() { long long ll; }" | g++ -x c++ --std=c++98 --pedantic -

my_map.push_back(my_list); //je supose que j'ai une copie :-(

Une copie ? Ça n'a pas de sens ! où sont le "front" et le "back" d'un arbre,
une std::map<> ?

Je crois qu'il parle d'une copie de la liste.

Oui. Et moi je parle de std::map<>::push_back !

Personnellement, j'aimerais savoir d'où vient ces list, et
régarder si je ne pourrais pas les construire in situ,
directement dans la map.

Lis attentivement le PO.

(Sauf que j'imagine que my_list, c'est la conventions de nommage pour un
membre, et ici, il ne peut pas être un membre.)

Le PO n'utilise pas ta convention ;-)

Mais c'est à peu près la limite. J'aurais une tendance à écrire mon code
comme si std::list n'avait pas de constructeur de copie.

Ça n'entre pas dans la catégorie des optimisations prématurées ?

(des « building blocks », mais je ne trouve pas d'expression équivalente en
français),

Briques ?

ou tList_A const & my_list(iter_map->second);
La syntaxe d'initialisation utilisant le symbole = implique une copie.

Pas quand on initialise une référence.

Je sais maintenant pourquoi, avant de me relire, j'avais mis des parenthèses
autour de cette phrase ;-)

(Pas forcément autrement non plus.)

Vraiment ?

--
Franck Branjonneau

"James Kanze" <james.kanze@gmail.com> a écrit dans le message de news:
1176450520.771800.293620@l77g2000hsb.googlegroups.com...

a partir de cette table je peux rejouer la meilleure variation/refutation
trouvée. Malheuresement cette table n'est pas infinie (2^24) et des
positions importantes peuvent etre reecrite. Je souhaite temporairement
sauvegarder celles ci, pour pouvoir les restaurer.

Et quel est le rôle de la liste, là-dedans ?

betement, c'est la structure qui me semble la plus "naturelle".

une suite de coups n'est elle pas une liste? on la cree, parcoure dans
l'ordre du debut a la fin

Certe un vector convient aussi.