Discussion :

[Kurisu]

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 :

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
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 :

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

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.

[loufoque]

Code :

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

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 ?

[Kurisu]

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 :

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

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 :

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

1
2
typedef std::vector<FooPtr> VFoo;
VFoo foovec;

en l'appelant de la facon suivante.

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
 
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 ?

[Luc Hermitte]

Code :

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

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;
    }
};

[loufoque]

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

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.

[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.

[loufoque]

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é.