如何使用模板创建排序映射整数索引

Question

我有数据结构：

template <int...I> struct index {};

template <typename...T> struct data {};

template <int I, int J> struct X
{
   static constexpr int i = I;
   static constexpr int j = J;
};

typedef data< X<0,4>, X<1,2>, X<2,1>, X<1,6>, X<1,3> > data_t;

其中 data 不包含重复且索引 J 很小，在 0-31 范围内。

我想创建一个静态索引，其中包含索引 I 等于某个给定值（例如 I=1）的所有 X 在 data 中的位置，按索引 J 排序.就是我觉得难的"sorting"位

例如，我想实现一个 class build_index 这样：

typedef build_index<1,data>::type_t index_t;

生成相同的内容：

typedef index<1, 4, 3> index_t;

反映了按J排序的元素X(1,J)在data中的位置： X(1,2) 在数据(1), X(1,3) 在数据(4), X(1,6) 在数据(3)

我不想使用 STL，因为它不适用于 gcc-avr，尽管我可以移植选定的片段。

Answer 1

当您在 C++ 模板编程中遇到复杂的问题时，尝试将其分解为几个较小的步骤（就像处理大多数编程问题一样）会很有帮助。这是一个可能的路径：

Select 匹配所选 I 的 X 并将它们存储在新的数据类型中，用位置替换 I（为此使用递归）
把selected_data中的X按J排序。我觉得写起来有点烦。也许你应该为此创建一个单独的问题。
从排序和选择的X中提取位置

这是相应的代码。我正在使用 std::conditional，但当然很容易替换。我在测试中使用 std::is_same，你当然不需要它（否则实现起来很简单）。

你的东西 + 实用程序 header std::conditional 和 std::is_same

#include <utility>

template <int... I>
struct index
{
};

template <typename... T>
struct data
{
};

template <int I, int J>
struct X
{
  static constexpr int i = I;
  static constexpr int j = J;
};

typedef data<X<0, 4>, X<1, 2>, X<2, 1>, X<1, 6>, X<1, 3>> data_t;

提取与我们要查找的I相匹配的X并将i替换为位置。

template <int Pos, int I, typename Extracted, typename Rest>
struct ExtractImpl;

template <int Pos, int I, typename... ExtractedX>
struct ExtractImpl<Pos, I, data<ExtractedX...>, data<>>
{
  using type = data<ExtractedX...>;
};

template <int Pos, int I, typename... ExtractedX, typename T, typename... Rest>
struct ExtractImpl<Pos, I, data<ExtractedX...>, data<T, Rest...>>
{
  using type = typename std::conditional<
      (T::i == I),
      typename ExtractImpl<Pos + 1,
                           I,
                           data<ExtractedX..., X<Pos, T::j>>,
                           data<Rest...>>::type,
      typename ExtractImpl<Pos + 1, I, data<ExtractedX...>, data<Rest...>>::
          type>::type;
};

template <int I, typename Data>
struct Extract
{
  using type = typename ExtractImpl<0, I, data<>, Data>::type;
};

using extracted = typename Extract<1, data_t>::type;
static_assert(std::is_same<extracted, data<X<1, 2>, X<3, 6>, X<4, 3>>>::value, "");

按 J 排序。这是通过将元素递增地插入排序列表来完成的。可能有更优雅的方法来做到这一点。

template <typename T, typename LessList, typename RestList>
struct insert_impl;

template <typename T, typename... Lesser>
struct insert_impl<T, data<Lesser...>, data<>>
{
  using type = data<Lesser..., T>;
};

template <typename T, typename... Lesser, typename Next, typename... Rest>
struct insert_impl<T, data<Lesser...>, data<Next, Rest...>>
{
  using type = typename std::conditional<
      (T::j < Next::j),
      data<Lesser..., T, Next, Rest...>,
      typename insert_impl<T, data<Lesser..., Next>, data<Rest...>>::type>::
      type;
};

template <typename T, typename SortedList>
struct insert
{
  using type = typename insert_impl<T, data<>, SortedList>::type;
};

template <typename SortedList, typename UnsortedList>
struct SortImpl;

template <typename SortedList>
struct SortImpl<SortedList, data<>>
{
  using type = SortedList;
};

template <typename SortedList, typename T, typename... UnsortedX>
struct SortImpl<SortedList, data<T, UnsortedX...>>
{
  using type = typename SortImpl<typename insert<T, SortedList>::type,
                                 data<UnsortedX...>>::type;
};

template <typename UnsortedList>
struct Sort
{
  using type = typename SortImpl<data<>, UnsortedList>::type;
};

using sorted = typename Sort<extracted>::type;
static_assert(std::is_same<sorted, data<X<1, 2>, X<4, 3>, X<3, 6>>>::value, "");

最后，提取您要查找的索引：

template <typename List>
struct Indexes;

template <typename... Data>
struct Indexes<data<Data...>>
{
  using type = index<Data::i...>;
};

using result = typename Indexes<sorted>::type;
static_assert(std::is_same<result, index<1, 4, 3>>::value, "");

警告：虽然我没有发现代码中有任何问题，但我没有在您的示例之外对其进行测试...

Answer 2

我将分享我解决这个问题的方法，我认为它很巧妙。我用的是C++11std::conditional和C++14std::integer_sequence和std::make_integer_sequence，所有这些你都可以在网上找到实现。

让我们从您拥有的数据结构开始。

template <int... Is> struct index {};
template <typename... Ts> struct list {};
template <int L, int R> struct pair {};

我们将使用元函数 concat，它连接 N 类型列表。我们使用它来过滤列表，方法是在谓词 returns true 时返回 list<T>，否则返回 list<>。

例如，要从list<1, 3, 2, 4, 2>中过滤偶数，我们可以对每个I执行std::conditional_t<I % 2 == 0, list<I>, list<>>得到concat_t<list<>, list<>, list<2>, list<4>, list<2>> = list<2, 4, 2>。

template <typename... Ts> struct concat;

template <> struct concat<> { using type = list<>; }

template <typename... Ts>
struct concat<list<Ts...>> { using type = list<Ts...>; };

template <typename... Ts, typename... Us>
struct concat<list<Ts...>, list<Us...>> { using type = list<Ts..., Us...>; };

template <typename... Ts, typename... Us, typename... Tail>
struct concat<list<Ts...>, list<Us...>, Tail...>
    : concat<list<Ts..., Us...>, Tail...> {};

template <typename... Ts>
using concat_t = typename concat<Ts...>::type;

现在我们到了 build_index。我们在 [0, 32) 的已知范围内进行桶排序。我们本可以使用通用排序算法，但作弊更有趣。

template <int N, typename T> struct build_index;

// e.g., `build_index<
//            1, list<pair<0, 4>, pair<1, 2>, pair<2, 1>, pair<1, 6>, pair<1, 3>>`
template <int N, int... Ls, int... Rs>
struct build_index<N, list<pair<Ls, Rs>...>> {
  // Filter for pairs where `N == lhs`, and replace the `lhs` with the index.
  template <int... Is>
  static auto filter(std::integer_sequence<int, Is...>)
      -> concat_t<std::conditional_t<N == Ls, list<pair<Is, Rs>>, list<>>...>;

  // e.g., `list<pair<1, 2>, pair<3, 6>, pair<4, 3>>`
  using filtered =
      decltype(filter(std::make_integer_sequence<int, sizeof...(Ls)>{}));

  // `get<I>(set)` returns the `lhs` if `set` can implicitly convert to
  // `pair<lhs, I>` for some `lhs`, and nothing otherwise.
  template <typename... Ts> struct set : Ts... {};
  template <int I, int L> static list<index<L>> get(pair<L, I>);
  template <int I> static list<> get(...);

  // We invoke `get<I>` for `I` in `[0, 32)` to sort `filtered`.
  template <int... Is, typename... Ts>
  static auto sort(std::integer_sequence<int, Is...>, list<Ts...>)
      -> concat_t<decltype(get<Is>(set<Ts...>{}))...>;

  // e.g., `list<index<1>, index<4>, index<3>>`
  using sorted =
      decltype(sort(std::make_integer_sequence<int, 32>{}, filtered{}));

  // e.g., `list<1, 4, 3>`
  template <int... Is> static index<Is...> indices(list<index<Is>...>);
  using type = decltype(indices(sorted{}));
};

template <int N, typename... Ts>
using build_index_t = typename build_index<N, Ts...>::type;

我们得到：

using index_t = build_index_t<
    1, list<pair<0, 4>, pair<1, 2>, pair<2, 1>, pair<1, 6>, pair<1, 3>>>;
static_assert(std::is_same<index<1, 4, 3>, index_t>::value, "");

如何使用模板创建排序映射整数索引

How to create a sorted mapping integer index with templates

c++

sorting

metaprogramming

c++11

c++14