Discussion :

[taron]

Bonjour, je me pose une question sur binary_search, en effet elle ne liste pas tous les elements de mon vector afin de les comparer, jugez par ce code :

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
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
 
class CFriend
{
  public:
 
  int _x;
 
  bool operator<(const CFriend& c) const
  {
	  cout << "Value :  " << _x << " | " << c._x << endl;
	return false;
  }
};
 
bool compare(const CFriend &ref1, const CFriend &ref2)
{
	cout << "Value : " << ref1._x << " | " << ref2._x << endl;
	return false;
}
 
int main()
{
        CFriend *c1 = new CFriend();
	CFriend *c2 = new CFriend();
	CFriend *c3 = new CFriend();
 
        c1->_x = 69;
	c2->_x = 13;
	c3->_x = 45;
 
	CFriend *search = new CFriend();
	search->_x = 69;
 
       vector<CFriend> vc;
	vc.push_back(*c1);
	vc.push_back(*c2);
	vc.push_back(*c3);
 
	if(binary_search(vc.begin(), vc.end(), *search)) cout << "Found !\n";
	// 	if(binary_search(vc.begin(), vc.end(), *search, compare)) cout << "Found !\n";
	else cout << "Not found !\n";
 
	return 0;
}

Qui me retourne :

Value : 13 | 69
Value : 69 | 69
Value : 69 | 69

Donc il manque un objet dans la liste, celui avec _x == 45...
Pourquoi ?

Une autre question : pourquoi devoir redéfinir operator< et pas operator== ?

Merci pour vos réponses.

[Laurent Gomila]

binary_search effectue une recherche dichotomique, donc cela suppose que ton vecteur est trié... C'est pour cela que tous les éléments ne sont pas inspectés.

De plus, renvoyer systèmatiquement false ne va pas l'aider à avoir un comportement normal

Une autre question : pourquoi devoir redéfinir operator< et pas operator== ?

Parce que l'algorithme effectue des tests d'équivalence, pas d'égalité. Et à partir de < on peut déduire les 5 autres opérateurs de comparaison.

[taron]

OK merci, mais dans operator< je peut faire une comparaison d'égalité == ou faut-il faire autre chose ? Du genre :

Code :

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

1
2
3
4
bool operator<()
{
   if(_x == c._x) return false;
}

Dernière question : pour trier le vecteur (avec sort() ), je peux utiliser un foncteur ou une fonction, mais comment comparer exactement (quelles valeurs retourner) ?

Merci beaucouP.

[Luc Hermitte]

??? Comment penses-tu ordonner avec une relation d'égalité ?

Mais que cherches-tu à faire ? Tu as lu la FAQ ?

[taron]

Excusez-moi, je me suis mal expliqué...
Mais ca va, problème réglé . Merci

Parce que l'algorithme effectue des tests d'équivalence, pas d'égalité. Et à partir de < on peut déduire les 5 autres opérateurs de comparaison.

Justement, si je définis operator< pour les objets de ma classe, le compilo devrait automatiquement déduire des operator> et les autres qui suivent, nan ?

[Laurent Gomila]

Justement, si je définis operator< pour les objets de ma classe, le compilo devrait automatiquement déduire des operator> et les autres qui suivent, nan ?

C'est ce que j'ai dit non ? Enfin ce n'est pas le compilo qui les déduit, mais le programmeur s'il le souhaite. Mais de toute façon je ne suis pas certain que les algorithmes de tri ou de recherche de la STL aient besoin d'autre chose que de <.

[taron]

Ok, mais il se pourrait que dans une classe j'ai besoin de 2 operator< nan ?
Par exemple si j'en place un pour effectuer les recherches avec binary_search et un autre pour pouvoir utiliser less<CFriend>, je fais comment ?

[Laurent Gomila]

C'est pour cela qu'on a inventé les foncteurs.

[taron]

Bon ok...
Dernière petite question, et apres j'arrete de vous harceler, promis ! :p

Auriez-vous un lien qui développe un peu sur les différents types d'itérateur ; unidirectionnel, bidirectionnel, ramdom access etc... parce que j'ai pas bien saisi.

Merci.

[Laurent Gomila]

http://www.sgi.com/tech/stl/Iterators.html