
January 15th, 2012, 08:47 AM
#1
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

January 15th, 2012, 10:29 AM
#2
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/

January 15th, 2012, 10:40 AM
#3
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 function1 (does it not have to have some relevance to struct mystruct?)
{
On basis of variables a, b and c
}
Sort function2 (does it not have to have some relevance to struct mystruct?)
{
On basis of variables a, d and e
}
Sort function3 (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 function1);
vector< mystruct > myvector2;
vector< mystruct >::iterator it2;
sort (myvector2.begin(), myvector2.end(),Sort function2);
vector< mystruct > myvector3;
vector< mystruct >::iterator it3;
sort (myvector3.begin(), myvector3.end(),Sort function3);
return 0;
}

January 15th, 2012, 12:04 PM
#4
Re: Sorting for equal_range()
Originally Posted by gulHK
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 12:08 PM.

January 15th, 2012, 12:19 PM
#5
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;
}

January 15th, 2012, 05:36 PM
#6
Re: Sorting for equal_range()
Originally Posted by gulHK
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 strictweak 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

January 16th, 2012, 02:19 AM
#7
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

January 16th, 2012, 02:44 AM
#8
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.

January 19th, 2012, 04:12 PM
#9
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;
}
};

January 19th, 2012, 04:21 PM
#10
Re: Sorting for equal_range()
Originally Posted by gulHK
can write this "bool operator<(const MyPred& p) const" overloaded method out side of struct
Yes, operators can be defined either as members or nonmembers. 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 carethere 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 upthread. 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 04:53 PM.

January 19th, 2012, 04:37 PM
#11
Re: Sorting for equal_range()
Originally Posted by gulHK
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

Forum Rules

Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.
Featured
