By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
458,145 Members | 1,600 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 458,145 IT Pros & Developers. It's quick & easy.

std::stable_sort with predicate woes

P: n/a
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
Jul 22 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a


William Payne wrote:
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.

--
http://lakeweb.net
http://ReserveAnalyst.com
No EXTRA stuff for email.

Jul 22 '05 #2

P: n/a

"William Payne" <mi*******************@student.liu.se> wrote in message
news:c6**********@news.island.liu.se...
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
Jul 22 '05 #3

P: n/a
---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?
Jul 22 '05 #4

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:c6************@ID-196037.news.uni-berlin.de...

"William Payne" <mi*******************@student.liu.se> wrote in message
news:c6**********@news.island.liu.se...
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


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
Jul 22 '05 #5

P: n/a

"William Payne" <mi*******************@student.liu.se> wrote in message
news:c6**********@news.island.liu.se...

"John Harrison" <jo*************@hotmail.com> wrote in message
news:c6************@ID-196037.news.uni-berlin.de...

"William Payne" <mi*******************@student.liu.se> wrote in message
news:c6**********@news.island.liu.se...
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


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
Jul 22 '05 #6

P: n/a
>
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
Jul 22 '05 #7

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:c6************@ID-196037.news.uni-berlin.de...

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


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
Jul 22 '05 #8

P: n/a
On Wed, 21 Apr 2004 06:59:31 +0100, "John Harrison"
<jo*************@hotmail.com> wrote:
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
--
C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Jul 22 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.