Is there any way to sort a collection of pointers at compile-time?

Question

I have this function named c_sort() that allows me to sort an array at compile-time (based on this answer):

template<typename Array>
constexpr void c_sort_impl(Array& array_) noexcept {
    using size_type = typename Array::size_type;
    size_type gap = array_.size();
    bool swapped = false;
    while ((gap > size_type{ 1 }) or swapped) {
        if (gap > size_type{ 1 }) {
            gap = static_cast<size_type> (gap / 1.247330950103979);
        }
        swapped = false;
        for (size_type i = size_type{ 0 }; gap + i < static_cast<size_type> (array_.size()); ++i) {
            if (array_[i] > array_[i + gap]) {
                auto swap = array_[i];
                array_[i] = array_[i + gap];
                array_[i + gap] = swap;
                swapped = true;
            }
        }
    }
}

template<typename Array>
constexpr Array c_sort(Array array_) noexcept {
    auto sorted = array_;
    c_sort_impl(sorted);
    return sorted;
}

This works as intended, except when I try to sort an array of function pointers in a constant expression. The problem is the line if (array_[i] > array_[i + gap]). Pointers apparently can't be compared like this at compile-time. std::greater doesn't seem to work either, and I can't cast the pointers to std::uint_ptr_t because reinterpret_cast isn't allowed in constexpr functions.

Is there any way around this? Could a collection of pointers ever be sorted at compile-time?

@KarlKnechtel They're function pointers. They're created using a little trick to create ids for types. Like so: `template void type_id() {}`. Every time you need an id for a type you take the address of the the function type_id — JensB, Jan 07 '22 at 00:45
Okay, so the goal is to create, at compile time, an array of pointers to functions, which are sorted... by value? As in, according to the order in memory in which the pointed-at functions will be placed? I don't think those locations are determined until link time. — Karl Knechtel, Jan 07 '22 at 00:47
It doesn't matter what the pointers are pointing to. You won't know what those pointer values are until runtime, when the OS/allocator/runtime/whatever actually instantiates those entities in memory. Only at that point do you have instantiations that have memory addresses, and thus pointers to them make sense. — fbrereto, Jan 07 '22 at 00:49
@KarlKnechtel Yeah, that would be the goal. The reason I need them sorted is so that I can compare different arrays of them that haven't necessarily been given them in the same order. So it isn't possible? — JensB, Jan 07 '22 at 00:49
Why do you need to handle sorting function pointers at compile time? — Kevin, Jan 07 '22 at 00:50
"The reason I need them sorted is so that I can compare different arrays of them that haven't necessarily been given them in the same order." Do you need to do the comparison at compile time? Or are you just looking to optimize the runtime comparison by avoiding a runtime sort? In the latter case, why not just use `std::set` instead of an array? (If the order doesn't matter, then surely it doesn't make sense to have duplicates either?) — Karl Knechtel, Jan 07 '22 at 00:51
@KarlKnechtel No, the comparisons will be done at run time. Correct, I want to avoid the runtime sort. Hm, not too familiar with `std::set`. How would it help me here? — JensB, Jan 07 '22 at 00:55
@KarlKnechtel The function pointers are supposed to be representatives for arbitrary types, see his previous question. — user17732522, Jan 07 '22 at 00:56
@JensB I just want to note that you can still implement comparison of unordered arrays without sorting. Equality-testing is allowed, it will just have θ(n^2) complexity in the number of elements. — user17732522, Jan 07 '22 at 00:56
"not too familiar with std::set. How would it help me here?" Simple; `std::set` internally maintains sorted order (and removes duplicates), using the runtime value, and then you can directly and efficiently compare two instances with `==`. (`std::unordered_set` also exists and has a different internal structure, but also offers efficient construction and comparison.) — Karl Knechtel, Jan 07 '22 at 01:01

user17732522 · Answer 1 · 2022-01-07T01:16:46.050

As we discussed in your other question, the built-in relational operators produce unspecified results when comparing function pointers, except when comparing for equality.

In constant expressions, unspecified results from built-in relational operators are specifically not permitted.

The only alternative to this is comparison via std::less (and friends) which are specified to always produce a total order of pointers, even if the built-in operators don't.

In my naive reading of the standard I would have expected that they should then also work without the issue of unspecified values in constant expressions.

But as this question shows, this doesn't seem to be so clear and compilers / standard libraries don't seem to currently support this use. I assume the issue is that it would require significant work to implement the required total order without relying on the actual numeric addresses of functions (which in practice compilers will not know during compilation).

There is no other way to compare function pointers for ordering in a constant expression, at least not if the set of pointers is not from the start bounded, in which case you could e.g. map each one an integer value.

(There is also stateful metaprogramming with friend injections, which could in theory provide an ordering for an unbounded set of pointers, but only consistent in a single translation unit. This is however generally considered an unintended loophole in the standard that should be closed in the future, see this question.)

Thanks for the help! I just wanted to make sure that there wasn't some way around this before I changed my design — JensB, Jan 07 '22 at 00:50
@JensB I have updated my answer, but I don't think either point I added will be of help to you. — user17732522, Jan 07 '22 at 01:17

Is there any way to sort a collection of pointers at compile-time?

1 Answers1