Why this sample works?

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

When sort_by_polar_angle() is called, is it function as a construnctor? How the overloaded operator () correctly used?

Answer 1

When you call sort_by_polar_angle() in the sort() function, you are creating a temporary object of type sort_by_polar_angle (i.e. its constructor is called). Inside the sort algorithm, the functor object you passed is used something like functor() which will be translated into functor.operator().

Answer 2

It won't work for points on a straight line from the center. The 'angle' of these is equal, so their order isn't determined. Sorting these points will return undetermined results.

That's because any "sort" operation should be 'strict': if a < b, then b > a. (actually the definition is somewhat more complicated.)

dd a0 = { 0, 1 };
dd b0 = { 0, 2 };

assert( sort_by_polar_angle ()( a0, b0 ) && ! sort_by_polar_angle () ( b0, a0 ) );

Answer 3

Try here for a basic introduction to what functors are, or google for c++ functor.