c++c++20std-rangespartial-sort

What is a concrete use case of std::ranges::partial_sort_copy with *different* projections?


I root caused a problem in my code to mismatched projections in std::ranges::partial_sort_copy. After reading cppreference, I couldn't think of a legitimate situation where proj1 & proj2 needed to be different.

What's the motivation for this algorithm providing two different projections?


Solution

  • You need it when there is a mismatch between the type of the input range, and the type of the output range. Consider the following example:

    #include <string>
    #include <ranges>
    #include <algorithm>
    #include <iostream>
    
    int main() {
        std::string names[] = {
            "alpha",
            "beta",
            "tau",
            "pi",
            "omega"
        };
        std::string_view shortest_three[3];
    
        std::ranges::partial_sort_copy(names, shortest_three,
                                       {},                         // std::ranges::less 
                                       &std::string::length,       // proj1
                                       &std::string_view::length); // proj2
        // note: It might not be allowed to take the address of
        //       member functions in std::string/std::string_view.
        //       (unspecified behavior, see [namespace.std]/6)
        //       To be on the safe side, we would have to wrap access to length()
        //       in a lambda expression.
    
        for (auto view : shortest_three) {
            std::cout << view << '\n';
        }
    }
    

    This outputs:

    pi
    tau
    beta
    

    In this example, it would be wasteful if the destination range contained std::string objects, because we could just as well store the shortest three strings as a const char* or std::string_view. As a result, there are two different projections applied here.

    Technically you could always create a single projection that covers both cases:

    auto proj = []<typename T>(const T& x) {
        // note: in this specific case, we don't need this if-statement,
        //       because the name of the member function is the exact same for
        //       both types. However, this may not always be the case, e.g.
        //       we need .length() for one type and .size() for another.
        if constexpr (std::is_same_v<T, std::string>) {
            return x.length();
        }
        else {
            return x.length();
        }
    };
    

    However, providing two separate projections is often more concise.