container à clé

On Tue, 6 Jan 2004 17:05:46 +0100, "Guillaume Gourdin" <toto@toto.com>
wrote:

Or, je n'ai pas besoin de ce tri

Tu n'en as pas besoin, ou tu veux absolument l'éviter ?
[Pour info, il sert surtout à optimiser la recherche de clef]

, je veux juste ajouter les
nouveaux objets "à la fin" du container. J'ai bien sûr besoin de la fonction
de récupération d'un objet via une clé.

struct Paire
{
Clef clef;
Objet objet;
};
// Note : on pourrait aussi utiliser std::pair<> ; je le trouve assez
désagréable, mais c'est peut-être parce que l'implémentation de
std::pair sur mon compilo est mauvaise

class ChercheClef
{
public:
bool operator () (Paire const& p) const { return p.clef == clef; }
ChercheClef (Clef& c) : clef (c) {}
private:
Clef clef;
};

Le conteneur s'appelle std::vector<Paire> (ou deque, ou list), et la
std::find_if (v.begin(), v.end(), ChercheClef (clef_a_chercher));

Evidemment, comme il n'y a pas de tri, c'est nettement moins efficace
que std::map.

Autre solution : utiliser std::map<> (voire multimap<>), mais rajouter
à l'objet l'ordre d'entrée (puisque cette information est perdue lors
de l'insertion dans le map<>) sous forme d'un entier.

--
;-)

http://www.gotw.ca/gotw/063.htm
http://www.gotw.ca/gotw/067.htm#2

Bonjour, je suis à la recherche d'un container qui permet d'ajouter un
objet et une clé associée (en l'occurence, il s'agit d'un entier). J'ai
pensé à std::map, mais d'après ce que j'ai lu, les objets sont triés à
l'insertion dans la map. Or, je n'ai pas besoin de ce tri, je veux juste
ajouter les nouveaux objets "à la fin" du container. J'ai bien sûr besoin
de la fonction de récupération d'un objet via une clé.

En utilisant "std::vector" :

#include <vector>
#include <string>
#include <iostream>
#include <ostream>

template <class K, class V>
class my_pair
{
public:

my_pair(const K& k, const V& v) : key(k), value(v) { }
my_pair(const my_pair& p) : key(p.key), value(p.value) { }

const bool operator==(const K& k) const { return (key == k); }

K key;
V value;
};

int main()
{
typedef my_pair <int, std::string> couple;
std::vector <couple> liste;

liste.push_back(couple(123, "un, deux, trois"));
liste.push_back(couple(456, "quatre, cinq, six"));

// Recherche d'une clé
std::vector <couple>::const_iterator it std::find(liste.begin(), liste.end(), 123);

if (it != liste.end())
std::cout << "trouvé : " << (*it).value << std::endl;
else
std::cout << "non trouvé" << std::endl;
}


Vincent

--
vmime, une bibliothèque C++ sous licence GPL pour parser et générer
des messages au format MIME : http://www.sourceforge.net/projects/vmime/

Vous pensez à quel container ?

Une autre possibilité un peu plus couteuse en mémoire, mais plus rapide :

class MonContainer
{
public:
Objet GetByIndex(int index) { return objets[index]; }
Objet GetByClef(Clef clef) { return GetByIndex(GetIndexOf(clef)); }
int GetIndexOf(Clef clef) { return clefToIndex[clef]; }

int size() { return objets.size(); }
int Add(Clef clef, Objet objet)
{
objets.push_back(objet);
clefToIndex.insert(clef, size()-1);
return size()-1;
}
private:
std::map<Clef, int> clefToIndex;
std::vector<Objet> objets;
};

Fabien LE LEZ wrote:

struct Paire
{
Clef clef;
Objet objet;
};
// Note : on pourrait aussi utiliser std::pair<> ; je le trouve assez
désagréable,

Moi aussi, principalement parce que les champs sont nommés de manière
positionnelle et non pas en vertu de leur rôle. J'aurais préféré key et
value.

mais c'est peut-être parce que l'implémentation de
std::pair sur mon compilo est mauvaise

Pour une classe si simple, j'ai du mal à voir en quoi l'implémentation
pourraît être mauvaise...

--
Loïc

Dans news:btf5hp$qls$1@news-reader3.wanadoo.fr, Loïc

Fabien LE LEZ wrote:

// Note : on pourrait aussi utiliser std::pair<> ; je le trouve
assez désagréable,

Moi aussi, principalement parce que les champs sont nommés de
manière positionnelle et non pas en vertu de leur rôle. J'aurais
préféré key et value.

Même quand une des deux valeurs est un bool indiquant le succès
de l'opération (map::insert) ? La solution propre est peut-être
de ne pas avoir de pair si « générique »...

--
Michel Michaud mm@gdzid.com
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/

On Tue, 06 Jan 2004 21:28:46 +0100, Loïc Joly
<loic.actarus.joly@wanadoo.fr> wrote:

mais c'est peut-être parce que l'implémentation de
std::pair sur mon compilo est mauvaise

Pour une classe si simple, j'ai du mal à voir en quoi l'implémentation
pourraît être mauvaise...

En fait, j'ai un souci, que je suppose venir de l'implémentation de la
STL sur mon compilo : je ne peux pas faire de
std::vector<std::pair<>>, le compilo râle parce que
std::pair<machin,truc> n'a pas de constructeur par défaut.

--
;-)

http://www.gotw.ca/gotw/063.htm
http://www.gotw.ca/gotw/067.htm#2

On Tue, 6 Jan 2004 15:56:13 -0500, "Michel Michaud" <mm@gdzid.com>
wrote:

La solution propre est peut-être
de ne pas avoir de pair si « générique »...

Je suis assez d'accord, c'est pour ça que je ne l'utilise pas ;-)
Du coup std::pair<> est chez moi systématiquement un *itérateur.

--
;-)

http://www.gotw.ca/gotw/063.htm
http://www.gotw.ca/gotw/067.htm#2

Fabien LE LEZ <gramster@gramster.com> wrote in message
news:<8h1nvv441utmn3q161208t4gafkjmd81kv@4ax.com>...

On Tue, 06 Jan 2004 21:28:46 +0100, Loïc Joly
<loic.actarus.joly@wanadoo.fr> wrote:

mais c'est peut-être parce que l'implémentation de std::pair sur
mon compilo est mauvaise

Pour une classe si simple, j'ai du mal à voir en quoi
l'implémentation pourraît être mauvaise...

En fait, j'ai un souci, que je suppose venir de l'implémentation de la
STL sur mon compilo : je ne peux pas faire de
std::vector<std::pair<>>, le compilo râle parce que
std::pair<machin,truc> n'a pas de constructeur par défaut.

Ce qui est normal. En revanche, on ne doit pas avoir besoin d'un
constructeur par défaut pour s'en servir dans un std::vector.

En passant, j'utilise assez souvent quelque chose du genre :

struct KeyValuePair
{
std::string key ;
int value ;

typedef std::map< std::string, int >::value_type
MapElement ;
operator MapElement() const
{
return MapElement( key, value ) ;
}
} ;

Le grand avantage, à mon avis, c'est que ça permet l'initialisation
comme pour un aggloméré :

static KeyValuePair const
initTable[] {
{ "Toto", 42 } ,
{ "Titi", 12 } ,
// ...
} ;
std::map< std::string, int >
map( begin( initTable ), end( initTable ) ) ;

--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

On 7 Jan 2004 02:12:21 -0800, kanze@gabi-soft.fr wrote:

En revanche, on ne doit pas avoir besoin d'un
constructeur par défaut pour s'en servir dans un std::vector.

Yep. Un jour, quand j'aurai le courage (et abandonné OWL au profit de
wxWindows), je changerai de compilo. En attendant, il m'arrive de
déclarer des constructeurs par défaut (sans les définir) pour des
classes contenues dans std::vector<> :-/

--
;-)

Guillaume Gourdin <toto@toto.com> wrote:

dans la map. Or, je n'ai pas besoin de ce tri, je veux juste ajouter les
nouveaux objets "? la fin" du container. J'ai bien s?r besoin de la fonction
de r?cup?ration d'un objet via une cl?.

Je crois que ce que tu as besoin de, c'est un container ``hash''. Ca
n'existe pas (malheureusement) dans la bibliotheque Standard, mais, si
mon memoire me sert correctement, dans la STL de SGI (hash_map). Un
hash c'est un container comme un map sauf que les objets ne sont pas
triees. Toutefois, il n'y a pas de ``fin'' dans un hash...

-Gerhard