once more sorting structs....

[Steve Baerthlein]

hello,

i've implemented a structure like that:

struct file_struct
{
string strName;
string strType;
int nKB;
time_t date;
bool bIsDir;
};

these member-vars represent the attributes filled by the content of a directory, and the flag bIsDir shows if it is an directory or not.
the results are saved in an vector<file_struct>vc; for example:


1 ttt
2 adm(dir)
3 054(dir)
4 gah
5 j02(dir)
6 rec (dir)
7 fhr(dir)

now i've got 7 elements which are directories and 2 elements which are other files
i sort them like this:

int CompDir(const void* lhs, const void* rhs)
{
bool bLhs = ((file_struct*)lhs)->bIsDir;
bool bRhs = ((file_struct*)rhs)->bIsDir;

if (bLhs < bRhs) return 1;
if (bLhs > bRhs) return -1;

return 0;
}

and

qsort(static_cast<void*>(&vc[0]), vc.size(), sizeof(file_struct), CompDir);
getting something like that:

1 fhr(dir)
2 adm(dir)
3 054(dir)
4 rec (dir)
5 j02(dir)
6 gah
7 ttt

so i've sorted my array with directories and other files...

but now i'm searching for an possibility to sort the directory-elements and the file-elements in an alphabetical order which should lokk like similar to this way:


1 054 (dir)
2 adm(dir)
3 fhr(dir)
4 j02(dir)
5 rec (dir)
6 gah
7 ttt


i've tried it with std::sort and std::partial_sort but didn't get very far...

bool cn(const file_struct lhs, const file_struct rhs)
{
return lhs.strName.c_str() < rhs.strName.c_str();
}
sort(vc.begin(), vc.begin() + 5, cn);

normally i would do this with qsortand:

int CompName(const void* lhs, const void* rhs)
{
return _stricmp(((file_struct*)lhs)->strName.c_str(), ((file_struct*)rhs)->strName.c_str());
}


...so do i have to implement my struct as a class and do some operator work, in order to use the std::-sorting algos?

i would be very greatefull for any hints,
thanx in advance,
have a nice day,
ciao,
stefan

[Philip Nicoletti]

using std::sort(), here is a compare function :

inline bool sortCompare(file_struct& a, file_struct &b) // note the "&"
{
    if ( a.bIsDir != b.bIsDir )
    {
        return a.bIsDir;
    }

    return a.strName < b.strName;
}

and here is its usage:

    sort(vc.begin() , vc.end() , sortCompare);  // note vc.end()

[cup]

qsort is a C function: it doesn't know anything about vectors. If you intend to use qsort, you have to give it an array of pointers to structures: not a vector.

If you intend to use vectors, use Philip Nicoletti's solution.

[jfaust]

I believe qsort will work on vector containers, because the storage is guaranteed to be contiguous. It won't work, however, on other STL containers.

Still, use std::sort.

Jeff

[Graham]

But the OP's file_struct is not POD, so qsort won't............ oh, no, not again!

[Paul McKenzie]

Originally posted by jfaust
I believe qsort will work on vector containers, because the storage is guaranteed to be contiguous. It won't work, however, on other STL containers.

Still, use std::sort.

Jeff

Hello Jeff,

qsort() is only guaranteed to work on POD types. The OP has std::string, making the class non-POD. Therefore the only safe method is std::sort (remember the Portland compiler? )

Regards,

Paul McKenzie

[jfaust]

Boy, do I remember...

The point I was attempting to make is correct. Unfortunately, the example wasn't.

Jeff

[Steve Baerthlein]

thank you all for your explenations!!!!

is it possible to sort a std::vector with std::sort this way?
my vector filled with std:string elements:

1 c
2 d
3 a
4 e
5 b


now i want to sort the first 3 elements like this:

1 a
2 c
3 d
4 e
5 b

and afterwards i sort the last 2 elements, so that the content of my vector looks like:

1 a
2 c
3 d
4 b
5 e


is it possible to change the position of the iterator to do this (just a scetch, symbolic syntax...):

sort(vc[0], vc[3], comp);

and afterwards

sort(vc[4], vc[5], comp);


thank you for your patience,
ciao,
stefan

[Philip Nicoletti]

    sort(vc.begin(),vc.begin()+3);
    sort(vc.begin()+3,vc.end());

of course, vector must be big enough for "vc.begin()+3" to
be valid in both sorts.


If sorting in ascending order, no need for a comparison function.

[Steve Baerthlein]

i'm very sorry for this seems to become one of these long postings, but i'm a beginner in stl c++ (i'm just used to the mfc-stuff)...

could you help me out with this, where is my mistake?

inline bool c(const string &lhs, const string &rhs)
{
return lhs.c_str() < rhs.c_str();
}

int main(int argc, char* argv[])
{
string s1 = "c";
string s2 = "d";
string s3 = "a";
string s4 = "e";
string s5 = "b";

vector<string>v;
v.push_back(s1);
v.push_back(s2);
v.push_back(s3);
v.push_back(s4);
v.push_back(s5);

sort(v.begin(), v.begin() + 3, c);

sort(v.begin() + 3, v.end(), c);

return 0;
}

this was just a test; the output looks like:

unsorted
c
d
a
e
b

sorted 1-3
a
d // wrong
c
e
b

sorted 3-5
a
d
c
b
e


thanx for now,
stefan

[Philip Nicoletti]

1) your comparison function is incorrect.

lhs.c_str() returns a pointer to a c-style string.
If you want to use those pointers, you should
use strcmp().

A simpler change would be ...

inline bool c(const string &lhs, const string &rhs)
{
   // return lhs.c_str() < rhs.c_str();
    return lhs < rhs;
}

2) if comparing strings using the default comparison, you
do not need a comparison function ...

    sort(v.begin(), v.begin() + 3);
    sort(v.begin() + 3, v.end());

[Steve Baerthlein]

hello again,
i've tried this function before

inline bool c(const string &lhs, const string &rhs)
{
return lhs < rhs;
}
but i'm not able to compile this code due to:

error C2678: binary '<' : no operator defined which takes a left-hand operand of type 'const class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >' (or there is no
acceptable conversion)
(i'm using vc++6.0)

what i would like to use is:

int CompName(const void* lhs, const void* rhs)
{
return _stricmp(((file_struct*)lhs)->strName.c_str(), ((file_struct*)rhs)->strName.c_str());
}
and calling afterwards
qsort(static_cast<void*>(&vc[0]), vc.size(), sizeof(file_struct), CompDir);

but i'm only able to sort the whole array and not parts of it with qsort which is my desire....

perhaps i have to write my own sort - function. i can't use the default stl sort-function because of the operator<(a,b) which would be rather complicate to implement for my structur, and also a bool compare-function would be (how should equal elements be sorted aso...)

thank you for your patience,
bye,
stefan

[Paul McKenzie]

Hello Steve,

Your comparison is still wrong. Since you have a vector of file_struct, your comparison takes references to file_struct, not string. Here is a stripped down example. Adapt it to your example.

#include <string>
#include <vector>
#include <algorithm>
class A
{
   public:
      std::string sa;
};

std::vector<A> VA;

bool c(const A& A1, const A &A2)
{
   return A1.sa < A2.sa;
}

int main()
{
   std::sort(VA.begin(), VA.end(), c);
}

Note that this compiles cleanly. You are passing to std::sort's comparison function A objects, not std::string's. And as I pointed out, your class is a non-POD (plain old data) class because of std::string. Therefore you should not use qsort() on it since sorting non-POD objects is not guaranteed to work with qsort().

Regards,

Paul McKenzie

[Philip Nicoletti]

Sorry. From your one message I thought the vector was
a vector<string> , not vector<file_struct>.

As Paul mentioned, if you are sorting vector<A> , the
comparison fucntion prototype will be :

bool comp(const A& lhs, const A& rhs);

Is there a reason you abandoned your first thought of
just using one sort and having the comparison put
the directories first ?

Here is a simple working example. I also made the comparison
function a functor - it is a little faster that way. Notice
the "()" after the sortCompare in the call to sort, and notice
the way sortCompare is written. It can also be made faster by
using specialization, but unless you have a large number of
elements it will not make that much difference.

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

using namespace std;


struct file_struct
{
    string strName;
    string strType;
    int nKB;
    time_t date;
    bool bIsDir;
};



struct sortCompare
{
    inline bool operator ()(file_struct& a, file_struct& b)
    {
        if ( a.bIsDir != b.bIsDir )
        {
         return a.bIsDir;
        }

        return a.strName < b.strName;
    }
};



int main()
{

    vector<file_struct>vc; 

    file_struct fs;

    fs.strName = "ttt";
    fs.bIsDir = false;
    vc.push_back(fs);

    fs.strName = "adm";
    fs.bIsDir = true;
    vc.push_back(fs);

    fs.strName = "054";
    fs.bIsDir = true;
    vc.push_back(fs);

    fs.strName = "gah";
    fs.bIsDir = false;
    vc.push_back(fs);

    fs.strName = "j02";
    fs.bIsDir = true;
    vc.push_back(fs);

    fs.strName = "rec";
    fs.bIsDir = true;
    vc.push_back(fs);

    fs.strName = "fhr";
    fs.bIsDir = true;
    vc.push_back(fs);

    sort(vc.begin() , vc.end() , sortCompare());

    for (int i=0; i<vc.size(); ++i)
    {
        cout << vc[i].strName << endl;
    }

    return 0;
}

[Steve Baerthlein]

hi again,

just wanted to say thank you very muchtoo all of you.
that was exactly what i was searching for. i'm sorry for my confusing postings, i just wanted to achieve those things i wrote in my first posting, later on i tried only to cope with the more simple string-vector-thing, but finally you told me how to succseed....

thanx,
stefan