Sorting for equal_range()
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Sorting for equal_range()

  1. #1
    Join Date
    Nov 2010
    Posts
    146

    Sorting for equal_range()

    Hello all

    I am using 3 vectors each of which is of type struct "ABC". I am trying to find duplicates in each vector using equal_range() method. In order for equal_range() to work, the vectors must be sorted. The criteria for sorting each vector is different, therefore, I can't write a single sort method inside the struct "ABC". Is there any way to write different methods for sorting, one for each vector?

    Many Thanks

  2. #2
    Join Date
    Jan 2009
    Posts
    596

    Re: Sorting for equal_range()

    You don't need to write different sort methods for each vector. Rather, you should use the std::sort() function and pass it an appropriate comparison function for each vector.

    This is explained in detail here: http://www.cplusplus.com/reference/algorithm/sort/

  3. #3
    Join Date
    Nov 2010
    Posts
    146

    Re: Sorting for equal_range()

    Thanks Peter_B
    Could you please modify the program below for me.
    Code:
    // sort algorithm example
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    struct mystruct {
    string a;
    string b;
    string c;
    string d;
    string e;
    };
    
    Sort function-1 (does it not have to have some relevance to struct mystruct?)
    {
        On basis of variables a, b and c
    }
    
    Sort function-2 (does it not have to have some relevance to struct mystruct?)
    {
        On basis of variables a, d and e
    }
    
    Sort function-3 (does it not have to have some relevance to struct mystruct?)
    {
        On basis of variables b, c and d
    }
    
    int main () {
      
      vector< mystruct > myvector1;
      vector< mystruct >::iterator it1;
    
      sort (myvector1.begin(), myvector1.end(),Sort function-1);
    
      vector< mystruct > myvector2;
      vector< mystruct >::iterator it2;
    
      sort (myvector2.begin(), myvector2.end(),Sort function-2);
    
      vector< mystruct > myvector3;
      vector< mystruct >::iterator it3;
    
      sort (myvector3.begin(), myvector3.end(),Sort function-3);
    
      return 0;
    }

  4. #4
    Join Date
    Apr 1999
    Posts
    27,433

    Re: Sorting for equal_range()

    Quote Originally Posted by gulHK View Post
    Thanks Peter_B
    Could you please modify the program below for me.
    Try a simple example first so that you are familiar with how to use the functions. That is what any programmer who is not familiar with a function or other aspect of C++ would do:
    Code:
    #include <algorithm>
    #include <vector>
    #include <string>
    
    struct foo
    {
       std::string s1;
       std::string s2;
    };
    
    bool SortByS1(const foo& f1, const foo& f2)
    {
        return f1.s1 < f2.s1;
    }
    
    bool SortByS2(const foo& f1, const foo& f2)
    {
        return f1.s2 < f2.s2;
    }
    
    int main()
    {
       std::vector<foo> fooVect;
       //...
       std::sort(fooVect.begin(), fooVect.end(), SortByS1);
       std::sort(fooVect.begin(), fooVect.end(), SortByS2);
    }
    The sort() that takes 3 arguments -- in the sorting function you are passed references to two items, each item is of the type that you're sorting. In the example above, the type being sorted are foo objects. In the sorting function, you return true if item 1 comes before item 2, false otherwise.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 15th, 2012 at 11:08 AM.

  5. #5
    Join Date
    Nov 2010
    Posts
    146

    Re: Sorting for equal_range()

    Thanks Paul McKenzie for your example problem, that was really helpful

    Can I now combine the two sort functions?

    Code:
    bool Sort(const foo& f1, const foo& f2)
    {
        if f1.s1 < f2.s1;
             return true;
        else
             return false;
    
        if f1.s2 < f2.s2;
             return true;
        else
             return false;
    }

  6. #6
    Join Date
    Apr 1999
    Posts
    27,433

    Re: Sorting for equal_range()

    Quote Originally Posted by gulHK View Post
    Thanks Paul McKenzie for your example problem, that was really helpful

    Can I now combine the two sort functions?
    How are you going to do that?

    1) You return before the second test is done.

    2) The sort function must have a strict-weak ordering. In other words, when given three items, a, b and c, the sorting criteria must be consistent and make sense. If a < b and b < c, then a < c must be true.

    If for some reason, if your sorting criteria says that a > c after determining that a < b and b < c, then you have a problem -- your sort is not a sort, but a scrambled mess. The sort may go into an infinite loop and/or erratic behaviour will occur.

    Regards,

    Paul McKenzie

  7. #7
    Join Date
    Nov 2010
    Posts
    146

    Re: Sorting for equal_range()

    OK Paul thanks for clearing things out . But can there be a way to write a single sort function, or is it must to write one for each? because if the number of variables in struct increases then the number of sort functions will also increase, is there any way to avoid it?

    Thanks

  8. #8
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,315

    Re: Sorting for equal_range()

    You could write something like this:
    Code:
    bool compareFoo(const Foo& f1, const Foo& f2)
    {
        if (f1.s1 < f2.s1)
        {
            return true;
        }
        else if (f2.s1 < f1.s1)
        {
            return false;
        }
        else
        {
            return f1.s2 < f2.s2;
        }
    }
    or more compactly:
    Code:
    bool compareFoo(const Foo& f1, const Foo& f2)
    {
        return f1.s1 < f2.s1 || !(f2.s1 < f1.s1) && f1.s2 < f2.s2;
    }
    Nonetheless, if you add a member variable to the struct, then this comparison function must change accordingly to cater to that.

    Note that this is a comparison function that is used in the sorting. It is not a sort function by itself. Also, if this is comparison is canonical, then you could just overload operator< for Foo.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  9. #9
    Join Date
    Nov 2010
    Posts
    146

    Re: Sorting for equal_range()

    Thanks LaserLight, please have a look at the code and please let me know if I can write this "bool operator<(const MyPred& p) const" overloaded method out side of struct, actually that's what I need, the overloaded operator consists of variables that should have the same values in order for any two elements of the vector to be considered equal and is it possible to write more than one comparison method with different comparison criteria? This struct with overloaded method works fine with equal_range() and it does find duplicate elements in the vector

    Code:
    struct MyPred
    {
    	std::string x;
    	std::string y;
    
    	MyPred(const std::string& x, const std::string& y): x(x), y(y) {}
    
    	bool operator==(const MyPred& p) const
    	{
    		return x == p.x && y == p.y;
    	}
            
            // variables with same values are compared here OR found out here
    	bool operator<(const MyPred& p) const
    	{
    		if(x < p.x) return true;
    		if(x > p.x) return false;
    		if(y < p.y) return true;
    		if(y > p.y) return false;
    		return false;
    	}
    };

  10. #10
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,891

    Re: Sorting for equal_range()

    Quote Originally Posted by gulHK View Post
    can write this "bool operator<(const MyPred& p) const" overloaded method out side of struct
    Yes, operators can be defined either as members or non-members. In many cases it makes no difference.

    actually that's what I need, the overloaded operator consists of variables that should have the same values in order for any two elements of the vector to be considered equal
    Take care----there are two different but related concepts at work: equality, and equivalence.

    To have equality, you will need an operator== or equivalent function.
    To have equivalence, you only need that (A < B) is false, and (B < A) is also false. Note that here < can be replaced by any function defining a strict weak ordering.

    Both equal_range() and sort() only care about equivalence.

    is it possible to write more than one comparison method with different comparison criteria?
    Certainly, that's exactly what was done just up-thread. However, you can have only one operator< for a type, so any alternative comparison criteria will need to be defined as named functions or functors, or lambdas. For readability, it's generally best not to have an operator< at all when there are going to be multiple types of comparison done, so there is no confusion about which sorting order is being used at any given time.

    The only thing you have to do is make sure that the same comparator (comparison function/functor/lambda) is passed to both sort() and equal_range(). (Or one which at least imposes the same order.)
    Last edited by Lindley; January 19th, 2012 at 03:53 PM.

  11. #11
    Join Date
    Apr 1999
    Posts
    27,433

    Re: Sorting for equal_range()

    Quote Originally Posted by gulHK View Post
    and is it possible to write more than one comparison method with different comparison criteria?
    A struct can basically do anything you want it to do. All you would need is to pass which criteria you want to use when you construct it.
    Code:
    struct MyPred
    {
        std::string x;
        std::string y;
        int sorting_criteria;
    
        MyPred(const std::string& x, const std::string& y,
                                 int crit = 0): x(x), y(y), sorting_criteria(crit) {}
    
        bool operator()(const MyPred& p1, MyPred& p2) const
        {
               switch( sorting_criteria ) 
               { 
                       case 0:
                               return SortThisWay(p1, p2);
                       case1:
                               return SortThatWay( p1, p2);
                       case 2:
                               return SortAThirdWay( p1, p2);
                }
                return false;
            }
    //...
    };
    That is just a rough outline.

    Regards,

    Paul McKenzie

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center