Need help with sort()

Can i know how to use the <algorithm> sort function in c++?

Is it possible to use that to sort the order in my string array?

Thanks

You can use qsort to sort your string array

Code:

---

int sortfunc(const void *elem1, const void *elem2)
{ 
  return strcmp(*((LPSTR*)elem1), *((LPSTR*)elem2));
}

...

LPSTR strs[] = {"String4", "String1", "String3", "String2"};
qsort(&strs[0], 4, sizeof(strs[0]), sortfunc);

---

Hope it will help you

Using the std::sort() Method...

Quote:

---

Originally posted by rxbagain
You can use qsort to sort your string array

---

Well...one side note....you should not use 'qsort()' with STL types like 'vector' for several reasons like for example:

• 'qsort()' is not guaranteed to work with non-POD types (structures and classes)
• 'qsort()' is not type-safe

hmm how can i use the code to sort 2D array?
i need a more simple code on the sort()...
thanks

Well....how does your array look like?

i have a storage[10][100] array....
storing 10 string.

i wanted to sort it by name.

how can i use the code to modify to this?

Code:

---

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

#include <conio.h>


int main()
{
  std::vector<std::string> StringArray;

  StringArray.push_back("String One");
  StringArray.push_back("String Four");
  StringArray.push_back("String Two");
  StringArray.push_back("String Three");

  std::sort(StringArray.begin(), StringArray.end());

  // Print results
  for(std::vector<std::string>::iterator iter = StringArray.begin();
      iter != StringArray.end();
      ++iter)
    std::cout << *iter << std::endl;

  // Wait for keystroke
  _getch();

  return 0;
}

---

a) You should use std::vector<std::string>. Much easier to handle instead of char[10][100].

Code:

---

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

typedef std::vector<std::string> StringArray;

using namespace std;

StringArray S(3, ""); 

int main()
{
    S[0] = "Paul";
    S[1] = "John";
    S[2] = "Alan";
    cout << "Before sort:" << endl;
    cout << S[0] << " " << S[1] << " " << S[2] << endl;

    std::sort(S.begin(), S.end() );
    cout << "After sort:" << endl;
    cout << S[0] << " " << S[1] << " " << S[2] << endl;
}

---

The problem with sorting a char[10][100] is that the element that you are sorting (a char[100]) is not an l-value, and std::sort() requires that what you're sorting is an l-value. A wrapper for the array is required:

Code:

---

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

struct Wrapper
{
    Wrapper(const char *val="") { strcpy(Char100, val); }
    char Char100[100];
};

bool SortIt( const Wrapper& first,  const Wrapper& second)
{
    int result = strcmp(first.Char100, second.Char100);
    return (result < 0)?true:false;
}

int main()
{
    Wrapper GlobArray[] = {"Paul", "John", "Alan"};

    cout << "Before sort:" << endl;
    cout << GlobArray[0].Char100 << " " << GlobArray[1].Char100 << " " << GlobArray[2].Char100 << endl;

    cout << "After sort" << endl;
    std::sort(GlobArray, GlobArray + 3, SortIt);
    cout << GlobArray[0].Char100 << " " << GlobArray[1].Char100 << " " << GlobArray[2].Char100 << endl;
}

---

Regards,

Paul McKenzie

Quote:

---

Originally posted by Andreas Masur
Well...one side note....you should not use 'qsort()' with STL types like 'vector' for several reasons like for example:

• 'qsort()' is not guaranteed to work with non-POD types (structures and classes)
• 'qsort()' is not type-safe

---

Not only that, the compiler can optimize std::sort and the functor more aggressively than qsort(). In truth, there is no reason whatsoever to use qsort() in a C++ program unless the compiler's library doesn't have STL (which is rare).

Even if the compiler doesn't have STL, you still end up having to write your own sort, since as you pointed out, qsort() is not guaranteed to work for non-POD types.

Regards,

Paul McKenzie

StringArray S(3, "");

this is equivilant to S[3][??] ??
how many characters does it takes in?

sorry quite new to STL stuff

Paul: i get 4 warning with your code.....

warning C4786: 'std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >
>::~vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >' : identifier was truncated to '255' characters in the debug information


And 1 more serious problem... fstream f.open cannot open the array....

error C2664: 'fopen' : cannot convert parameter 1 from 'class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >' to 'const char *'


wad is that? anyways to solve?

Thanks

Quote:

---

Originally posted by ayumi
StringArray S(3, "");

this is equivilant to S[3][??] ??
how many characters does it takes in?

---

A vector is a dynamic array. The vector type is std::string. The vector has 3 std::strings, each initialized to "". A std::string grows dynamically, so the number of characters that can be stored is theoretically unlimited.

Quote:

---

Paul: i get 4 warning with your code.....

---

Those warnings only mean that the debugger will recognize only the first 255 characters. They are harmless and can be turned off with

#pragma warning (disable : 4786)

Quote:

---

And 1 more serious problem... fstream f.open cannot open the array....

error C2664: 'fopen' : cannot convert parameter 1 from 'class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >' to 'const char *'

---

std::string whatever;
fopen( whatever.c_str(), "r");

The c_str() member function returns a const char *.

Quote:

---

sorry quite new to STL stuff

---

Get "Accelerated C++" by Koenig & Moo. You would have learned immediately not to use char[10][100] and instead do what I posted.

Regards,

Paul McKenzie

Quote:

---

Originally posted by ayumi
warning C4786: 'std::vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > >
>::~vector<std::basic_string<char,std::char_traits<char>,std::allocator<char> >,std::allocator<std::basic_string<char,std::char_traits<char>,std::allocator<char> > > >' : identifier was truncated to '255' characters in the debug information

---

Take a look at this FAQ...

Since you are new to the 'vector' class, besides the book Paul already mentioned...take a look at this introduction to the vector class...

wow... thanks a lot paul and andreas and those who helped me!!

another thing is ..... do i need to delete the vector after used??

Quote:

---

Originally posted by ayumi
another thing is ..... do i need to delete the vector after used??

---

Yes and no...depending where you created the vector...

Code:

---

// Stack
int main()
{
  std::vector<int> IntVector;

  // No need to explicitely delete the vector, will be done implicitely

  return 0;
}


// Heap
int main()
{
  std::vector<int> *PointerToIntVector = new std::vector<int>;

  // Here we need to explicitely delete the vector, otherwise we will have a memory leak...
  delete PointerToIntVector;

  return 0;
}

---

Quote:

---

Originally posted by ayumi
wow... thanks a lot paul and andreas and those who helped me!!

another thing is ..... do i need to delete the vector after used??

---

The vector will always clean up the memory it has allocated for itself when destroyed. If you place objects in a vector, you don't call delete. You make a vector of your objects, and you don't worry about memory management. Makes the application easier to maintain, and easier to debug.

However, if you have place pointers in a vector that point to dynamically allocated objects (i.e. you used "new" to create the object), then of course, you are responsible for deleting the objects. The vector<> does not know that the object placed in the vector were created with "new", therefore it can't delete them automatically.

The rule of thumb is that if your application uses "new" or "new[]", you must use "delete" or "delete[]".

Regards,

Paul McKenzie

!!
the sort is not quite right....

i hav stored for example 2 files in the vector

abc_1_xyz.txt
abc_11_xyz.txt

the sort shows the second file first and then the first 1...
by right i wanted opposite.

How do i enhance the sort?

Quote:

---

Originally posted by ayumi
!!
the sort is not quite right....

---

The sort is correct. The underscore comes after the '1' in the ASCII collating sequence. So I don't know what you are really asking us to do...

Regards,

Paul McKenzie

sorry for not stating clearly....

i mean vector [0] stored abc_11_xyz.txt
vector [1] stored abc_1_xyz.txt

after using sort.. i wanted [0] to store abc_1_xyz.txt and [1] to store abc_11_xyz.txt.

How do i do it?

Thanks

You are still not making yourself clear. In your first post, you stated that you want a sort, so you have a sort. The sort is correct, a '_' comes after '1' in the ASCII collating sequence. Do you agree or disagree with that statement?

OK, are you saying you want to sort in descending order and not ascending order? If you store in descending order, the '_' will come before '1', but 'B' will come before 'A', '9' will come before '8', etc. So for example, here is what you'll get

FOX.TXT
FIRE_1.TXT
FIRE11.TXT
DOG.TXT
CAT.TXT
ANIMAL.TXT

Here the FIRE_1.TXT comes before FIRE11.TXT, but also DOG.TXT comes before CAT.TXT. Is this what you want? If this is not what you want, then what exactly do you want? You can't change the ASCII collating sequence. If you need a specialized sort that doesn't use the ASCII collating sequence, you should explain exactly what your rules are of sorting.

Regards,

Paul McKenzie

This problem is quite common. Usually, the files are created
in another program. The best solution is to have that program
create filenames that are compatible with sort routines (whether
it be sort(), qsort(), or any other routine). That is, instead of
abc_1_xyz.txt , the code would name it abc_01_xyz.txt

This assumes that abc_99_xyz is the "largest" possble value. I
usually put a large number of leading zeroes : abc_00001_xyz.txt


Given a specific file naming sequence, you can get the sorting routine
to sort your files like you want - but then, if you run the code
with files that don not fit the naming convention, it will not work.

In your case, the sort could use the characters in between the underscore
characters to decide the order. Here is sample code. Note,
I don't check that the filename is in the correct format -
you should probably throw an exception if a problem occurs.

Code:

---

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

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

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

int main()
{
    std::vector<std::string> fnames;

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

    std::sort(fnames.begin(),fnames.end(),sort_between_underscores());

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

    return 0;
}

---

sorry .... but that's what i need ...

abc_1_xyz.txt
abc_2_xyz.txt
abc_11_xyz.txt

I need to get this no matter using what kind of sort ....
And my filename is not always this format.....

if array[0] = 11.txt
array[1] = 1.txt

i need sort 1.txt to be first

What i need is to follow the sequence from Windows...

The filename is obtain from CFileDialog multi select and i stored in array. But CFileDialog did not follow the sequence and i do not know what has happen that's why i'm forced to sort it manually.

In window the sequence is for example
abc_1_xyz.txt
abc_2_xyz.txt
abc_3_xyz.txt
abc_11_xyz.txt

Anyway to make the GetNextPathName(pos) to follow that sequence and store in my array accordingly?

Thanks. :(

Change my previosu code to :

Code:

---

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

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);
    }
};

int main()
{
    std::vector<std::string> fnames;

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

    std::sort(fnames.begin(),fnames.end(),sort_between_underscores());

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

    return 0;
}

---

the sort works for any type of format?

like 1.txt 11.txt

abc1.txt abc11.txt

any format ?

thanks for that code ~

No, not any sequence ... just those that have 2 underscores
as per your example. By the way, for these files :

abc_1_xyz.txt
abc_2_xyz.txt
abc_3_xyz.txt
abc_11_xyz.txt

Windows Explorer on W2K gives this order :

abc_1_xyz.txt
abc_11_xyz.txt
abc_2_xyz.txt
abc_3_xyz.txt

Not the order you said ...

i'm using win xp...

but your code i change to other format it seems to works lol!
how to modify your code to works for any format?

Quote:

---

What i need is to follow the sequence from Windows...

---

So the original question is not how to call a sort routine, the question is really what determines the order of items. This is basically what I was trying to ask you -- how do you determine what item comes before another item.

By default, items are sorted by the operator < unless you override it. Since you are sorting strings, the standard ASCII collating sequence is used to determine what goes where. ASCII knows nothing about how Windows Explorer lays out items -- that is a "feature" of Windows Explorer.

If you want to sort any other way besides the default, you have to provide the rules of the sort. This is what Philip did -- he didn't change how to call the sort, except that he provided "rules for sorting" in the third parameter to the std::sort() function.

Regards,

Paul McKenzie

i wanted to sort that's because when i retrieve the filename from the directory i chose from file dialog and store in array, it is not the same order as in window

window sequence can be anything .....i just wanted to extract the filename out in order of how it is in window directory but it seems that the getpathname function didn't get it out in the same sequence.. hence my array is messed up.

anyways to extract in sequence of the window? so that i do not need so much trouble to sort. ;(

Thanks~

Then what you want is not a "sort", since you don't have any rules laid out as to how to sort. You want to gather names in some order.

Maybe you should start a brand new thread, and not mention "sort" but just state you want to retrieve the file names in the order that "application x" retrieves them. If it then turns out that there is a way to "sort" them, then it will reveal itself. But to start the thread saying you want to sort has been misleading.

Regards,

Paul McKenzie

From Philip's code

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? :confused:

Thanks.....

Quote:

---

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

---

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

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

Code:

---

#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;
}

---

Code:

---

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

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.

Code:

---

#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;
}

---

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.

Code:

---

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 :

Code:

---

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

---

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 :(

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:

Code:

---

#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

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

thanks you and everyone :rolleyes: