c++ - 通过删除重复项生成新的 integer_sequence

Question

我使用下面给出的代码实现了编译时检查以检查是否对某些内容进行了排序:

template<typename IntegerSequence>
struct is_sorted {
    static constexpr bool value = true;
};

template<typename Integer, Integer Head, Integer Next, Integer... Tail>
struct is_sorted<std::integer_sequence<Integer, Head, Next, Tail...>> {
    static constexpr bool value = Head <= Next && is_sorted<std::integer_sequence<Integer, Next, Tail...>>::value;
};

上面的代码有效。我计划使用这些排序检查创建两个额外的元函数，这将生成没有重复的新序列

using in_seq = std::integer_sequence<int, 1,2,3,4>;

using mod_seq = is_sorted<in_seq>::value ? remove_duplicates<in_seq>::uniq_seq : in_seq;
// Examples
// in_seq = 1,2,3,4 -> mod_seq = 1,2,3,4
// in_seq = 1,2,2,3,4 -> mod_seq = 1,2,3,4

如何在编译时使用模板从整数序列中删除重复项。也可以在我们执行排序检查时删除重复项，在这种情况下，如果我们在模板检测到序列未排序时立即停止删除重复项，我会很好。

// partial sort example 4,4,4,5,5,3,2,2,1 -> 4,5,3,2,2,1 (not sure if this is possible, but just curious)

我不确定如何动态生成新的 std::integer_sequence。

Answer 1

由于所有 std 算法现在在 C++20 中都是constexpr，我们可以使用它以自然方式进行编译时编程(就像@cigien说):

template <typename T, T... Ints>
constexpr auto unique_until_nonsorted(std::integer_sequence<T, Ints...>) {
  // constexpr structured bindings are not allow :(
  constexpr auto pair = [] {
    std::array<T, sizeof...(Ints)> arr{Ints...};
    // get last iterator of unique
    auto sorted_end = std::is_sorted_until(arr.begin(), arr.end());
    // unique until last iterator
    auto unique_end = std::unique(arr.begin(), sorted_end);
    // copy nonsorted elements to last iterator
    auto copy_end = std::copy(sorted_end, arr.end(), unique_end);
    // get final arr size
    auto size = std::distance(arr.begin(), copy_end);
    return std::pair{arr, size};
  }();
  constexpr auto arr  = pair.first;
  constexpr auto size = pair.second;
  // using template lambda to expand pack
  return [&arr]<std::size_t... Is>(std::index_sequence<Is...>) {
    return std::integer_sequence<T, arr[Is]...>{};
  }(std::make_index_sequence<size>{});
}    

Works for GCC and Clang.

template <typename X, X... Xs, typename Y, Y... Ys>
constexpr bool operator==(std::integer_sequence<X, Xs...>,
                          std::integer_sequence<Y, Ys...>) noexcept {
  return ((Xs == Ys) && ...);
}

static_assert(unique_until_nonsorted(std::index_sequence<4,4,4,5,5,3,2,2,1>{}) ==
                                     std::index_sequence<4,5,3,2,2,1>{});
static_assert(unique_until_nonsorted(std::index_sequence<1,2,3,4>{}) == 
                                     std::index_sequence<1,2,3,4>{});
static_assert(unique_until_nonsorted(std::index_sequence<1,2,2,3,4>{}) == 
                                     std::index_sequence<1,2,3,4>{});
static_assert(unique_until_nonsorted(std::index_sequence<2,2,2,2,4,1,1>{}) == 
                                     std::index_sequence<2,4,1,1>{});
static_assert(unique_until_nonsorted(std::index_sequence<1,1,1,2,3,2,2>{}) == 
                                     std::index_sequence<1,2,3,2,2>{});
// corner case
static_assert(unique_until_nonsorted(std::index_sequence<>{}) == 
                                     std::index_sequence<>{});