Making a cpp sorted tuple

Question

Here's the code for std::make_tuple in the standard library.

template<typename... _Elements>
    inline tuple<typename __decay_and_strip<_Elements>::__type...>
    make_tuple(_Elements&&... __args)
    {
    typedef tuple<typename __decay_and_strip<_Elements>::__type...>
    __result_type;
    return __result_type(std::forward<_Elements>(__args)...);
    }

What I would like to do, is to sort __args before creating the tuple, presumably with std::sort(..., Compare comp) where the user passes in an appropriate comparator that can be used to sort whatever type things end up in __args.

However, I'm relatively new to cpp, I don't understand half of the code in this function, and the std::sort needs an argument for the end of __args, and I'm not sure how to derive that.

Also please explain the typename __decay_and_strip<_Elements>::__type... and _Elements&&... bits...

EDIT Since for arbitrary type combinations the return type would then be unknown at compile time, the generic case seems to be not possible. Supposing all the same type, then, and we replace ..._Elements with T, I'm still unsure how to get the ".end()" of __args for use in std::sort

You wont be able to use `std::sort`, because in order to construct your tuple the order of the arguments needs to be known at compile time. `std::sort` is not `constexpr` and therefore will only work at runtime. — 0x5453, Sep 01 '17 at 17:43
"What I would like to do" I think you need to better understand why you want it and how it could work in theory before trying to implement it. — Slava, Sep 01 '17 at 17:45
This can be done if the tuple elements all have the same type -- do they? — cdhowie, Sep 01 '17 at 17:45
In my use case, they happen to, and also there will be exactly two. However, in the interest of learning how to make fancy generalizations in cpp, I wanted to try to do this in the most general case possible... — Him, Sep 01 '17 at 17:47
I was trying to overcome the "same type" problem by passing in a custom `Compare`. — Him, Sep 01 '17 at 17:49
First try to implement a generic comparator function that would compare 2 arguments of different types, then maybe you would get rid of this idea. — Slava, Sep 01 '17 at 17:50
The generic comparator isn't necessary for this. The comparator will be for a specific tuple case, and will be passed in. — Him, Sep 01 '17 at 17:51
It is necessary indeed. Let's say you have tuple of `int`, `char` and `std::string`. You either need 6 different comparator functions or generic one. For more types variants would grow exponentially. Do you know how `std::sort` uses comparator? — Slava, Sep 01 '17 at 17:54
Also, looking at that code, does the make_tuple result end up on the stack, and is that bad? — Him, Sep 01 '17 at 18:03
You want to write a generic function that returns tuple, then you have to handle cases like this. And bigger question, what are you going to sort, runtime values of arguments? Then it is not possible in principle, as return type is generated at compile time. — Slava, Sep 01 '17 at 18:03
ahhhhh, because when it get's sorted the type signature changes. That makes sense. — Him, Sep 01 '17 at 18:05
As for explanations of __decay and other stuff, believe me, you do not want to deal with this (I mean write something like that or change it) when you are beginer. Unfortunately meta programming is advanced topic in C++ — Slava, Sep 01 '17 at 18:09
@Slava, I'm a beginner at cpp, not at programming generally, so the only thing for me to learn that isn't just syntax is the "meta-programming". — Him, Sep 01 '17 at 18:11
For tuple of the same type you can read this https://stackoverflow.com/questions/10604794/convert-stdtuple-to-stdarray-c11 - convert yout tuple to array, sort and then covert it back. — Slava, Sep 01 '17 at 18:12
You need to be advanced in C++, not in general programming to write meta programming code here. That's my opinion. And according to the way you trying to do things with tuple I am not wrong. — Slava, Sep 01 '17 at 18:14
So one cannot write meta programming cpp unless one is an advanced writer of cpp meta programming, but then, surely, one cannot be an advanced writer of cpp meta programming without having written any meta programming in cpp. Therefore, there exist no cpp meta programming writers. — Him, Sep 01 '17 at 18:23

cdhowie · Accepted Answer · 2017-09-02T19:12:37.337

This can be done if the tuple type arguments are homogeneous. (We can't sort non-homogeneous types because that would require rearrangement of the types themselves, and that's not something you can do at compile time.¹)

Assuming homogeneous types, the solution basically boils down to this:

Throw the arguments into an array.
Sort the array.
Make a tuple from the array contents.

This isn't too hard. First we need the indices trick to index our array (for step 3 -- you can use std::index_sequence instead if you have C++14):

template <std::size_t... Is>
struct indices {};

template <std::size_t N, std::size_t... Is>
struct build_indices
  : build_indices<N-1, N-1, Is...> {};

template <std::size_t... Is>
struct build_indices<0, Is...> : indices<Is...> {};

Then we need a way to peel off the first type from the parameter pack to declare our array (for step 1). As a bonus, we'll have it check to make sure all the types are the same:

template <typename...>
struct pack_type;

template <typename Head>
struct pack_type<Head>
{
    using type = Head;
};

// Will fail deduction on a non-homogeneous pack.
template <typename Head, typename... Tail>
struct pack_type<Head, Head, Tail...> : pack_type<Head, Tail...> {};

Finally, our sorter implementation with a helper to build the indices pack:

template <std::size_t... I, typename Comparer, typename... Ts>
std::tuple<Ts...> make_sorted_tuple_impl(indices<I...>, Comparer const &c, Ts && ...args)
{
    typename pack_type<Ts...>::type values[sizeof...(Ts)] = { std::forward<Ts>(args)... };

    std::sort(std::begin(values), std::end(values), c);

    return std::make_tuple(std::forward<Ts>(values[I])...);
}

// Special case to handle empty tuples.
template <typename Comparer>
std::tuple<> make_sorted_tuple_impl(indices<>, Comparer const &)
{
    return std::tuple<>();
}

template <typename Comparer, typename... Ts>
std::tuple<Ts...> make_sorted_tuple(Comparer const &c, Ts && ...args)
{
    return make_sorted_tuple_impl(build_indices<sizeof...(Ts)>(), c, std::forward<Ts>(args)...);
}

See it run.

Also please explain the typename __decay_and_strip<_Elements>::__type... and _Elements&&... bits...

I'm not going to explain the first because identifiers containing __ are reserved by the C++ implementation, so this __decay_and_strip is an implementation detail specific to this particular C++ implementation.

_Elements&&... is a pack of rvalue references. This allows the arguments to be perfectly forwarded to the std::tuple constructor.

¹ I lied. You can do it if the values and the compare function are constexpr, but the code to pull it off will be huge and not worth the time to write.

You may look at [`std::index_sequence`](http://en.cppreference.com/w/cpp/utility/integer_sequence) to replace your hand made `Indices`. — Jarod42, Sep 02 '17 at 01:12
@Jarod42 Added that alternative into my answer. I like keeping my answers applicable to C++11, pointing out differences with C++14/17. — cdhowie, Sep 02 '17 at 19:13

Making a cpp sorted tuple

1 Answers1

Linked