I stumbled across a situation where a library sorts a container (e.g. std::vector<T>
) with a user-provided comparison object. For one particular case, the user actually doesn't want to sort the container, but the sorting happens unconditionally.
So, to try to avoid this situation, I thought to try using a comparison object that sorts based on element address. Equivalently, we have:
std::vector nums{1, 5, 4};
auto cmp = [](auto& a, auto& b) { return &a < &b; };
std::sort(nums.begin(), nums.end(), cmp);
This "works" because std::vector<T>
elements are stored in (contiguous) memory locations in the same order as the elements in the vector. The end result is that the nums
vector appears to have been left untouched even after sorting.
However, once I replace std::vector<T>
with std::array<T, N>
, I get a segmentation violation (see https://gcc.godbolt.org/z/9srehdbhG).
My first thought is that I'm violating the type requirements as listed at https://en.cppreference.com/w/cpp/algorithm/sort:
RandomIt
must meet the requirements of ValueSwappable and LegacyRandomAccessIterator.- The type of dereferenced
RandomIt
must meet the requirements of MoveAssignable and MoveConstructible.Compare
must meet the requirements of Compare.
My assumption was that the addresses of the elements would remain stable throughout the sort - this is almost certainly wrong.
So, which requirements/preconditions of std::sort()
am I violating?
array
is a local variable, hmm. An odd optimization?cmp
that will get the job done:auto cmp = [](auto&&, auto&&) { return false; };