Array Initialisation Compile Time - Constexpr Sequence

Question

I was reading this question on SO.

The question itself is not so interesting, but I was wondering whether it exists and how to implement a compile time solution.

Regard to the first sequence:

All numbers except the ones which can be divided by 3.

The sequence should be something like:

[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, ...]

By induction, I've found the math formula for that sequence:

 f(0) = 0;
 f(x > 0) = floor[(3x - 1) / 2];

So I've implemented a C++ constexpr function which generates the i-th number in the sequence:

#include <type_traits>

template <typename T = std::size_t>
constexpr T generate_ith_number(const std::size_t index) {
  static_assert(std::is_integral<T>::value, "T must to be an integral type");

  if (index == 0) return 0;
  return (3 * index - 1) / 2;
}

Now I'd like to generate a "compile-time array/sequence" which stores the first N-th numbers of the sequence.

The structure should be something like:

template <typename T, T... values>
struct sequence {};

template <typename T, std::size_t SIZE>
struct generate_sequence {};  // TODO: implement

Questions (more than one, but related among them):

1) How to implement that kind of integer_sequence?

2) Is it possible to build an std::array from that integer_sequence at compile time?

Vittorio Romeo · Accepted Answer · 2017-08-29 13:27:52Z

16

1) How to implement that kind of integer_sequence?

template <std::size_t... Is> 
constexpr auto make_sequence_impl(std::index_sequence<Is...>)
{
    return std::index_sequence<generate_ith_number(Is)...>{};
}

template <std::size_t N> 
constexpr auto make_sequence()
{
    return make_sequence_impl(std::make_index_sequence<N>{});
}

2) Is it possible to build an std::array from that integer_sequence at compile time?

template <std::size_t... Is>
constexpr auto make_array_from_sequence_impl(std::index_sequence<Is...>)
{
    return std::array<std::size_t, sizeof...(Is)>{Is...};
}

template <typename Seq>
constexpr auto make_array_from_sequence(Seq)
{
    return make_array_from_sequence_impl(Seq{});
}

Usage:

int main()
{
    constexpr auto arr = make_array_from_sequence(make_sequence<6>());
    static_assert(arr[0] == 0);
    static_assert(arr[1] == 1);
    static_assert(arr[2] == 2);
    static_assert(arr[3] == 4);
    static_assert(arr[4] == 5);
    static_assert(arr[5] == 7);
}

live example on wandbox.org

answered Aug 29, 2017 at 13:27

Vittorio Romeo

94.1k37 gold badges276 silver badges451 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

metal Over a year ago

With C++17 constructor deductions, std::array<std::size_t, sizeof...(Is)>{Is...}; could be simplified to std::array{Is...};.

Collectives™ on Stack Overflow

Array Initialisation Compile Time - Constexpr Sequence

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related