efficient sorting
Author
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.
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.
std::vector is a good container for this. Then use std::sort
http://www.sgi.com/tech/stl/sort.html
http://www.codeproject.com/KB/stl/stdsort.aspx
-me
http://www.sgi.com/tech/stl/sort.html
http://www.codeproject.com/KB/stl/stdsort.aspx
-me
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::sortYou 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.
Quote:Original post by samothThat 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.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::sortYou 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.
Certainly stable_sort's main usage is when you must not reorder items that are considered equivalent though.
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.
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.
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:
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); }};This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
