I have a struct with members x,y,z and w. How do I sort efficiently first by x, then by y, by z and finally by w in C++?
相关问题
- Sorting 3 numbers without branching [closed]
- How to compile C++ code in GDB?
- Why does const allow implicit conversion of refere
- thread_local variables initialization
- What uses more memory in c++? An 2 ints or 2 funct
相关文章
- Class layout in C++: Why are members sometimes ord
- How to mock methods return object with deleted cop
- Which is the best way to multiply a large and spar
- C++ default constructor does not initialize pointe
- Given a list and a bitmask, how do I return the va
- Selecting only the first few characters in a strin
- What exactly do pointers store? (C++)
- Converting glm::lookat matrix to quaternion and ba
You can turn a struct into a
std::tuple
usingstd::tie
, and use the lexicographic comparisonstd::tuple::operator<
. Here's an example using a lambda tostd::sort
This example supplies
std:sort
with a comparison operator on-the-fly. If you always want to use lexicographic comparison, you could write a non-memberbool operator<(S const&, S const&)
that would automatically be selected bystd::sort
, or by ordered associative containers likestd::set
andstd::map
.Regarding efficiency, from an online reference:
If you have a C++11 environment, prefer
std::tie
over hand-written solutions given here. They are more error-prone and less readable.If you want to implement a lexicographical ordering, then the simplest way is to use
std::tie
to implement a less-than or greater-than comparison operator or functor, and then usestd::sort
on a collection of your structs.If there is not a natural ordering for
Foo
, it might be better to define comparison functors instead of implementing comparison operators. You can then pass these to sort:If you do not have C++11
tuple
support, you can implement this usingstd::tr1::tie
(use header<tr1/tuple>
) or usingboost::tie
from the boost.tuple library.If you roll your own comparison operator, then you can freely throw objects into
std::map
s or invokestd::sort
. This implementation's designed to be simple so you can easily verify and modify it if needed. By only usingoperator<
to compare x, y, z and w, it minimises the number of operators you may need to implement if those variables are not already comparible (e.g. if they're your own structs rather than ints, double, std::strings etc.).Sometimes types will define a comparison function that returns -1, 0 or 1 to indicate less-than, equal or greater-than, both as a way to support the implementation of
<
,<=
,==
,!=
,>=
and>
and also because sometimes doing a<
then a!=
or>
would repeat a lot of work (consider comparing long textual strings where only the last character differs). If x, y, z and w happen to be of such types and have a higher-performance compare function, you can possibly improve your overall performance with:This solution has at most 4 comparisons per element-compare and does not require construction of other objects: