C++模板排序

Question

我正在寻找模板代码来对模板参数进行排序，例如：

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

Args 中的所有类型实际上都是 T，但我需要使用可变参数模板，这样我就可以像这样缩小编译时间列表：

sort(varA, varB, varC, varD).

（事实上，我计划有一个 "all_different"，它将排序并删除重复项，以评估 4 个值 varA、varB、varC、varD 是否都不同）。

哪里已经写过这种东西了？

Answer 1

假设您要对函数参数进行排序，这实现起来相当简单。只需从参数中构建一个向量（或 std::list，如果出于某种原因你想使用它），然后对其进行排序。

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;
}

有关 expander 工作原理的说明，请参阅。

您可以将 "build the vector" 部分缩写为：

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

但这会导致每个元素的额外副本（并且不适用于仅移动类型），因为您无法从 std::initializer_list.

移动

Answer 2

这个简单：

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

Answer 3

一次只做一件事：

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);
}

一些元编程：（hana 风格）

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>{}... ) ) >;

现在，一个生成向量的函数。您可以为向量传递一个类型，或者让它从第一个参数推导出来，您的选择：

// 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;
}

并拼接：

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)

C++模板排序

C++ template sort

c++

templates

variadic-templates

c++11