Discussion :

[camboui]

Je cherche à faire un std::set<> très simple, son contenu serait ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
	struct StringId
	{
		std::string s_value;
		unsigned s_id;
		friend bool operator<(StringId const & rl, StringId const & rr)
		{
			return rl.s_value<rr.s_value;
		}
	};
 
...
 
std::set<StringId> collection;

Le but serait de construire une collection de string en associant un id unique à chaque string, puis de retrouver le string à partir de son id. Dans un cas la clé est le string, dans l'autre l'id.
En général j'utilise deux containers mais je me demande s'il n'y a pas plus simple, plus efficace, moins gourmant en resources, etc.
Merci.

[Nogane]

Bonjour,
Il me semble que c'est ce que propose boost.bimap.
http://www.boost.org/doc/libs/1_43_0...tml/index.html

[koala01]

Salut,

Ceci dit, si tu ne souhaite pas avoir "simplement" avoir une relation bidirectionnelle entre deux collections, mais bien disposer de plusieurs index pour un seul et même objet, tu peux également envisager le multi-index de boost:

Soit une structure (finlament très classique pour l'exemple):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
/* ce pourrait être une classe ;) */
struct
{
    unsigned int id;
    std::string nom;
    std::string prenom;
    date_time DN;
};

multiset te permet d'avoir une clé "primaire" sur id (qui sera une valeur unique) et autant de clés secondaires que tu le souhaites (et que la structure te permet de définir ), comme le nom, le prénom ou la date de naissance.

En effet, même quand on s'appelle philippe, ou que son nom de famille est dunski, il est très facile de trouver quelqu'un portant le même prénom ou le même nom de famille (et je tairai ma date de naissance )

[camboui]

Super, magnifique, et en plus j'ai le choix !

Boost::bimap semble être ce qu'il faut pour résoudre pour problème du jour en 5 minutes. Cependant multi-index m'a l'air plus général et convient aussi pour faire du bimap.

Comme j'ai pas le temps aujourd'hui de tout lire, c'est le compilo qui décide: bimap est trop récent pour msvc6, va donc pour multi_index (dans un premier temps).

...

J'ai un container qui contient un string et un identifiant. Problème d'insertion si l'identifiant est auto-incrémenté, il faut d'abord vérifier si le string est déjà dans le bimap avant de l'insérer avec son identifiant auto-incrémenté. Est-il possible d'éviter cette recherche préalable ?
Par exemple comme ceci (sans avoir vérifié la syntaxe exacte):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

container.insert("abc", container.size()+1);

[koala01]

Super, magnifique, et en plus j'ai le choix !

Boost::bimap semble être ce qu'il faut pour résoudre pour problème du jour en 5 minutes. Cependant multi-index m'a l'air plus général et convient aussi pour faire du bimap.

Comme j'ai pas le temps aujourd'hui de tout lire, c'est le compilo qui décide: bimap est trop récent pour msvc6, va donc pour multi_index (dans un premier temps).

Peut être serait il intéressant d'envisager de migrer vers un compilateur plus récent, non

Enfin, je dis cela, mais je sais que le choix ne t'appartient peut être pas
...

J'ai un container qui contient un string et un identifiant. Problème d'insertion si l'identifiant est auto-incrémenté, il faut d'abord vérifier si le string est déjà dans le bimap avant de l'insérer avec son identifiant auto-incrémenté. Est-il possible d'éviter cette recherche préalable ?

Peut on estimer qu'il y a un rapport directe entre la chaine de caractères et l'identifiant

Bon, je m'explique: peut on dire que deux chaines totalement identiques auront fatalement un identifiant identique, ou, au contraire (un peu comme le prénom de la structure que je présentais plus haut), court-on le risque de voir plusieurs chaines de caractères identiques être reliées à plusieurs identifiants (il y a plus d'un âne qui s'appelle Henri, parrait il )

D'après ta question, j'aurais tendance à dire que nous sommes effectivement face au cas où une chaine donnée n'est jamais reliée qu'à un seul identifiant, mais je préfère avoir une certitude

Si tel est le cas, je me dis que bimap serait effectivement bien plus intéressant à utiliser

Mais il me semble que tu pourrais envisager d'implémenter quelque chose prenant la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* j'ai la flegme d'écrire tous ces espaces de noms :P */
using namespace ::boost;
using namespace ::boost::multi_index;
using namespace std;
struct MyStruct
{
    MyStruct(int i, std::string const & s):index(i),str(s){}
    int index;
    std::string str;
    bool operator<(const MyStruct& e)const{return index<e.index;}
 
};
typedef multi_index_container
    <
        MyStruct,
        indexed_by
        <
            ordered_unique< identity < MyStruct > >,
            ordered_unique
            < member   < MyStruct, std::string,&MyStruct::str > >
         >
    > set;
ostream & operator<<(ostream & ofs, MyStruct const & s)
{
    ofs<<s.index<<" "<<s.str<<endl;
    return ofs;
}
int main()
{
    set s;
    s.insert(MyStruct(1,"salut"));
    s.insert(MyStruct(2,"monde"));
    s.insert(MyStruct(3,"world"));
    const set::nth_index<0>::type& index=s.get<0>();
    const set::nth_index<1>::type& name=s.get<1>();
    cout<<"tries par index"<<endl;
    std::copy(
    index.begin(),index.end(), ostream_iterator<MyStruct>(std::cout));
    cout<<"tries par chaine "<<endl;
    std::copy(
    name.begin(),name.end(), ostream_iterator<MyStruct>(std::cout));
    return 0;
}

Mais cela rend bien compte du fait que, dans ce cas particulier, la bimap est très largement plus facile à utiliser

[camboui]

J'ai un ensemble de chaines (voire une seule) qui doivent être associées à un identifiant unique. Si la chaine est seule elle ne peut exister qu'une seule fois. S'il y en a plusieures, elles doivent constituer un ensemble unique. Comme tu le disais, il peut y avoir plusieurs "âne"(s), plusieurs "Henri" mais un seul "âne Henri".
Le bimap est de fait la solution la plus appropriée pour ce problème précis, mais les multi_index sont très intéressants aussi, il seront utiles à l'avenir. Merci de m'avoir fait connaître les deux.


Ceci dit, j'ai un autre problème connexe.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct AnimalNom
{
	std::string s_animal, s_nom;
	friend bool operator<(AnimalNom const & rl, AnimalNom const & rr)
	{
		if (rl.s_animal==rr.s_animal)
			return rl.s_nom<rr.s_nom;
		return rl.s_animal<rr.s_animal;
	}
};
 
...
 
boost::bimap<AnimalNom, unsigned> bm;

Dans ce cas de figure, comme "Henri" et "âne" sont quand même très fréquents, c'est pas mal d'info redondante qui se retrouve en mémoire (les std::string ne sont pas très efficaces).
Je dois envisager de changer la structure comme ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
struct AnimalNom
{
	char const *s_animal, *s_nom;
	friend bool operator<(AnimalNom const & rl, AnimalNom const & rr)
	{
		if (strcmp(rl.s_animal, rr.s_animal)==0)
			return strcmp(rl.s_nom, rr.s_nom)<0;
		return strcmp(rl.s_animal, rr.s_animal)<0;
	}
};

et gérer le contenu des pointeurs par un memory pool qui s'assurera de l'unicité des string.