STL stable_sort sorting issue

[sandy]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2)
{
//Make first string lower case
string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

//Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;
}

int main()
{
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt)
{
cout <<*VectIt<< '\n';
}
return 0;
}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

Why it's giving preference to first small case why not upper
letter ?
Can somebody help me in fixing the bug in code.
Any help or suggestion is appreciated.

 

[Haro Panosyan]

The result is consistant, because comparing uppercase "aaa" to "AAA"
will return false.

I found some solution ( not tested completly):

first keep a copy before transform:

string P1 = p1;
string P2 = p2;

and then return this:

return (p1 == p2) ? (P1 < P2) : (p1 < p2);

-haro

 

[Martin York]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2)
{
//Make first string lower case
string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

//Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;

}

int main()
{
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt)
{
cout <<*VectIt<< '\n';
}
return 0;

}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

Why it's giving preference to first small case why not upper
letter ?
Can somebody help me in fixing the bug in code.
Any help or suggestion is appreciated.

You are doing a case insensitive search. Thus "aaa" and "AAA" are
essentially equal. Thus normally you would not be able to determine
the order that these two items would be placed in the container. BUT
we have a caveat to that. Because you used stable_sort() any elements
that are equal will remain in the same relative order that they were
in the original container (see www.sgi.com/tech/stl/stable_sort.html
for the exact definition). So the output is as expected.


A couple of additional notes:
==============================
This comparison function:
bool my_comparison( string p1, string p2)

A copy of each parameter is made before this function is called (every
time it is called). It may be more efficient to pass the parameters by
const reference.

bool my_comparison(string& const p1,string& const p2)

If you change the definition you will not be allowed to directly
modify the parameters and thus you will be required to change your
algorithm accordingly.

Hope this helps
Martin.

 

[BobR]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2){
file://Make first string lower case

string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

file://Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;

[ See [1] below ]: p1 == p2 --> 65 == 65

}

int main(){
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt){
cout <<*VectIt<< '\n';
}
return 0;
}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

To get this output, first sort the vector [1], then do your stable_sort.
Since you are putting both strings in the same case (your predicate can't
tell which is larger), it just leaves the two in the order they appeared in
the vector.

Why it's giving preference to first small case why not upper
letter ?
Can somebody help me in fixing the bug in code.
Any help or suggestion is appreciated.

Try this (untested):

bool my_comparison( string p1, string p2){

std::string p3(p1), p4(p2); // make temp copy

string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

if( p1 == p2 ){ return p3 < p4;} // compare for equality

return p1 < p2;
} // my_comparison(string,string)

Maybe one of the real Guru's will come up with something less clunky.

[1] - on my machine (win98 partition),
cout<<" a="<< int('a')<<std::endl; // a=97
cout<<" A="<< int('A')<<std::endl; // A=65

 

[Daniel T.]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2)
{
//Make first string lower case
string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

//Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;
}

int main()
{
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt)
{
cout <<*VectIt<< '\n';
}
return 0;
}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

Why it's giving preference to first small case why not upper
letter ?

Because they are put in your container first. "stable_sort" tries to
maintain the existing order of the items as best it can. Since your code
says that "aaa" and "AAA" are equal, it doesn't swap them.

 

[Haro Panosyan]

The result is consitant, because when you compare UPPERCASE (aaa) with
AAA, it will return false (comparing with less operator).

The solution (not so nice) I found, could be this:

Save the copies before transform:
string P1 = p1;
string P2 = p2;

and then return this:

return (p1 == p2) ? (P1 < P2) : (p1 < p2);

-haro

 

[peter koch]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2)
{
//Make first string lower case
string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

//Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;

}

int main()
{
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt)
{
cout <<*VectIt<< '\n';
}
return 0;

}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

Why it's giving preference to first small case why not upper
letter ?
Can somebody help me in fixing the bug in code.
Any help or suggestion is appreciated.

You don't want a stable sort. A stable sort requires that items that
compare equal keep their relative order and that is exactly what
happens. You need to reconsider your comparison function so that
less("AAA","aaa") returns true if this is your criterion.

/Peter

 

[Otis Bricker]

Hello C++ Guru,
I am using STL stable_sort to sort the vector string data using
below code.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

bool my_comparison( string p1, string p2)
{
//Make first string lower case
string::iterator StringValueIterator = p1.begin();
transform (p1.begin(),p1.end(), StringValueIterator,toupper);

//Make second string lower case
StringValueIterator = p2.begin();
transform (p2.begin(),p2.end(), StringValueIterator,toupper);

return p1 < p2;
}

int main()
{
typedef vector<string> holder;
holder some_holder;
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

stable_sort(some_holder.begin(),some_holder.end(),my_comparison);
holder::iterator VectIt = some_holder.begin();
for( ; VectIt!=some_holder.end(); ++VectIt)
{
cout <<*VectIt<< '\n';
}
return 0;
}

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

I am sure I will not be the first to answer and am hardly a guru but just
in case...

Why it's giving preference to first small case why not upper
letter ?

It isn't giving preference to the lower case string, it is giving
preference to the string that is first in the collection. That is what
stable_sort promises to do. Since you defining "aaa" to be 'equal'(what
is the right term for this?) to 'AAA', stable_sort is not allowed to
change the orginal ordering.

Try it with:
some_holder.push_back("AAA");
some_holder.push_back("BBB");
some_holder.push_back("aaa");
some_holder.push_back("bbb");

or
some_holder.push_back("AAA");
some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("BBB");

and you'll see that the order you put items into the collection controls
would it sorts among 'equals'.

Can somebody help me in fixing the bug in code.
Any help or suggestion is appreciated.

To do that we would need to know just what the 'bug' is.

I'm guessing but are you trying to sort the strings case insensitively
but have ties broken by the case of the letters?

You could make the Predicate test this or you could do a simple sort of
the vector first.

add:
sort(some_holder.begin(),some_holder.end());// Stable_sort would
// also work.

before the other call to stable_sort. Not too pretty but easy.

Otis

 

[Pete Becker]

some_holder.push_back("aaa");
some_holder.push_back("bbb");
some_holder.push_back("AAA");
some_holder.push_back("BBB");

I got below result :
aaa
AAA
bbb
BBB

When I am expecting result like below :.

AAA
aaa
BBB
bbb

Why it's giving preference to first small case why not upper
letter ?

It's not, except by coincidence. With a stable sort, elements that
compare equal are in the same relative order after the sort as they were
before the sort. Since "aaa" and "AAA" compare equal under your sort and
"aaa" comes before "AAA" in the vector before the sort, "aaa" will come
before "AAA" after the sort. Same thing for "bbb" and "BBB".

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 

[sandy]

The result is consistant, because comparing uppercase "aaa" to "AAA"
will return false.

I found some solution ( not tested completly):

first keep a copy before transform:

string P1 = p1;
string P2 = p2;

and then return this:

return (p1 == p2) ? (P1 < P2) : (p1 < p2);

-haro

Nope. Above solution still fail for below test data.

AAA
BBB
aaa
bbb
TTTTTTT
tttttat

It give me result like below :
AAA
aaa
BBB
bbb
tttttat --------- Why this comes top of TTTTTTT
TTTTTTT --------- This should comes to top of tttttat


Any suggestion or help is appreciated.

 

[Juha Nieminen]

Any suggestion or help is appreciated.

I don't understand. You seem to want a case sensitive sorting order.
Then why don't you simply use a case sensitive comparison instead of
a case insensitive one?

 

[Charles Bailey]

Nope. Above solution still fail for below test data.

AAA
BBB
aaa
bbb
TTTTTTT
tttttat

It give me result like below :
AAA
aaa
BBB
bbb
tttttat --------- Why this comes top of TTTTTTT
TTTTTTT --------- This should comes to top of tttttat


Any suggestion or help is appreciated.

I think you need to describe what "sort" of sort you are expecting.

The results you get are correct for a stable, case insensitive sort and
for the two stage sort (case-insensitive, then case-sensitive to refine
equal members).

You say that you expect "TTTTTTT" to sort before "tttttat", but you
don't generalise this, so we can't tell what logical sort you are trying
to implement.

 

[Clark Cox]

Nope. Above solution still fail for below test data.

AAA
BBB
aaa
bbb
TTTTTTT
tttttat

It give me result like below :
AAA
aaa
BBB
bbb
tttttat --------- Why this comes top of TTTTTTT
TTTTTTT --------- This should comes to top of tttttat


Any suggestion or help is appreciated.

Because you told it to (i.e. 'A' comes before 'T').