find sur un vector qui contient une structure

Version imprimable

26/04/2009, 22h21
kunda

find sur un vector qui contient une structure
Bonsoir,

J'ai déja réussit (en cherchant) à faire un find de la STL sur un vector de string, et maintenant, je voudrais faire une modification dans laquelle le vector contient non pas une seule string, mais une structure de 3 string.
Et la, j'ai beau faire, je n'arrive pas à trouver la syntaxe à appliquer.

Sur mon vector de string, j'avais fait ceci :
Code:

1 2 3 4 if (find(index.begin(), index.end(), nom ) == index.end() ) { /* si pas trouvé */ } else { /* si trouvé */ }
maintenant, mon vector est devenu ceci :
Code:

1 2 3 4 5 6 7 8 struct IndexBloc { string rang; string nom; string valeur; }; std::vector<IndexBloc> index;
et je voudrias faire un find sur le champ nom, et je ne trouve pas la syntaxe.

Voila les syntaxes que j'ai essayé (sans succès hélas) dans mon find.

index::nom.begin()
index.nom.begin()
index->nom.begin()

Si quelqu'un peut m'éclairer, je l'en remercie d'avance, car j'ai beau chercher, je n'arrive pas à dénicher l'info.
26/04/2009, 22h51
hiura

Regarde std::find_if [1].

[1] http://www.dinkumware.com/manuals/?m...h.html#find_if
26/04/2009, 23h52
poukill

Cet article est plus complet ! ;)
27/04/2009, 00h18
kunda

Entre temps, je suis allé regarder la déclaration du template dans le stl_algo.h, mais sans résultat.

Merci à tous deux, mais je ne suis pas tout à fait sur de ce que je dois comprendre, corrigez moi si je me trompe :

>> pour résoudre mon problème, je ne dois pas me servir de find, qui est reservé aux cas simples (tel qu'un vector ou un tableau C d'un type non composé), mais dès qu'il faut préciser sur quel élément le test doit se faire, il faut se servir de find_if pour expliquer à cette brave STL ce qu'on souhaite ?

C'est ca, j'ai bon ? (si oui, alors je risquait de chercher encore longtemps du coté de find :roll:)

Bon je vais essayer d'aller faire fonctionner ca, et si ca marche, je reviens vous le dire (et si ca marche pas, je reviens aussi ;) )
27/04/2009, 00h59
JolyLoic

Disons que find recherche par égalité. Donc, si tu veux trouver une structure, il faut que tu lui passe une structure à laquelle elle doit être égale. find_if lui recherche par prédicat, tu peut donc lui indiquer n'importe quelle condition de recherche, comme par exemple une égalité partielle.

A noter que si tu dois faire beaucoup de recherches par nom, vector+find n'est probablement pas la meilleure structure, car la recherche se fait en temps linéaire. Tu pourrais faire un map<string, IndexBloc> pour une recherche en temps logarithmique.

Il est probable que tu devrais en effet utiliser plutôt un map comme cela t'a été suggéré.
Toutefois j'ai essayé de faire quelque chose avec la structure telle quelle, en utilisant la fonction find_if() prenant en (dernier) argument un 'objet fonctionnel' que j'ai préalablement défini (trouve()):

Code:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
 
struct IndexBloc
{
  string rang;
  string nom;
  string valeur;
};
 
 
// définition d'un objet fonctionnel (function object) qui servira d'argument à find_if
class trouve
{
  string const & s;
  public:
    trouve(string const & ss):s(ss) {}
    bool operator()(IndexBloc const & ib) const { return ib.nom == s; }
};
 
//--------------------------------------------------------------------------
 
int main () 
{ 
  std::vector<IndexBloc> index;
 
  // création de trois structures
  IndexBloc a,b,c;
  // remplissage partiel d'icelles
  a.nom = "Jules";
  a.valeur = "immense";
  b.nom = "Simon";
  c.nom = "Isabelle";
  // remplissage du vecteur
  index.push_back(a);
  index.push_back(b);
  index.push_back(c);
 
  // création d'un itérateur pour le vecteur
  vector<IndexBloc>::const_iterator iter;
 
  //après exécution de la ligne qui suit iter pointe vers la première structure dont
  // le champ nom est "Jules", s'il en existe une
  // sinon iter pointe vers index.end() (la position qui suit le dernier élément du vecteur)
  iter = find_if(index.begin(), index.end(), trouve("Jules"));
 
  // exploitation possible :
  if( iter != index.end())
    cout << "valeur de " <<  (*iter).nom << ": " << (*iter).valeur << endl;
  else
    cout << "Pas de Jules.";
}

Voici deux solutions aboutissant au même résultat. La méthode 1 est issue d'un copier/coller, je n'arrive pas à comprendre ce qu'il y a "derrière".
Donc pas demander, juste accepter que c'est OK :aie:

Code:

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
struct IndexBloc
{
	std::string s_rang;
	std::string s_nom;
	std::string s_valeur;
	bool CestLeMeme(std::string nom) const
	{
		//pour la méthode 1
		return s_nom==nom;
	}
};
 
struct IndexBlocPred
{
	//pour la méthode 2
	std::string s_nom;
	IndexBlocPred(std::string const & nom):s_nom(nom) {}
	bool operator()(IndexBloc const & r) const
	{
		return s_nom==r.s_nom;
	}
};
 
 
{
	//méthode 1
	std::vector<IndexBloc> v;
	std::string nom;
	std::vector<IndexBloc>::iterator it=std::find_if(v.begin(),v.end(),
		std::bind2nd(std::mem_fun_ref(&IndexBloc::CestLeMeme),nom)
		);
}
{
	//méthode 2
	std::vector<IndexBloc> v;
	std::string nom;
	std::vector<IndexBloc>::iterator it=std::find_if(v.begin(),v.end(),IndexBlocPred(nom));
}

28/04/2009, 14h30
ptyxs

@camboui est-ce que ta méthode 2 diffère de la proposition que j'avais faite ?

Non, c'est la même chose à première vue. Sauf que tu passes les paramètres par valeur et moi par référence. On pourrait même pousser plus loin en ayant une référence pour le champ du prédicat, il n'y aurait alors plus aucune copie.
Code:

1 2 3 4 5 6 7 8 9 10 struct IndexBlocPred { //pour la méthode 2 std::string const & s_nom; IndexBlocPred(std::string const & nom):s_nom(nom) {} bool operator()(IndexBloc const & r) const { return s_nom==r.s_nom; } };

28/04/2009, 15h04
ptyxs

En effet. Je vais éditer mon message en ce sens. Ce sera plus correct.

Citation:

Envoyé par camboui

Voici deux solutions aboutissant au même résultat. La méthode 1 est issue d'un copier/coller, je n'arrive pas à comprendre ce qu'il y a "derrière".
Donc pas demander, juste accepter que c'est OK :aie:

Ah, un compagnon de galère. A chaque fois que je veux utiliser ce genre de chose, je me retrouve toujours à batailler pour retrouver la syntaxe exacte, et ça fini souvent en copier/coller :lol:

Il parait que les bind2st, mem_fun et autres étaient encore assez expérimentaux à l'époque de la normalisation en 98, pas encore complètement développé, mais la deadline était là. Apparemment, entre temps, on a découvert comment faire proprement ce genre d'opération, ce qui a donné std::bind dans le nouveau standard.
Et donc en C++0x on pourra faire ça (on peut même le faire dès maintenant avec VS2008 SP1) :
Code:

1 2 std::vector<IndexBloc>::iterator it=std::find_if(v.begin(),v.end(), std::tr1::bind(&IndexBloc::CestLeMeme, std::tr1::placeholders::_1, nom));
Ben je comprends toujours pas des masses ce qui se passe. :aie:

Par contre, bizarrement, je trouve la syntaxe avec les lambdas beaucoup plus propre et intuitive.
Code:

1 2 std::vector<IndexBloc>::iterator it = std::find_if(v.begin(), v.end(), [&nom](const IndexBloc& r){return r.CestLeMeme(nom)});
Bon ok, à première vue ça a l'air horrible. En fait, quand on a compris le truc, et que l'on connait la correspondance avec le même code en C++98, c'est transparent.

Une lambda n'est qu'une "fonction anonyme"
Code:

1 2 3 4 5 // fonction anonyme ([] remplace le nom de la fonction) [](T1 arg1, T2 arg2...) { // corps de la lambda }
...avec un petit plus. Une lambda peut "capturer le contexte" qui la précède. Par exemple, [&nom], ça veut dire capturer par référence la variable "nom", déclaré un peu plus haut dans le code. Quand une variable est capturée on peut l'utiliser directement dans le corps de la lambda.

Ce qui fait qu'au final, une lambda, c'est juste un bête foncteur sous une forme un peu plus compact et intégré au code. Par exemple ce code :
Code:

1 2 std::vector<IndexBloc>::iterator it = std::find_if(v.begin(), v.end(), [&nom](const IndexBloc& r){return r.CestLeMeme(nom)});
est totalement équivalent à ce code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 struct IndexBlocPred { //pour la méthode 2 std::string const & s_nom; IndexBlocPred(std::string const & nom):s_nom(nom) {} bool operator()(IndexBloc const & r) const { return r.CestLeMeme(s_nom); } }; std::vector<IndexBloc>::iterator it = std::find_if(v.begin(), v.end(), IndexBlocPred(nom));
[&nom] est équivalent au constructeur IndexBlocPred(std::string const & nom):s_nom(nom) {}. C'est grâce à ce constructeur que le foncteur pouvait "capturer le contexte" c'est à dire stocker la variable nom.
(const IndexBloc& r) est équivalent aux paramètres de l'opérateur() du foncteur.
Le corps de la lambda est équivalent au corps de l'opérateur() du foncteur.
Code:

1 2 auto it = std::find_if(v.begin(), v.end(), [&nom](const IndexBloc& r){return r.CestLeMeme(nom)});
Plutôt chouette non ? On pourra écrire ce genre de chose avec VC10, j'ai hâte.

(Par contre, il ne faut pas abuser sur la taille des lambda sinon ça devient vite illisible :aie:)

28/04/2009, 20h03
Goten

A noter que nom est capturer par référence constante par défaut. Il faut indiquer mutable pour que ça ne soit pas le cas non?
28/04/2009, 20h56
Arzar
Citation:

Envoyé par Goten

A noter que nom est capturer par référence constante par défaut.

Ça dépend de la manière dont il est capturé.
[nom] = capture par copie.
[&nom] = capture par const reference.

Ce qui oblige effectivement à apposer cet hideux "mutable" si l'on veut pouvoir modifier la variable capturée. Tout ne peux pas être parfait...

Le pire, si j'ai bien compris le proposal, c'est qu'on peut même faire ça:
Code:

1 2 3 4 5 int var = 0; function<void (void)> f = [var]() mutable { var++; }; f(); // var vaut maintenant un.
var est capturé par copie, et pourtant on peut quand même le modifier à cause de mutable... brisant ainsi des dizaines d'années de convention et le sens commun qui assure pourtant que le passage par copie ne permet en aucun cas d'affecter l'original. :roll:
J'espère me tromper pour ce dernier, car je ne vois pas du tout de justification.
28/04/2009, 21h30
Goten

Je suis pas sur qu'on puisse écrire ce que tu as donné.
Pour le reste : c'est bien ce qu'il me semblait. Et c'est vrai que le mutable me file la nausée ^^. M'enfin m'étonnerait que y'est énormément de cas où ça est du sens.
28/04/2009, 21h35
camboui

Arzar, j'adore te lire. Tes interventions sont exhaustives, et anticipatives !
:hola::hola::hola:
Mamma mia :lahola:
:applo: :ccool: