Recherche d'élement dans un vector avec std::find_if

Le
philippe.lrx
Bonjour,

Dans le code ci dessous, le second appel à std::find_if me donne le
message d'erreur :
test.cpp: In function ‘int main()’:
test.cpp:36: erreur: no matching function for call to ‘find_if
(__gnu_cxx::__normal_iterator<const Foo*, std::vector<Foo,
std::allocator<Foo> > >, __gnu_cxx::__normal_iterator<Foo*,
std::vector<Foo, std::allocator<Foo> > >, Functor)’

Je ne comprends absolument pas le sens de l'erreur, qui peut
m'expliquer ?

Le code :
#include <iostream>
#include <vector>
#include <algorithm>

struct Foo
{
Foo( std::string n )
: n_( n )
{}

std::string n_;
};

typedef std::vector<Foo> FooVector;

struct Functor
{
bool operator()( Foo const& f ) const
{
return f.n_ == "toto";
}
};

int main()
{
FooVector fv;
fv.push_back( Foo( "tutu" ) );
fv.push_back( Foo( "toto" ) );
fv.push_back( Foo( "tata" ) );
fv.push_back( Foo( "toto" ) );
FooVector::const_iterator itFind =
std::find_if( fv.begin(), fv.end(), Functor() );
while ( itFind != fv.end() )
{
std::cout << "trouvé";
itFind = std::find_if( itFind + 1, fv.end(), Functor() );
}

return 0;
}

Merci.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Fabien LE LEZ
Le #18972201
On Tue, 24 Mar 2009 12:06:15 -0700 (PDT), :

itFind = std::find_if( itFind + 1, fv.end(), Functor() );



Ton "+1" transforme apparemment le "std::vector<Foo>::const_iterator"
en "Foo const*".

Écris plutôt :

++itFind;
itFind = std::find_if( itFind, fv.end(), Functor() );

Par ailleurs, tu remarqueras que ton code est plus compliqué que si tu
avais écrit la boucle toi-même.

Malheureusement, ça arrive souvent avec les algorithmes de la STL,
surtout les plus simples :-(

Ici, il te faudrait un "for_each_if" qui pourrait ressembler à :

template <class InputIterator, class Predicate, class Function>
Function for_each_if (InputIterator first, InputIterator last,
Predicate p, Function f)
{
while ( first!=last )
{
if (p (*first))
{
f (*first);
}
++first;
}
return f;
}

Ou bien, appeler for_each(), et laisser la fonction passée en
paramètre, vérifier que son argument convient.
philippe.lrx
Le #18972391
On 24 mar, 20:25, Fabien LE LEZ
On Tue, 24 Mar 2009 12:06:15 -0700 (PDT), :



Ton "+1" transforme apparemment le "std::vector<Foo>::const_iterator"
en "Foo const*".

Écris plutôt :

++itFind;
itFind = std::find_if( itFind, fv.end(), Functor() );



J'ai exactement le même message d'erreur au numéro de ligne près :(

Par ailleurs, tu remarqueras que ton code est plus compliqué que si tu
avais écrit la boucle toi-même.

Malheureusement, ça arrive souvent avec les algorithmes de la STL,
surtout les plus simples :-(


Oui, maintenant que tu le dis :)
Mais je suis quand même intrigués sur la raison de l'erreur.


Ici, il te faudrait un "for_each_if" qui pourrait ressembler à :
[...]


Ton idée me semble intéressante je vais creuser...
Fabien LE LEZ
Le #18972381
On Tue, 24 Mar 2009 12:06:15 -0700 (PDT), :

Dans le code ci dessous, le second appel à std::find_if me donne le
message d'erreur :



J'ai compilé ton code avec VC++, et ai pu obtenir un message d'erreur
à peu près compréhensible. G++ a beaucoup d'efforts à faire sur ce
point.

int main()
{
FooVector fv;



Ceci est un std::vector<Foo>...

itFind = std::find_if( itFind + 1, fv.end(), Functor() );



...donc fv.end() est un std::vector<Foo>::iterator.
Comme itFind est un std::vector<Foo>::const_iterator, le compilo
n'arrive pas à savoir à quoi correspond le premier paramètre template
de std::find_if.
Fabien LE LEZ
Le #18972371
>...donc fv.end() est un std::vector<Foo>::iterator.



Un peu plus d'explications avec un exemple :

struct C
{
int f() const;
int g() const;
std::string f();
};

C c;
C const cc;

cc est un "C const" donc "cc.f()" correspond à "int f() const;"
c est un "C" (non-const) donc "c.f()" correspond à "std::string f();"

c.g() est un problème : il n'y a aucune fonction non-const, membre de
C, appelée "g". Mais comme il existe une fonction "g" const, le
compilateur convertit "c" en un "C const", et peut ainsi appeler
C::g().

Il y a plusieurs cas où le compilateur peut convertir un type en un
autre, silencieusement.
Malheureusement, l'association d'un type à un paramètre template n'en
fait pas partie.

int Max1 (int a, int b);
template <class T> T Max2 (T a, T b);

int main()
{
int i= 42;
unsigned int u= 420;
Max1 (i, u); // OK, u est converti en un "int"
Max2 (i, u); // Erreur : "a" et "b" sont de types différents, donc
le compilo ne sait pas à quoi "T" correspond.
Max2<int> (i, u); // OK : le compilo n'a pas à se demander à quoi
"T" correspond, puisqu'on le lui indique. "Max2<int>" est identique à
"Max1".
}
Falk Tannhäuser
Le #18973361
Fabien LE LEZ schrieb:
On Tue, 24 Mar 2009 12:06:15 -0700 (PDT), :
int main()
{
FooVector fv;



Ceci est un std::vector<Foo>...

itFind = std::find_if( itFind + 1, fv.end(), Functor() );



...donc fv.end() est un std::vector<Foo>::iterator.
Comme itFind est un std::vector<Foo>::const_iterator, le compilo
n'arrive pas à savoir à quoi correspond le premier paramètre template
de std::find_if.



C'est pareil comme pour std::max(666, 42L) - le compilateur n'arrive pas à déduire le type correcte de la fonction à instantier. Par contre,
l'instantiation explicite compile :
result = std::max<long>(666, 42L);
itFind = std::find_if<FooVector::const_iterator>(itFind + 1, fv.end(), Functor()); // Déduction automatique du type "Functor"

Une autre solution, peut-être moins moche, consiste à créer un alias qualifié "const" du vecteur :
FooVector const& cfv = fv;
...
itFind = std::find_if(itFind + 1, cfv.end(), Functor());


Finalement, dans C++0x (eh oui, encore un peu de patience) on pourra écrire
itFind = std::find_if(itFind + 1, fv.cend(), Functor());
la fonction cend() renvoyant un const_iterator même pour un vecteur non const.
GCC 4.3.2 accepte déjà cette dernière variante si on spécifie -std=c++0x sur la ligne de commande.

Falk
Marc
Le #18973821
Falk Tannhäuser wrote:

C'est pareil comme pour std::max(666, 42L) - le compilateur n'arrive
pas à déduire le type correcte de la fonction à instantier.



Il y a eu des propositions pour faire en sorte que min et max soient
capables de gérer ça intelligemment, mais elles ont été rejetées.

Une autre solution, peut-être moins moche, consiste à créer un alias qualifié "const" du vecteur :
FooVector const& cfv = fv;
...
itFind = std::find_if(itFind + 1, cfv.end(), Functor());


Finalement, dans C++0x (eh oui, encore un peu de patience) on pourra écrire
itFind = std::find_if(itFind + 1, fv.cend(), Functor());
la fonction cend() renvoyant un const_iterator même pour un vecteur non const.
GCC 4.3.2 accepte déjà cette dernière variante si on spécifie -std=c++0x sur la ligne de commande.



Dans cette optique, on peut aussi utiliser cref(fv).end(), où cref sera
standard mais peut déjà être implémenté sans modifier la bibliothèque
standard. Mais la version précédente avec "cfv" est sans doute la
meilleure.

C'est dommage, il ne semble pas nécessaire d'être aussi strict dans la
déclaration de find_if, on n'a pas besoin que les 2 premiers arguments
soient du même type, juste qu'ils soient comparables par == ou !=.
Fabien LE LEZ
Le #18973811
On Tue, 24 Mar 2009 23:49:17 +0000 (UTC), Marc

Il y a eu des propositions pour faire en sorte que min et max soient
capables de gérer ça intelligemment, mais elles ont été rejetées.



Dans les cas où je travaille sur des entiers (signés ou non-signés),
j'écris tout simplement :

int Max (int a, int b)
{
return (a<b) ? b : a;
}

et le tour est joué.

On ne va pas se laisser faire par un compilateur, non plus !..
James Kanze
Le #18974711
On Mar 25, 1:00 am, Fabien LE LEZ
On Tue, 24 Mar 2009 23:49:17 +0000 (UTC), Marc



>Il y a eu des propositions pour faire en sorte que min et max
>soient capables de gérer ça intelligemment, mais elles ont
>été rejetées.



Dans les cas où je travaille sur des entiers (signés ou
non-signés), j'écris tout simplement :



int Max (int a, int b)
{
return (a<b) ? b : a;
}



et le tour est joué.



On ne va pas se laisser faire par un compilateur, non plus !..



Sauf que ta fonction risque de donner un mauvais résultat si tu
l'appelles avec des long.

Le problème de base, je crois, c'est qu'il n'y a pas de façon
« intelligente » quand les types sont melangés. Si les deux
types sont entiers, et tous les deux signés ou tous les deux
non-signés, on prend le plus grand ; jusqu'à là, pas de
probème. Mais si un des types est flottant, et l'autre entier,
ou un signé et l'autre non-signé, ce n'est pas du tout clair ce
qu'il faut faire. Même pour une personne, sans parler du
compilateur.

--
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
philippe.lrx
Le #18975781
On 24 mar, 20:47, Fabien LE LEZ
>...donc fv.end() est un std::vector<Foo>::iterator.

Un peu plus d'explications avec un exemple :

[...]


Ok, merci pour les explications et l'exemple, je pense avoir compris
le problème.
espie
Le #18976291
In article James Kanze
Le problème de base, je crois, c'est qu'il n'y a pas de façon
« intelligente » quand les types sont melangés. Si les deux
types sont entiers, et tous les deux signés ou tous les deux
non-signés, on prend le plus grand ; jusqu'à là, pas de
probème. Mais si un des types est flottant, et l'autre entier,
ou un signé et l'autre non-signé, ce n'est pas du tout clair ce
qu'il faut faire. Même pour une personne, sans parler du
compilateur.



Oui enfin là, l'exemple cité, c'était du int et du long, donc le
type le plus grand va de soit.

Quand C++98 est sorti, les traits étaient quelque chose de relativement
ésoterique. Aujourd'hui, c'est quand même mieux maitrisé, on devrait
pouvoir arriver à faire pondre quelque chose de décent à std::min et
std::max avec des arguments mélangés, tant qu'il y a *indiscutablement*
un type plus grand que l'autre...
Publicité
Poster une réponse
Anonyme