std::stable_sort with predicate woes

[William Payne]

Hello, in my program I have a std::vector of structs, a struct such as:

enum Type
{
TYPE_FILE,
TYPE_FOLDER
};

struct Entry
{
Entry(const char* name,
const char* description,
long file_size,
Type type,
HICON icon)
:
m_file_size(file_size),
m_type(type),
m_icon(icon)
{
std::memset(m_name, '\0', sizeof(m_name));
std::memset(m_description, '\0', sizeof(m_description));
std::memset(m_file_size_as_string, '\0',
sizeof(m_file_size_as_string));

std::strcpy(m_name, name);

if(m_type == TYPE_FILE)
{
std::sprintf(m_file_size_as_string, "%li KB", m_file_size);
}
}

char m_name[MAX_PATH + 1];
char m_description[64];
long m_file_size;
char m_file_size_as_string[32];
Type m_type;
HICON m_icon;
};

As you can see, each Entry can be either a TYPE_FILE or a TYPE_FOLDER. Now I
need to sort this vector, and I am beginning with sorting on names. But
there is a catch, an Entry of type TYPE_FOLDER is always less than an Entry
of type TYPE_FILE. So if I sort my vector in descending order, I want all
elements of TYPE_FOLDER to come first (sorted by name), and then all
elements of TYPE_FILE (sorted by name). If sorted by ascending order I want
all elements of TYPE_FILE first (sorted by name) followed by all elements of
type TYPE_FOLDER (sorted by name). (Yes, I am trying to mimic Windows XP
explorer.) How do I do that? I tried the following which seems to work for
ascending order, but for descending order I get all folders first when they
should be last. Please help me solve this!

bool sort_on_name(const Entry& lhs, const Entry& rhs)
{
if(lhs.m_type == TYPE_FOLDER && rhs.m_type == TYPE_FILE)
{
return true;
}

if(lhs.m_type == TYPE_FILE && rhs.m_type == TYPE_FOLDER)
{
return false;
}

return std::strcmp(lhs.m_name, rhs.m_name);
}

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

Thanks for any replies

/ WP

 

[Dan Bloomquist]

I tried the following which seems to work for
ascending order, but for descending order I get all folders first when they
should be last. Please help me solve this!

bool sort_on_name(const Entry& lhs, const Entry& rhs)
{
if(lhs.m_type == TYPE_FOLDER && rhs.m_type == TYPE_FILE)
{
return true;
}

if(lhs.m_type == TYPE_FILE && rhs.m_type == TYPE_FOLDER)
{
return false;
}

return std::strcmp(lhs.m_name, rhs.m_name);
}

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

So, you have a sort_on_name_des(...) with all the truths reversed and call:

std::stable_sort(entries.begin(), entries.end(), sort_on_name_des);

And it doesn't work?

/ WP

Best, Dan.

 

[John Harrison]

Hello, in my program I have a std::vector of structs, a struct such as:

How do I do that? I tried the following which seems to work for

ascending order, but for descending order I get all folders first when they
should be last. Please help me solve this!

bool sort_on_name(const Entry& lhs, const Entry& rhs)
{
if(lhs.m_type == TYPE_FOLDER && rhs.m_type == TYPE_FILE)
{
return true;
}

if(lhs.m_type == TYPE_FILE && rhs.m_type == TYPE_FOLDER)
{
return false;
}

return std::strcmp(lhs.m_name, rhs.m_name);

Perhaps you mean this

return std::strcmp(lhs.m_name, rhs.m_name) < 0;

what you have doesn't work at all.

}

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

Any reason for using stable_sort? Since you cannot have files or folders
with the same name it doesn't seem necessary, just sort would be better.

So if I understand you do

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

for ascending order and it works. What do you do for descending order (which
doesn't work)? Since that is where your problem lies it would have helped to
post that code. I would do this

bool reverse_sort_on_name(const Entry& lhs, const Entry& rhs)
{
return !sort_on_name(lhs, rhs);
}

std::sort(entries.begin(), entries.end(), reverse_sort_on_name);

john

 

[velthuijsen]

---8<------8<------8<---

As you can see, each Entry can be either a TYPE_FILE or a TYPE_FOLDER. Now I
need to sort this vector, and I am beginning with sorting on names. But
there is a catch, an Entry of type TYPE_FOLDER is always less than an Entry
of type TYPE_FILE. So if I sort my vector in descending order, I want all
elements of TYPE_FOLDER to come first (sorted by name), and then all
elements of TYPE_FILE (sorted by name). If sorted by ascending order I want
all elements of TYPE_FILE first (sorted by name) followed by all elements of
type TYPE_FOLDER (sorted by name). (Yes, I am trying to mimic Windows XP
explorer.) How do I do that? I tried the following which seems to work for
ascending order, but for descending order I get all folders first when they
should be last. Please help me solve this!

---8<------8<------8<---

Ascending sort, sorts values from smallest to greatest (as in -1 < 0 <
5)
Descending sort, sorts values from greatest to smallest (as in 7 > 0 >
-10)
You have just defined that the value of TYPE_FILE < TYPE_FOLDER which
is conflicting with the claim you make that an Entry of TYPE_FOLDER is
always less then an Entry of TYPE_FILE.

Either you rewrite the sort so that in ascending the TYPE_FOLDER
entries end up first (and then they will show up last on descending).
Or if you really insist on the entries of TYPE_FOLDER always being
last you use remove_copy_if to split up the vector then sort the main
(containing TYPE_FILE) and temporary vector (containing TYPE_FOLDER)
then insert the temporary vector back into the main vector.

If the comment I kept is wrong and the function you posted below it is
correct.
How do you perform the descending sort?

 

[William Payne]

How do I do that? I tried the following which seems to work for

Perhaps you mean this

return std::strcmp(lhs.m_name, rhs.m_name) < 0;

what you have doesn't work at all.


Any reason for using stable_sort? Since you cannot have files or folders
with the same name it doesn't seem necessary, just sort would be better.

So if I understand you do

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

for ascending order and it works. What do you do for descending order (which
doesn't work)? Since that is where your problem lies it would have helped to
post that code. I would do this

bool reverse_sort_on_name(const Entry& lhs, const Entry& rhs)
{
return !sort_on_name(lhs, rhs);
}

std::sort(entries.begin(), entries.end(), reverse_sort_on_name);

john

Thanks for your reply, John. I ended up with this code:

bool sort_on_names_ascending(const Entry& lhs, const Entry& rhs)
{
return sort_on_name(lhs, rhs);
}

bool sort_on_names_descending(const Entry& lhs, const Entry& rhs)
{
return !sort_on_name(lhs, rhs);
}

bool sort_on_sizes_ascending(const Entry& lhs, const Entry& rhs)
{
return sort_on_size(lhs, rhs);
}

bool sort_on_sizes_descending(const Entry& lhs, const Entry& rhs)
{
return !sort_on_size(lhs, rhs);
}

bool sort_on_name(const Entry& lhs, const Entry& rhs)
{
if(lhs.m_type == TYPE_FOLDER && rhs.m_type == TYPE_FILE)
{
return true;
}

if(lhs.m_type == TYPE_FILE && rhs.m_type == TYPE_FOLDER)
{
return false;
}

std::string s1(lhs.m_name);
std::string s2(rhs.m_name);

std::transform(s1.begin(), s1.end(), s1.begin(), tolower);
std::transform(s2.begin(), s2.end(), s2.begin(), tolower);

return strcmp(s1.c_str(), s2.c_str()) < 0;
}

bool sort_on_size(const Entry& lhs, const Entry& rhs)
{
return lhs.m_file_size < rhs.m_file_size;
}

The *_ascending/descending()-functions are called by std::stable_sort
depending on if I sort on names or sizes (settings folders to size -1) and
depending on if I sort in descending order or in ascending order. It seems
to work as it should...looks okay to you too?

/ WP

 

[John Harrison]

helped

Thanks for your reply, John. I ended up with this code:

bool sort_on_names_ascending(const Entry& lhs, const Entry& rhs)
{
return sort_on_name(lhs, rhs);
}

bool sort_on_names_descending(const Entry& lhs, const Entry& rhs)
{
return !sort_on_name(lhs, rhs);
}

bool sort_on_sizes_ascending(const Entry& lhs, const Entry& rhs)
{
return sort_on_size(lhs, rhs);
}

bool sort_on_sizes_descending(const Entry& lhs, const Entry& rhs)
{
return !sort_on_size(lhs, rhs);
}

bool sort_on_name(const Entry& lhs, const Entry& rhs)
{
if(lhs.m_type == TYPE_FOLDER && rhs.m_type == TYPE_FILE)
{
return true;
}

if(lhs.m_type == TYPE_FILE && rhs.m_type == TYPE_FOLDER)
{
return false;
}

std::string s1(lhs.m_name);
std::string s2(rhs.m_name);

std::transform(s1.begin(), s1.end(), s1.begin(), tolower);
std::transform(s2.begin(), s2.end(), s2.begin(), tolower);

return strcmp(s1.c_str(), s2.c_str()) < 0;
}

bool sort_on_size(const Entry& lhs, const Entry& rhs)
{
return lhs.m_file_size < rhs.m_file_size;
}

The *_ascending/descending()-functions are called by std::stable_sort
depending on if I sort on names or sizes (settings folders to size -1) and
depending on if I sort in descending order or in ascending order. It seems
to work as it should...looks okay to you too?

/ WP

Actually no, in fact my code wasn't too good either.

The killer is equal elements (it wasn't too clear from your original code
that they existed). The problem is that sort_on_size is doing a less than
comparison, so this

bool sort_on_sizes_descending(const Entry& lhs, const Entry& rhs)
{
return !sort_on_size(lhs, rhs);
}

is doing not less than, i.e. greater than or equal. That is not a suitable
predicate because it could be that x >= y and y >= x (i.e. when x equals y).
That will confuse the sorting algorithm which will be expecting this never
to be true (because its expecting the predicate to behave like a less than
comparison and obviously it can never be the case that x < y and y < x).

The right way to code the above (and the way I should have posted
originally) is

bool sort_on_sizes_descending(const Entry& lhs, const Entry& rhs)
{
return sort_on_size(rhs, lhs);
}

john

 

[John Harrison]

The right way to code the above (and the way I should have posted
originally) is

bool sort_on_sizes_descending(const Entry& lhs, const Entry& rhs)
{
return sort_on_size(rhs, lhs);
}

Obviously you should make a similar change to sort_on_names_descending even
though there equal elements cannot exist. It just better style to do it that
way.

john

 

[William Payne]

Obviously you should make a similar change to sort_on_names_descending even
though there equal elements cannot exist. It just better style to do it that
way.

john

Thanks, John, I have changed my code accordingly. Names cannot be equal
(that holds true even if they are of different types), but sizes can be
equal. I should have posted that information from the beginning.

/ WP

 

[tom_usenet]

So if I understand you do

std::stable_sort(entries.begin(), entries.end(), sort_on_name);

for ascending order and it works. What do you do for descending order (which
doesn't work)? Since that is where your problem lies it would have helped to
post that code. I would do this

bool reverse_sort_on_name(const Entry& lhs, const Entry& rhs)
{
return !sort_on_name(lhs, rhs);
}

std::sort(entries.begin(), entries.end(), reverse_sort_on_name);

That won't work; reverse_sort_on_name isn't a strict weak ordering the
way you've written it (it's >= rather than the required >). You want:

bool reverse_sort_on_name(const Entry& lhs, const Entry& rhs)
{
return sort_on_name(rhs, lhs);
}

Tom