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

1. Member
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. Member +
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. Member
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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## 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 11:08 AM.

5. Member
Join Date
Nov 2010
Posts
146

## Re: Sorting for equal_range()

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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## Re: Sorting for equal_range()

Originally Posted by gulHK

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. Member
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. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,734

## 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.

9. Member
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. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## 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 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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

## 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
•