Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

STL stable_sort sorting issue


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.

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

On May 29, 12:45 pm, sandy <sandip.w@gmail.com> wrote:

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.

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

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

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
In article <1180442852.291017.240@k79g2000hse.googlegroups.com>,

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.

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

sandy <sandip.w@gmail.com> wrote in message ...
> 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

Comment says lowercase, but, you use 'std::toupper'? <G>

>         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

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
--
Bob R
POVrookie

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

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 <sandip.w@gmail.com> wrote in news:1180442852.291017.240950
@k79g2000hse.googlegroups.com:

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

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

On 29 Maj, 21:45, sandy <sandip.w@gmail.com> wrote:

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

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

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

On May 30, 1:07 am, Haro Panosyan <h@ti.com> wrote:

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.

sandy wrote:
> 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?

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.

On 2007-05-30 00:25:47 -0700, sandy <sandip.w@gmail.com> said:

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

--
Clark S. Cox III
clarkc@gmail.com

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc