6

Answers here and here are pretty much what I need. However, I would like to be able to generate sequences such as:

gen_seq<5, 2> // {0, 1, 3, 4}
gen_seq<3, 0> // {1, 2}
// optional behavior that would be useful for me:
gen_seq<4, 4> // {0, 1, 2, 3}

In the examples I used gen_seq to generate a sequence from 0 to N-1 without I. This is not mandatory, I would also be fine with gen_seq where N is the length of the sequence and I the missing index or other variants.

I think most of the problem is already answered in the linked questions. However I cannot really wrap my head around how to incorporate the "leave this one out" condition for the second parameter.

Ideally, I would love to stick to c++11 features and avoid c++14. Elegant and especially readable soulutions using c++14 could also be very interesting, though.

Community
  • 1
  • 1
b.buchhold
  • 3,837
  • 2
  • 24
  • 33

3 Answers3

8

You may use the following:

#if 1 // Not in C++11 // make_index_sequence
#include <cstdint>

template <std::size_t...> struct index_sequence {};

template <std::size_t N, std::size_t... Is>
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence<0u, Is...> : index_sequence<Is...> { using type = index_sequence<Is...>; };

#endif // make_index_sequence

namespace detail
{
    template <typename Seq1, std::size_t Offset, typename Seq2> struct concat_seq;

    template <std::size_t ... Is1, std::size_t Offset, std::size_t ... Is2>
    struct concat_seq<index_sequence<Is1...>, Offset, index_sequence<Is2...>>
    {
        using type = index_sequence<Is1..., (Offset + Is2)...>;
    };
}

template <std::size_t N, std::size_t E>
using gen_seq = typename detail::concat_seq<typename make_index_sequence<E>::type, E + 1, typename make_index_sequence<(N > E) ? (N - E - 1) : 0>::type>::type;

static_assert(std::is_same<index_sequence<0, 1, 3, 4>, gen_seq<5, 2>>::value, "");
static_assert(std::is_same<index_sequence<1, 2>, gen_seq<3, 0>>::value, "");
static_assert(std::is_same<index_sequence<0, 1, 2, 3>, gen_seq<4, 4>>::value, "");

Live example

Jarod42
  • 203,559
  • 14
  • 181
  • 302
3

The simple linear method of generating integer sequences is trivially adaptable to excluding specific items, by adding a specialisations that covers the case where the item is the one being excluded:

#include <iostream>

// general case, ignores X

template <int N, int X, int... vals>
struct gen_seq : gen_seq<N - 1, X, N - 1, vals...> { };

template <int X, int... vals>
struct gen_seq<0, X, vals...> { static constexpr int values[] = { vals... }; };

// specialisations when vals has had X prepended: remove X

template <int N, int X, int... vals>
struct gen_seq<N, X, X, vals...> : gen_seq<N, X, vals...> { };

template <int... vals>
struct gen_seq<0, 0, 0, vals...> : gen_seq<0, 0, vals...> { };

template <int X, int... vals>
constexpr int gen_seq<0, X, vals...>::values[];

int main() {
  for (auto i : gen_seq<5, 2>::values) std::cout << i << std::endl; // 0 1 3 4
  for (auto i : gen_seq<3, 0>::values) std::cout << i << std::endl; // 1 2
  for (auto i : gen_seq<4, 4>::values) std::cout << i << std::endl; // 0 1 2 3
}

It may not be as efficient as other more advanced methods, but it is the most readable. Unlike your own answer and Jarod42's, this does not build a new algorithm on top of the pre-existing one, but builds a new one from scratch.

1

Always great to write your questions down.

I just figured out that I can just use the divide and conquer method and generate not from 0 to N/2 and N/2 + 1 to n but in a first step just generate from 0 to I - 1 and from I + 1 to N.

This, I can combine with the linear or also log-depth generation method. Now I feel stupid for asking but at least I'm not stuck anymore.

b.buchhold
  • 3,837
  • 2
  • 24
  • 33