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
– 0x5453, Commented Sep 1, 2017 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
– Slava, Commented Sep 1, 2017 at 17:45
This can be done if the tuple elements all have the same type -- do they? — cdhowie
– cdhowie, Commented Sep 1, 2017 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
– Him, Commented Sep 1, 2017 at 17:47

cdhowie · Accepted Answer · 2017-09-02 19:12:37Z

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 to replace your hand made Indices.
@Jarod42 Added that alternative into my answer. I like keeping my answers applicable to C++11, pointing out differences with C++14/17.

Collectives™ on Stack Overflow

Making a cpp sorted tuple

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related