CODEWITHSUNDEEP
c++
Him
Him

Reputation: 5549

Making a cpp sorted tuple

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

Upvotes: 8

Views: 1780

Answers (1)

cdhowie
cdhowie

Reputation: 169518

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.1)

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

  1. Throw the arguments into an array.
  2. Sort the array.
  3. 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.

1 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.

Upvotes: 10

Related Questions