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?

Is there any reason not to use initializer_list here and, say, have a sorting routine like `sort({varA, varB, varC, varD})`? — templatetypedef, Jun 16 '15 at 00:34
You are not actually sorting template parameters (`T, Args...`), right? You want to actually sort `first, rest...`? @templatetypedef That will force a copy. This one doesn't have to if sprinkled correctly with forwarding references. — T.C., Jun 16 '15 at 00:34

score 5 · Accepted Answer · edited May 23 '17 at 11:51

5

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.

edited May 23 '17 at 11:51

Community

1
1

answered Jun 16 '15 at 00:47

T.C.

133,968
17
288
421

Wouldn't it be clearer to make the function accept only "Args&&..." and obtain T using a variadic type function? This would e.g. eliminate the "1 +" for "reserve" and the lone "push_back". Easy type function implementation: template struct Head { static_assert(sizeof...(Args) != 0, "No types specified for 'Head'"); }; template struct Head { using type = T; }; – Arne Vogel Jun 16 '15 at 12:24
What, no `emplace`! `push_back` could give you a needless copy. ;) – Yakk - Adam Nevraumont Jun 16 '15 at 14:29
@Yakk On a type mismatch? So be it (and it'd be a move). I don't want to allow explicit conversions. – T.C. Jun 16 '15 at 14:30
@T.C. Good point. Add a "explicit conversions will generate an error" `using no_explicit = std::tuple< decltype( R{std::declval()} )... >;`? – Yakk - Adam Nevraumont Jun 16 '15 at 14:55
@Yakk That can still be explicit, no? Just catches narrowing. – T.C. Jun 16 '15 at 14:58
1

@T.C. Not in my tests: http://coliru.stacked-crooked.com/a/d3c47f2b292a5353 (replace `good` with `evil` and you get a conversion error, it won't call the `explicit` conversion). Note I'm making a throw-away tuple type, not a tuple: the point of that line is `R{Ts}` construction, which should be non-explicit. – Yakk - Adam Nevraumont Jun 16 '15 at 15:04
@Yakk It doesn't use explicit conversion operators of `Ts`, but still uses explicit constructors of `R`. – T.C. Jun 16 '15 at 15:21
@T.C huh, yes, the difference between `R r{x};` and `R r={x};`. So we need an expression that constructs with a `R&&` or `R const&` only, but we don't want to actually call it. [How about this](http://coliru.stacked-crooked.com/a/c30eebab349d73fe)? Could be done without my helper with a `std::array` I think. – Yakk - Adam Nevraumont Jun 16 '15 at 15:30
@Yakk Doesn't `std::tuple` have an "accept everything under the sun" constructor? `array` is better, but there's still the problem that implicit and explicit conversions can both be viable and yield different results, though that's pretty pathological. – T.C. Jun 16 '15 at 15:34

Yakk - Adam Nevraumont · Answer 2 · 2015-06-16T15:34:43.340

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)

@T.C. Point. Wow, this code gets cleaner in C++14 and C++1z. C++14 lets you package the work into an auto-lambda. C++1z gives you fold expressions. — Yakk - Adam Nevraumont, Jun 16 '15 at 14:19

Oleg Andriyanov · Answer 3 · 2015-06-16T01:44:04.637

-1

This simple:

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

edited Jun 16 '15 at 01:44

answered Jun 16 '15 at 01:32

Oleg Andriyanov

5,069
1
22
36

I didn't downvote, but this will incur extra copies. – T.C. Jun 16 '15 at 01:58

C++ template sort

3 Answers3