Need help with sort()

[ayumi]

From Philip's code

struct sort_between_underscores
{
    int ToInt(const std::string& str)
    {
        int x;
        std::stringstream ss(str);
        ss >> x;
        return x;
    }

    int BetweenUnderscores(const std::string& fname)
    {
        std::string::size_type pos1 = fname.find("_");
        std::string::size_type pos2 = fname.find("_",pos1+1);
        return ToInt(fname.substr(pos1+1,pos2-pos1-1));
    }

    bool operator () (const std::string& lhs, const std::string& rhs)
    {
        return BetweenUnderscores(lhs) < BetweenUnderscores(rhs);
    }
};

How can i edit so that it is not sort between underscores....
I wanted it to sort by strcmp. Can it be done?

Thanks.....

[Paul McKenzie]

Originally posted by ayumi
I wanted it to sort by strcmp. Can it be done?

What will strcmp() give you that string::compare() won't give you?

Right now, you're all over the map, and it's impossible to know what you want to do.

Please list the rules for the sort. I've asked you at least three times already to do this, but you haven't done this. Once again, std::sort() needs some sorting criteria. It's your program, you should know the criteria for the sort. So far, you haven't provided any of us the criteria for the sort. Instead, it's just been a guessing game as to what you really want to do.

For every piece of code we give you, there's something that you feel is not correct. To end this, tell us the rules for the sort, and then we give you what we believe will follow your rules. If you have no rules or you yourself do not know what they are, how are we to help you?

Going the other way where we guess and give you code, and then you say it doesn't do the job, is not going to work. Doing this will just make the thread go on indefinetly.

Regards,

Paul McKenzie

[Philip Nicoletti]

Just to add to Paul's comments - using strcmp() will not
change anything. Look at the two sample codes below. In
the first code, I use char arrays, qsort() , and strcmp().
In the second, I use vector<string>, std::sort, and
(implicitly) operator < for std::string. The results of the
sorts are exactly the same. The reason - both strcmp() and
operator < for string use the same sorting criteria - what
is called "lexicographical compare".

#include <iostream>
#include <cstdlib>

int qsort_compare( const void *arg1, const void *arg2 )
{
   return strcmp( * ( char** ) arg1, * ( char** ) arg2 );
}


int main()
{
    unsigned int i;

    char *fnames[4];
    for (i=0; i<4; ++i)
        fnames[i] = new char[80];

    strcpy(fnames[0],"abc_11_xyz.txt");
    strcpy(fnames[1],"abc_2_xyz.txt");
    strcpy(fnames[2],"abc_111_xyz.txt");
    strcpy(fnames[3],"abc_1_xyz.txt");

    qsort( fnames, 4 , sizeof(char*) , qsort_compare);

    for (i=0; i<4; ++i)
        std::cout << fnames[i] << std::endl;

    for (i=0; i<4; ++i)
        delete [] fnames[i];

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    vector<string> fnames;

    fnames.push_back("abc_11_xyz.txt");
    fnames.push_back("abc_2_xyz.txt");
    fnames.push_back("abc_111_xyz.txt");
    fnames.push_back("abc_1_xyz.txt");

    sort( fnames.begin(), fnames.end() );

    for (unsigned int i=0; i<fnames.size(); ++i)
        std::cout << fnames[i] << std::endl;

    return 0;
}

What you need to determine is how windows explorer
orders the filenames. I don't know off hand what is
uses. I tried a very quick search on MSDN, but came
up empty.

[Philip Nicoletti]

I'm not sure, but it almost looks like it treats
characters such as underscore as if it were a space.
Here is something you can try ... no guarentees ...
Also, this is not very efficient, as I copy each string
and then modify the copied string. If you test it,
and it does what you want, I could come up with
more efficient code if it is needed.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct sort_criteria
{
    bool operator () (const string& lhs, const string& rhs)
    {
        string clhs = lhs;
        string crhs = rhs;

        string::iterator it;

        for (it=clhs.begin(); it!=clhs.end(); ++it)
            if ( !isalpha(*it) && !isdigit(*it)) *it = ' ';

        for (it=crhs.begin(); it!=crhs.end(); ++it)
            if ( !isalpha(*it) && !isdigit(*it)) *it = ' ';

        return clhs < crhs;
    }
};

int main()
{
    vector<string> fnames;

    fnames.push_back("abc_11_xyz.txt");
    fnames.push_back("abc_2_xyz.txt");
    fnames.push_back("abc_111_xyz.txt");
    fnames.push_back("abc_1_xyz.txt");

    sort( fnames.begin(), fnames.end() , sort_criteria() );

    for (unsigned int i=0; i<fnames.size(); ++i)
        std::cout << fnames[i] << std::endl;

    return 0;
}

[Philip Nicoletti]

Well, the code in my last post doesn't order
the filenames like windows explorer. (a_1.txt and
a.1.txt could be in any order). Also, the case of the
filename should not matter) Here is one more guess at
the ordering criteria (and it IS a guess only).
Without actual documentation, I don't think I
can do anything else.

struct sort_criteria
{
    struct strange_compare
    {
        bool operator () (char x, char y) const
        {
            bool bx = isalpha(x) || isdigit(x);
            bool by = isalpha(y) || isdigit(y);

            // if both or neither characaters are alpha/digits ... compare as normal
            if ( bx &&  by) return tolower(x)<tolower(y);
            if (!bx && !by) return tolower(x)<tolower(y);

            // if one is alpha/digit and the other is not, set the
            // non alpha/digit char less than the alpha/digit char
            if (!bx &&  by) return true;
            if ( bx && !by) return false;

            return false; // will never get here
        }
    };

    bool operator () (const string& lhs, const string& rhs)
    {
        return lexicographical_compare(lhs.begin(),lhs.end(),
                        rhs.begin(),rhs.end(),strange_compare());
    }
};

usage :

    sort( fnames.begin(), fnames.end() , sort_criteria() );

[ayumi]

I was thinking whether if i could use strcmp or lexico compare to check each string in the vector to see if it is bigger or smaller than the other.

Then put it in front or behind to get the order. I don't know if this is possible to get the order i wanted.

i go and try type out 1 using strlen and strcmp ... maybe that will let your see what i wanted.

Sorry for not stating clearly what i wanted but i tried to state as clear as i can already. sorry.. and thanks

[jwbarton]

The sorting criteria that you seem to want is similar to one that I have used for a number of years. The following code shows the sorting criteria that I use:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;


struct sort_criteria_numeric
   {
   int CountDigits( const string& thisString, string::const_iterator it )
      {
      int count = 0;

      while ( it != thisString.end() && isdigit(*it) )
         {
         ++count;
         ++it;
         }

      return count;
      }

   bool operator() ( const string& lhs, const string& rhs )
      {
      string::const_iterator lit = lhs.begin();
      string::const_iterator rit = rhs.begin();

      // Loop until compare is complete
      while ( lit != lhs.end() && rit != rhs.end() )
         {
         // Check if the strings currently point to numbers
         if ( isdigit(*lit) && isdigit(*rit) )
            {
            int countLeft = CountDigits( lhs, lit );
            int countRight = CountDigits( rhs, rit );

            // Check if the numbers don't have equal length strings
            if ( countLeft != countRight )
               return ( countLeft < countRight );

            // Loop through the digits, comparing the numbers
            while ( countLeft )
               {
               // Check each digit
               if ( *lit != *rit )
                  return ( *lit < *rit );

               // Go to the next character in both strings
               ++lit;
               ++rit;
               countLeft--;
               }
            }
         else
            {
            // Check each character
            if ( *lit != *rit )
               return ( *lit < *rit );

            // Go to the next character in both strings
            ++lit;
            ++rit;
            }
         }

      return ( rit != rhs.end() );
      }
   };


int main(int argc, char* argv[])
   {
   vector<string> fnames;

   fnames.push_back( "abc_001_abc.txt" );
   fnames.push_back( "abc_01_abc.txt" );
   fnames.push_back( "abc_11_abc.txt" );
   fnames.push_back( "abc_2_abc.txt" );
   fnames.push_back( "abc_111_abc.txt" );
   fnames.push_back( "abc_1_abc.txt" );

   fnames.push_back( "abc_001_xyz.txt" );
   fnames.push_back( "abc_01_xyz.txt" );
   fnames.push_back( "abc_11_xyz.txt" );
   fnames.push_back( "abc_2_xyz.txt" );
   fnames.push_back( "abc_111_xyz.txt" );
   fnames.push_back( "abc_1_xyz.txt" );

   sort( fnames.begin(), fnames.end(), sort_criteria_numeric() );

   for ( vector<string>::iterator it = fnames.begin(); it != fnames.end(); ++it )
      cout << *it << endl;

   return 0;
   }

The comparison of the numerical parts of a string is done by using a very simple check - if the length of the substring that is numeric is shorter in one string than the other, that string is before the other string in the sort order. If the length is equal, then the numeric characters are compared. This results in a sort order that works as the user generally expects as long as leading zeroes are added consistently. If some numbers are given leading zeroes, but others aren't, the sort order will put the shorter numbers first, which are not always the numbers with the lowest numeric value.

I including some additional strings in the list to show you the behavior of this comparison.

Best regards,
John

[ayumi]

omg!! thanks a lot ... i have tried and seems to works fine.

thanks you and everyone