Jump to content
  • Advertisement
Sign in to follow this  
AcidZombie24

efficient sorting

This topic is 3621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have no idea how to sort these structs efficiently I have many pointers to stucts (stored in a vector) and i need to sort them (it can be in a different container) based on their tags. Say i have a windows explorer like tags. filename, size, last date modified etc how do i sort it by primarly on filesize then filename in acceding or descending order? I remember being told to use an stl container but i dont remember which.

Share this post


Link to post
Share on other sites
Advertisement
std::set or std::multi_set (former for only unique elements, the latter for duplicate elements) or std::sort combined with the appropriate comparer functor.

Share this post


Link to post
Share on other sites
Quote:
how do i sort it by primarly on filesize then filename in acceding or descending order?

Quote:
std::vector is a good container for this. Then use std::sort
You should use stable_sort though, because sort is not necessarily stable (it may be, but isn't required to).
To sort first by one key and then by another, you need a "stable" sort, i.e. one that preserves the relative order of elements that compare as equal.

Share this post


Link to post
Share on other sites
Quote:
Original post by samoth
Quote:
how do i sort it by primarly on filesize then filename in acceding or descending order?

Quote:
std::vector is a good container for this. Then use std::sort
You should use stable_sort though, because sort is not necessarily stable (it may be, but isn't required to).
To sort first by one key and then by another, you need a "stable" sort, i.e. one that preserves the relative order of elements that compare as equal.
That depends on whether you call the sort routine twice, or if you simply make your comparison function compare according to the secondary sort order method whenever there is a tie. The later is faster and does not require a stable sorting function. std::pair has a nice < operator showing how to do that.
Certainly stable_sort's main usage is when you must not reorder items that are considered equivalent though.

Share this post


Link to post
Share on other sites
If the precedence of the struct's members is static, as others have pointed out, std::sort with a comparison functor is the way to go.

If you need the precedence to be dynamic at runtime, you need something like (shameless plug) this.

The latter method is much more complicated, so only use it if you really need that flexibility.

Share this post


Link to post
Share on other sites
As you may have picked up from the other posts, the essential part to this is the comparison functor. You may want two of them, for ascending and for descending sorts. You can then use one of those functors either with one of the set containers or with std::sort on a vector (or similar container).

Your functors might look like this:

// A functor to sort in ascending order by file size and then name.
struct size_name_ascending
{
bool operator()(const file_properties & a, const file_properties & b)
{
if (a.size() != b.size()) return a.size() < b.size();
return a.name() < b.name();
}
};

// A functor to sort in descending order by file size and then name.
struct size_name_descending
{
bool operator()(const file_properties & a, const file_properties & b)
{
return size_name_ascending()(b, a);
}
};

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!