# efficient sorting

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

## 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 on other sites
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 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 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 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 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);    }};

1. 1
Rutin
27
2. 2
3. 3
4. 4
5. 5

• 11
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009399
• ### Who's Online (See full list)

There are no registered users currently online

×