Generate a new integer_sequence by removing duplicates

user_1877331 0
Viewed 314

I implemented a compile time check to check if something is sorted using the code given below:

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

The above code works. I am planning to create a two additional meta function with these sorted checks which would generate new sequence without duplicates

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

how to remove duplicates from integer sequence using templates at compile time. Also is it possible to remove duplicates while we are performing the sort check, in this case I am fine if we stop removing duplicates as soon as templates detect that sequence is not sorted.

// 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)

I am unsure how to go by generating new std::integer_sequence on the fly.

c++20 c++17 sfinae c++
3 Answers

Since all std algorithm are now constexpr in C++20, we can use it to do compile-time programming in the nature way (just like @cigien say):

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

Also is it possible to remove duplicates while we are performing the sort check, in this case I am fine if we stop removing duplicates as soon as templates detect that sequence is not sorted.

Yes, it's possible.

Maybe can be done a little simpler, but... using and abusing template specialization...

Given an helper class as the following

// csardh: check sort and remove duplicates helper
template <typename T, typename>
struct csardh
 { using type = T; };

template <typename T, T ... ordered, T v0, T v1, T ... vs>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0, v1, vs...>>
   : public std::conditional_t<
        (v0 < v1),
        csardh<std::integer_sequence<T, ordered..., v0>,
               std::integer_sequence<T, v1, vs...>>,
        csardh<std::integer_sequence<T, ordered..., v0, v1, vs...>, void>>
 { };

template <typename T, T ... ordered, T v0, T ... vs>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0, v0, vs...>>
   : public csardh<std::integer_sequence<T, ordered...>,
                   std::integer_sequence<T, v0, vs...>>
 { };

template <typename T, T ... ordered, T v0>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0>>
   : public csardh<std::integer_sequence<T, ordered..., v0>, void>
 { };

the main class become

// csard: check sort and remove duplicates
template <typename>
struct csard;

template <typename T, T... vals>
struct csard<std::integer_sequence<T, vals...>>
   : public csardh<std::integer_sequence<T>,
                   std::integer_sequence<T, vals...>>
 { };

A using can be useful to simplify the use

template <typename T>
using csard_t = typename csard<T>::type;

The following is a full compiling example (C++14 is enough)

#include <utility>
#include <type_traits>

// csardh: check sort and remove duplicates helper
template <typename T, typename>
struct csardh
 { using type = T; };

template <typename T, T ... ordered, T v0, T v1, T ... vs>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0, v1, vs...>>
   : public std::conditional_t<
        (v0 < v1),
        csardh<std::integer_sequence<T, ordered..., v0>,
               std::integer_sequence<T, v1, vs...>>,
        csardh<std::integer_sequence<T, ordered..., v0, v1, vs...>, void>>
 { };

template <typename T, T ... ordered, T v0, T ... vs>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0, v0, vs...>>
   : public csardh<std::integer_sequence<T, ordered...>,
                   std::integer_sequence<T, v0, vs...>>
 { };

template <typename T, T ... ordered, T v0>
struct csardh<std::integer_sequence<T, ordered...>,
              std::integer_sequence<T, v0>>
   : public csardh<std::integer_sequence<T, ordered..., v0>, void>
 { };

// csard: check sort and remove duplicates
template <typename>
struct csard;

template <typename T, T... vals>
struct csard<std::integer_sequence<T, vals...>>
   : public csardh<std::integer_sequence<T>,
                   std::integer_sequence<T, vals...>>
 { };

template <typename T>
using csard_t = typename csard<T>::type;

int main()
 {
   using T0 = std::integer_sequence<int,4,4,4,5,5,3,2,2,1>;
   using T1 = csard_t<T0>;
   using T2 = std::integer_sequence<int,4,5,3,2,2,1>;

   static_assert( std::is_same<T1, T2>::value, "!" );

   using U0 = std::integer_sequence<int,1,2,3,4>;
   using U1 = csard_t<U0>;
   using U2 = U0;

   static_assert( std::is_same<U1, U2>::value, "!" );

   using V0 = std::integer_sequence<int,1,2,2,3,4>;
   using V1 = csard_t<V0>;
   using V2 = U2;

   static_assert( std::is_same<V1, V2>::value, "!" );
 }
user_60226560

Let's do this with Boost.Mp11. There, the "integer sequence" concept is a little different, we deal with lists of types. mp_list_c<int, 1, 2> is the type mp_list<mp_int<1>, mp_int<2>>. This makes a lot of metaprogramming much easier. Everything here is a one-liner.

First, is_sorted. One algorithm that's currently missing from Mp11 (shocker) is the ability to do zip_with - that is, take a list and zip that list with itself offset by one:

template <typename L, template <typename...> class P>
using zip_with = mp_transform<P, mp_pop_back<L>, mp_pop_front<L>>;

Now, is_sorted is basically: take that list and check if every pair has the first element less than the second:

template <typename L>
using is_sorted = mp_rename<zip_with<L, mp_less>, mp_all>;

Removing duplicates? That's something there's already an algorithm for: mp_unique.

Putting it altogether:

using mod_seq = mp_if_c<is_sorted<L>::value, mp_unique<L>, L>;

There's no conditional operator for types, you need something like mp_if (or std::conditional_t).

user_20690640
Related