C++ template sort

Question

I'm looking for template code to sort template parameters, something like:

template <typename T, typename ... Args>
list<T> sort(T first, Args ... rest)

All the types in Args are actually T, but I need to use variadic templates, so that I can small compile time lists like:

sort(varA, varB, varC, varD).

(In fact, I plan on having an "all_different", which would sort and remove duplicates, to asses if the 4 values varA, varB, varC, varD are all different).

Anywhere where this kind would have been already written?

Answer 1

This is fairly straightforward to implement, assuming that you want to sort the function arguments. Just build a vector (or a std::list, if for whatever reason you want to use it) out of the arguments, and sort it.

template <typename T, typename ... Args, typename T_d = std::decay_t<T>>
std::vector<T_d> sort(T&& first, Args&&... rest){
    // optionally static assert that all of decay_t<Args>... are the same as T_d

    // build the vector
    std::vector<T_d> ret;
    ret.reserve(1 + sizeof...(Args));
    ret.push_back(std::forward<T>(first));
    using expander = int[];
    (void) expander{0, (ret.push_back(std::forward<Args>(rest)), 0)...};

    // now sort it
    std::sort(ret.begin(), ret.end());
    return ret;
}

See this answer for an explanation of how expander works.

You can abbreviate the "build the vector" part into:

std::vector<T_d> ret { std::forward<T>(first), std::forward<Args>(rest)... };

but this incurs an additional copy per element (and doesn't work for move-only types) since you can't move from a std::initializer_list.

Answer 2

This simple:

template <typename T, typename... Args>
list<T> sort(const T& first, Args... args)
{
    list<T> result{first, args...};
    result.sort();
    return result;
}

Answer 3

Do one thing at a time:

template<class R>
R sort_the_range( R&& r ) {
  using std::begin; using std::end;
  std::sort( begin(r), end(r) );
  return std::forward<R>(r);
}

some metaprogramming: (hana-style)

template<class T> struct tag{using type=T;};
template<class...> struct types{using type=types;};
template<class Tag>using type_t=typename Tag::type;

template<class Default, class...Ts,
  class=typename std::enable_if<!std::is_same<void,Default>::value>::type
>
constexpr tag<Default> type_from( tag<Default>, Ts... ) { return {}; }
template<class T0, class...Ts>
constexpr tag<T0> type_from( tag<void>, tag<T0>, Ts... ) { return {}; }

template<class Default, class...Ts>
using type_from_t = type_t< decltype( type_from( tag<Default>{}, tag<Ts>{}... ) ) >;

now, a function that makes a vector. You can pass in a type for the vector, or have it deduce from the first argument, your choice:

// explicit T argument is optional:
template<class ExplicitType=void, class...Ts,
  // deduce return type:
  class R=type_from_t<ExplicitType, typename std::decay<Ts>::type...>
>
std::vector<R> make_vector( Ts&&... ts ) {
  // block explicit conversions:
  using test = decltype(std::array<R, sizeof...(Ts)>{{ std::declval<Ts>()... }});
  (void)tag<test>{}; // block warnings
  // make our vector, and size it right:
  std::vector<R> retval;
  retval.reserve( sizeof...(ts) );
  // populate the vector:
  (void)std::initializer_list<int>{0,((
    retval.emplace_back(std::forward<Ts>(ts))
  ),void(),0)...};
  return retval;
}

and stitch:

template<class T=void, class...Ts>
auto make_sorted_vector(Ts&&...ts)
->decltype( make_vector<T>(std::forward<Ts>(ts)...) )
{
  return sort_the_range(
    make_vector<T>( std::forward<Ts>(ts)... )
  );
}

live example)