prédicat pour min_element d'une std::map

Version imprimable

Bonjour, comme déjà décrit dans l'autre topic, j'ai un problème pour avoir le min_element d'une map selon un foncteur/prédicat personnalisé.
Mon premier problème étant les paramètres de l'opérateur() du foncteur.

Voici un code exemplaire:

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
59
60
61
62
63
64
65
66
67
68
69
 
class Foo
{
public:
	std::string at_attr;
	std::string elem;
	int num;
 
	Foo() :
		at_attr(""),
		elem(""),
		num(0)
	{
	}
 
	Foo(std::string at, std::string e, int i) :
		at_attr(at),
		elem(e),
		num(i)
	{
	}
 
	Foo(Foo& f) :
		at_attr(f.at_attr),
		elem(f.elem),
		num(f.num)
	{
	}
 
	Foo& operator=(Foo& f)
	{
		this->at_attr = f.at_attr;
		this->elem = f.elem;
		this->num = f.num;
		return *this;
	}
};
 
typedef boost::shared_ptr<Foo> FooPtr;
 
typedef std::map<std::string, FooPtr> MsFoo;
 
struct Foo_smaller
{
	bool operator()(const FooPtr& a, const FooPtr& b)
	{
		return a->num < b->num;
	}
};
 
int main(int argc, char** argv)
{
	MsFoo foomap;
	FooPtr p1(new Foo("agv", "bla", 5));
	FooPtr p2(new Foo("ffgfg", "fdfd", 98));
	FooPtr p3(new Foo("poer", "dhh", 457));
	foomap["agv"] = p1;
	foomap["fhvbd"] = p2;
	foomap["puer"] = p3;
 
	MsFoo::iterator it3 = std::min_element(foomap.begin(), foomap.end(), Foo_smaller());
	std::cout << "min_element of foomap: " << it3->first << " => " 
		<< "at_attr_ " << it3->second->at_attr 
		<< "elem_ " << it3->second->elem
		<< "num_ " <<it3->second->num
		<< std::endl;
 
	return 0;
}

l'erreur de compilation obtenue est la suivante:

Code:

1
2
3
4
5
6
 
error C2664: 'bool Foo_smaller::operator ()(const FooPtr &,const FooPtr &)': Conversion of parameter 1 from 'std::pair<_Ty1,_Ty2>' into 'const FooPtr &' impossible with
[
            _Ty1=const std::string,
            _Ty2=FooPtr
]

Si quelqu'un à un soupcon d'idée, je suis preneur.

Code:

1 2 3 4 5 6 7 struct Foo_smaller { bool operator()(const MsFoo& a, const MsFoo& b) { return a.second->num < b.second->num; } };
C'est pas unordered_map plutôt que map dont tu aurais besoin ?

unordered_map n'est pas un type de la STL, à ce que je sache (et à ce que je viens de vérifier), c'est un template de boost?
Du moment que j'arrive à accéder mes éléments via operator[](key_type), ca me va.

EDIT:
le prédicat suivant fonctionne pour le vecteur défini ci-dessous.
Code:

1 2 3 4 5 6 7 8 struct Foo_smaller { bool operator()(const FooPtr& a, const FooPtr& b) { return a->num < b->num; } };
Code:

1 2 typedef std::vector<FooPtr> VFoo; VFoo foovec;
en l'appelant de la facon suivante.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 foovec.push_back(p1); foovec.push_back(p2); foovec.push_back(p3); foovec.push_back(p4); foovec.push_back(p5); VFoo::iterator it5 = std::min_element(foovec.begin(), foovec.end(), Foo_smaller()); std::cout << "min_element of foovec: " << " at_attr_ " << (*it5)->at_attr << " elem_ " << (*it5)->elem << " num_ " << (*it5)->num << std::endl; VFoo::iterator it6 = std::max_element(foovec.begin(), foovec.end(), Foo_smaller()); std::cout << "min_element of foovec: " << " at_attr_ " << (*it6)->at_attr << " elem_ " << (*it6)->elem << " num_ " << (*it6)->num << std::endl;
ma question est donc, quels sont les paramètres d'un prédicat de comparaison dans le cas d'une std::map ?

Code:

1
2
3
4
5
6
7
8
struct Foo_smaller
{
    typedef tamap::value_type T;
    bool operator()(T const& lhs, T const& rhs) const
    {
        return lhs.second->num < rhs.second->num;
    }
};

11/09/2006, 01h53
loufoque

Ah oui je me suis trompé dans mon code.
Ce n'est pas MsFoo qu'il faut mais std::pair<std::string, FooPtr>

Citation:

unordered_map n'est pas un type de la STL, à ce que je sache (et à ce que je viens de vérifier), c'est un template de boost?

C'est dans TR1.
11/09/2006, 16h43
Kurisu

Luc> merci, c'était ca. Ca fonctionne à merveille maintenant. Grand merci.

Je suppose qu'un prédicat pour search() fonctionne de manière similaire pour les type d'arguments (en supposant que l'operation soit == et non <).

Subsiste la question de l'efficacité de tel ou tel conteneur pour une telle recherche.
11/09/2006, 19h27
loufoque

Citation:

Subsiste la question de l'efficacité de tel ou tel conteneur pour une telle recherche.

Ben c'est en O(n).
Si tu veux que ce soit en O(log(n)) il faut que ton conteneur soit correctement ordonné.