Thread: std::sort and third argument

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    std::sort and third argument

    I have to use st::sort. In the cmp function I have, I want to have a variable that I have computed preveiously, but will be for all the cmp calls the same. Now, because I was eager to see my result, I placed the variable (P0) as global... :/ ( heartbreaking ). Is there any way to do it a more elegant way?

    And the relative code
    Code:
    Point_2 P0; //global
    ...
    std::cout<<"SORT<----------------"<<std::endl;
    std::sort(P.begin(), P.end(), cmp);
    std::copy(P.begin(), P.end(), out);
    
    ...
    
    // Definition of the function
    bool cmp(const Point_2 &a, const Point_2 &b)
    {
            double aRad = findRad(a, P0);
            double bRad = findRad(b, P0);
    
            if(aRad < bRad)
                    return true;
            if(aRad == bRad)
            {
                    if(a.y() > b.y())
                            return true;
                    else if(a.y() == b.y() && a.x() > b.x())
                            return true;
                    else
                            return false;
            }
            return false;
    }
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    What is P0?
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Is a point in R˛ . I have typedef'ed it.
    Code:
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef K::Point_2      Point_2;
    But then I have to read from the stream and decide which one of the points from this stream is really P0. I mean that I am finding that out at runtime. It is not a constant.
    Here is the code
    Code:
    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
    #include <CGAL/convex_hull_2.h>
    #include <stack>
    #include <CGAL/Polygon_2.h>
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef K::Point_2      Point_2;
    typedef CGAL::Polygon_2<K> Polygon;
    
    Point_2 P0;
    
    bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point);
    bool cmp(const Point_2 &a, const Point_2 &b);
    double findRad(const Point_2 &P, const Point_2 &P0);
    
    int main()
    {
      CGAL::set_ascii_mode(std::cin);
      CGAL::set_ascii_mode(std::cout);
      std::istream_iterator< Point_2 >  in_start( std::cin );
      std::istream_iterator< Point_2 >  in_end;
      std::ostream_iterator< Point_2 >  out( std::cout, "\n" );
    
      std::vector< Point_2 >  P (in_start, in_end);
    
      std::vector< Point_2 >  Q;
    
            P0 = P[1];
            int posP0 = 1;
            // Srart from zero, in case 1st and 2nd points
            // have same y coordinates
            for(int i = 0 ; i < P.size() ; i++)
            {
                    if( duplicatePoint(P, i, P[i]) )
                            P.erase (P.begin()+i);
                    if( P[i].y() < P0.y() )
                    {
                            P0 = P[i];
                            posP0 = i;
                    }
                    if( P[i].y() == P0.y() )
                            if( P[i].x() < P0.x() )
                            {
                                    P0 = P[i];
                                    posP0 = i;
                            }
            }
    ....
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by std10093 View Post
    Is there any way to do it a more elegant way?
    Well the third argument of std::sort is almost always a functor. A functor is a class that defines operator(), and in this case it would be your comparison. P0 can be declared as a member of the functor class and updated accordingly in operator().

    Of course the key word here is functor so you might want to google it.

  5. #5
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    But I do not want the P0 to be updated

    When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by std10093
    When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?
    That is perfectly fine: just initialise it in the constructor.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by std10093 View Post
    But I do not want the P0 to be updated

    When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?
    Then, um, don't update it. I'm under the wrong impression perhaps. If you need P0 for the comparison and nothing else, that is another reason to include it as a data member in the functor I think.

  8. #8
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Hmm sorry for not getting what you want to say, but I want to be 100% I understood correct.
    laserlight I do not have a constructor
    Whiteflags, it is not clear to me if I need to use what you say or not

    Maybe I should post all the code, so that you get the whole image
    Code:
    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
    #include <CGAL/convex_hull_2.h>
    #include <stack>
    #include <CGAL/Polygon_2.h>
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef K::Point_2      Point_2;
    typedef CGAL::Polygon_2<K> Polygon;
    
    Point_2 P0;
    
    bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point);
    bool cmp(const Point_2 &a, const Point_2 &b);
    double findRad(const Point_2 &P, const Point_2 &P0);
    
    int main()
    {
      CGAL::set_ascii_mode(std::cin);
      CGAL::set_ascii_mode(std::cout);
      std::istream_iterator< Point_2 >  in_start( std::cin );
      std::istream_iterator< Point_2 >  in_end;
      std::ostream_iterator< Point_2 >  out( std::cout, "\n" );
    
      std::vector< Point_2 >  P (in_start, in_end);
    
      std::vector< Point_2 >  Q;
    
            P0 = P[1];
            int posP0 = 1;
            // Srart from zero, in case 1st and 2nd points
            // have same y coordinates
            for(int i = 0 ; i < P.size() ; i++)
            {
                    if( duplicatePoint(P, i, P[i]) )
                            P.erase (P.begin()+i);
                    if( P[i].y() < P0.y() )
                    {
                            P0 = P[i];
                            posP0 = i;
                    }
                    if( P[i].y() == P0.y() )
                            if( P[i].x() < P0.x() )
                            {
                                    P0 = P[i];
                                    posP0 = i;
                            }
            }
    
            std::cout<<" MIN = " <<P0<<std::endl;
    
            P.erase(P.begin() + posP0);
    
            std::cout<<"input<----------------"<<std::endl;
            std::copy(P.begin(), P.end(), out);
    
            std::cout<<"SORT<----------------"<<std::endl;
            std::sort(P.begin(), P.end(), cmp);
            std::copy(P.begin(), P.end(), out);
    
            /* compute convex hull in Q from input P */
            Q = P;
    
    //TEST  CGAL::convex_hull_2(Q.begin(), Q.end(), out ) ;
    
            std::stack<Point_2> S;
            S.push(P0);
            S.push(P.at(1));
            S.push(P.at(2));
    
            Point_2 TOP;
            Point_2 NEXTtoTOP;
            for( int i = 3 ; i < P.size() ; i++ )
            {
                    std::cout<<"Loop "<<i<<std::endl;
                    TOP = P.top();
                    P.pop();
                    NEXTtoTOP = P.top();
                    P.push(TOP);
    
    
            }
    
            std::cout<<"result<----------------"<<std::endl;
            std::copy(Q.begin(), Q.end(), out);
    
            return 0;
    }
    
    bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point)
    {
            for(int i = 0 ; i < pointPos ; i++)
                    if(P[i] == point)
                            return true;
            return false;
    }
    
    bool cmp(const Point_2 &a, const Point_2 &b)
    {
            double aRad = findRad(a, P0);
            double bRad = findRad(b, P0);
    
            if(aRad < bRad)
                    return true;
            if(aRad == bRad)
            {
                    if(a.y() > b.y())
                            return true;
                    else if(a.y() == b.y() && a.x() > b.x())
                            return true;
                    else
                            return false;
            }
            return false;
    }
    
    double findRad(const Point_2 &P, const Point_2 &P0)
    {
            double dx, dy;
    // Here is where I need P0 <-------------------------------------------------
            dx = P.x() - P0.x();
            dy = P.y() - P0.y();
    
    if( dx == 0 && dy ==0 )
            {
                    std::cout<< " In function findRad, atan result is UNDEFINED! Return 0! "$
                    return 0.0;
            }
    
            return( atan2(dx, dy) * (-1.00) );
    }
    There is an error when I call the stack, but I have fixed it in my latest version. Ignore the stack part
    Last edited by std10093; 12-21-2012 at 10:12 AM.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by std10093
    I do not have a constructor
    That's because you currently are using a function for the comparator; functions do not have constructors.

    The idea here is to use a function object (functor), e.g.,
    Code:
    class Point_2_Compare
    {
    public:
        explicit Point_2_Compare(const Point_2 &P0_) : P0(P0_) {}
    
        bool operator()(const Point_2 &a, const Point_2 &b) const
        {
            double aRad = findRad(a, P0);
            double bRad = findRad(b, P0);
    
            if(aRad < bRad)
                return true;
            if(aRad == bRad)
            {
                if(a.y() > b.y())
                    return true;
                else if(a.y() == b.y() && a.x() > b.x())
                    return true;
                else
                    return false;
            }
            return false;
        }
    private:
        Point_2 P0;
    };
    
    // ...
    
    std::sort(P.begin(), P.end(), Point_2_Compare(P0));
    Now P0 can be declared in main.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    WOW ! I didn't even know what that is! Brilliant! Many thanks to everybody!!!
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You could use a lambda, too. It's mostly syntactic sugar (less code), but I'm throwing it in here for educational purposes (making you aware it exists and can be used).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Hmm I have heard about λ .. I am not going to use it, but I will have a google on it Thanks Elysia
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  13. #13
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Lambda functions fit perfectly for sort (provided you are using C++11). So to stress more Elysia's point here is how it would like like (or close to that).

    Code:
    std::sort(P.begin(), P.end(),
           [&](const Point_2 &a, const Point_2 &b)
    {
              double aRad = findRad(a, P0);
              double bRad = findRad(b, P0);
     
              if(aRad < bRad)
                  return true;
              if(aRad == bRad)
              {
                if(a.y() > b.y())
                    return true;
                else if(a.y() == b.y() && a.x() > b.x())
                    return true;
                else
                    return false;
              }
              return false;
    });
    Apart from saving you code and not requiring you to define a one-use class, this makes it more optimal as well. For example, you don't need to copy PO into a temporary object (your functor) you can just access it provided it is within the scope. Of course, lambda usage implies that you won't be calling sort() all over your code, but once.

  14. #14
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    That's a bit much imo. I suppose I should be glad it's not like this in C++, but in python the lambda function has to be one statement long. Aside from that, std10093 wanted P0 to be associated with the comparison. With lambdas I think it has to be global again, which is not so great; with functors, it can just be a data member like everyone said.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I find that comparison function very difficult to reason about is correctness. A nicer way of writing it would be:
    Code:
            double aRad = findRad(a, P0);
            double bRad = findRad(b, P0);
    
            if (aRad < bRad)
                return true;
            if (aRad > bRad)
                return false;
    
            if (a.y() > b.y())
                return true;
            if (a.y() < b.y())
                return false;
    
            return a.x() > b.x());
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Argument inside the Argument of a Function Declaration
    By manasij7479 in forum C++ Programming
    Replies: 3
    Last Post: 06-11-2011, 05:53 AM
  2. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  3. Replies: 1
    Last Post: 01-26-2010, 09:02 AM
  4. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM