Pourquoi cet exemple fonctionne?
Question
typedef pair<double, double> dd;
const double epsilon = 1e-6;
struct sort_by_polar_angle {
dd center;
// Constuctor of any type
// Just find and store the center
template<typename T> sort_by_polar_angle(T b, T e) {
int count = 0;
center = dd(0,0);
while(b != e) {
center.first += b->first;
center.second += b->second;
b++;
count++;
}
double k = count ? (1.0/count) : 0;
center.first *= k;
center.second *= k;
}
// Compare two points, return true if the first one is earlier
// than the second one looking by polar angle
// Remember, that when writing comparator, you should
// override not ‘operator <’ but ‘operator ()’
bool operator () (const dd& a, const dd& b) const {
double p1 = atan2(a.second-center.second, a.first-center.first);
double p2 = atan2(b.second-center.second, b.first-center.first);
return p1 + epsilon < p2;
}
};
// ...
vector < dd > points;
sort(all(points), sort_by_polar_angle(all(points)));
Quand sort_by_polar_angle () est appelée, est-il fonction comme construnctor? Comment correctement l'opérateur surchargé (par exemple)?
La solution
Lorsque vous appelez sort_by_polar_angle()
dans la fonction sort()
, vous créez un objet temporaire de type sort_by_polar_angle
(à savoir son constructeur est appelé). A l'intérieur de l'algorithme de tri, l'objet foncteur est utilisé que vous avez passé quelque chose comme functor()
qui sera traduit en functor.operator()
.
Autres conseils
Il ne fonctionnera pas pour les points sur une ligne droite du centre. Le « angle » de ceux-ci est égale, de sorte que leur ordre n'est pas déterminé. Tri ces points renvoie des résultats indéterminés.
En effet, toute opération devrait être 'stricte' de tri ": si a a. (En fait le est un peu plus compliquée.)
dd a0 = { 0, 1 };
dd b0 = { 0, 2 };
assert( sort_by_polar_angle ()( a0, b0 ) && ! sort_by_polar_angle () ( b0, a0 ) );
ici pour une introduction à ce que foncteurs sont, ou google pour c ++ foncteur .