deduce entire vector space at compile time

Question

Inspired by this question : c++ generate (xyz) points in range

I began to wonder whether there is a form of template code that can, from this statement:

using X = axis_limits<-10, +10>;
using Y = axis_limits<-10, +10>;
using Z = axis_limits<-10, +10>;

auto space = std::vector<point>{ generate_point_space<X, Y, Z> };

construct at compile time a vector called space that contains one point for each x, y , z where begin(X) <= x < end(X)... etc for y and z.

Order is not important.

The return type of generate_point_space<> should be std::initializer_list<int> or similarly compile-time-constructed sequence. I'm not looking to generate a sequence of calls to push_back(). That would be too easy :)

struct point would have a constructor of the form:

point::point(int x, int y, int z)

a single dimension of ints is straightforward (code below). The multi-dimensional aspect of the problem is beyond me today

#include <utility>
#include <iostream>
#include <vector>

template<int Begin, int End>
struct axis_limits
{
    static constexpr int first = Begin;
    static constexpr int last = End;
};

namespace details
{
    template<typename Int, typename, Int Begin, bool Increasing>
    struct integer_range_impl;

    template<typename Int, Int... N, Int Begin>
    struct integer_range_impl<Int, std::integer_sequence<Int, N...>, Begin, true> {
        using type = std::integer_sequence<Int, N+Begin...>;
    };

    template<typename Int, Int... N, Int Begin>
    struct integer_range_impl<Int, std::integer_sequence<Int, N...>, Begin, false> {
        using type = std::integer_sequence<Int, Begin-N...>;
    };
}

template<typename Int, Int Begin, Int End>
using integer_range = typename details::integer_range_impl<
Int,
std::make_integer_sequence<Int, (Begin<End) ? End-Begin : Begin-End>,
Begin,
(Begin<End) >::type;

template<int...Is>
std::vector<int> make_vector(std::integer_sequence<int, Is...>)
{
    return std::vector<int> { Is... };
}

template<int Begin, int End>
struct axis_range
{
    using sequence_type = integer_range<int, Begin, End>;
    static constexpr int size = sequence_type::size();
    static std::vector<int> as_vector()
    {
        return make_vector(sequence_type {});
    }
};

template< int Begin, int End >
std::vector<int> make_axis(const axis_limits<Begin, End> &)
{
    return axis_range<Begin, End>::as_vector();
}

template<class T>
void dump_vector(std::ostream& os, const std::vector<T>& v) {
    const char* sep = "{ ";
    for(const auto& i : v) {
        os << sep << i;
        sep = ", ";
    }
    os << " }";
}

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
    dump_vector(os, vec);
    return os;
}

using namespace std;

int main()
{

    using X = axis_limits<-5, +5>;
    auto space = std::vector<int>(make_axis(X{}));
    cout << space << endl;
    return 0;
}

current output:

{ -5, -4, -3, -2, -1, 0, 1, 2, 3, 4 }

what I am looking for:

{ { -10, -10, -10 }, { -10, -10, -9 } .... { 9, 9, 8 }, { 9, 9, 9 } }

Please don't add new, different questions to an existing question. — Yakk - Adam Nevraumont, May 11 '15 at 19:52

Jarod42 · Answer 1 · 2015-05-12T07:24:23.073

6

You may do something like the following:

template<int Begin, int End>
struct axis_limits
{
    static constexpr int first = Begin;
    static constexpr int last = End;
    static constexpr int range = End - Begin + 1;
};

struct point
{
    explicit point(int x, int y, int z) : x(x), y(y), z(z) {}
    int x; int y; int z;
};

namespace detail
{

    template <typename X, typename Y, typename Z, std::size_t... Is>
    std::vector<point> generate_point_space_impl(std::index_sequence<Is...>)
    {
        return {point(
            static_cast<int>(Is / (Z::range * Y::range)) % X::range + X::first,
            static_cast<int>(Is / Z::range) % Y::range + Y::first,
            static_cast<int>(Is) % Z::range + Z::first)...
            };
    }

}


template <typename X, typename Y, typename Z>
std::vector<point> generate_point_space()
{
    return detail::generate_point_space_impl<X, Y, Z>(std::make_index_sequence<X::range * Y::range * Z::range>());
}

Live demo

edited May 12 '15 at 07:24

answered May 11 '15 at 15:34

Jarod42

203,559
14
181
302

nice that worked well (with a couple of syntax tweaks) – Richard Hodges May 11 '15 at 15:50
@RichardHodges: syntax typo fixed. – Jarod42 May 11 '15 at 17:46
Just an aside, don't use C-casts like you did here (`int(...)`), it's dangerous. Use `static_cast(...)` as a replacement. http://stackoverflow.com/questions/332030/when-should-static-cast-dynamic-cast-const-cast-and-reinterpret-cast-be-used – May 11 '15 at 21:21

vsoftco · Answer 2 · 2015-05-11T16:22:03.247

2

std::vector constructors are not constexpr, so you're out of luck here. You cannot return them as constexpr from a factory function, the vector is always constructed at run-time. Perhaps you should try std::array? Something like

#include <iostream>
#include <utility>
#include <array>

template<int...Is>
constexpr auto make_array(const std::integer_sequence<int, Is...>& param)
{
    return std::array<int, sizeof...(Is)> {Is...};
}

int main()
{
    constexpr std::integer_sequence<int, 1,2,3,4> iseq{};
    constexpr auto arr = make_array(iseq);

    for(auto elem: arr)
        std::cout << elem << " ";
}

edited May 11 '15 at 16:22

answered May 11 '15 at 15:22

vsoftco

55,410
12
139
252

i was wondering whether there was something that could be done with tuple_cat and then subsequently turning the tuple into a variadic type? – Richard Hodges May 11 '15 at 15:28
Then you can create a factory function that returns a `constexpr std::array`. Frankly, I don't have an immediate solution for the latter, but I'm pretty sure it can be done. I just know for sure that `std::vector` is not the way to go. – vsoftco May 11 '15 at 15:28
@RichardHodges I tried to come up with something, it seem to work. Also, take a look [here](http://en.cppreference.com/w/cpp/utility/integer_sequence) for some tricks relating tuple<->array conversions at compile time. – vsoftco May 11 '15 at 15:45
I think this coupled with the other answer would do it. – Richard Hodges May 11 '15 at 15:52
@RichardHodges also see my answer for an `std::array`-based solution. – The Paramagnetic Croissant May 11 '15 at 15:53

score 2 · Accepted Answer · answered May 11 '15 at 21:16

Some metaprogramming helpers to work with lists of types:

template<class T>struct tag{using type=T;};
template<class Tag>using type=typename Tag::type;

template<class...>struct types{using type=types;};

template<class...Ts>
struct cat;
template<class...Ts>
using cat_t=type<cat<Ts...>>;

template<class...As, class...Bs, class...Ts>
struct cat< types<As...>, types<Bs...>, Ts... >:
  cat< types<As...,Bs...>, Ts... >
{};
template<class...Ts>
struct cat< types<Ts...> >:
  types<Ts...>
{};
template<>
struct cat<>:
  types<>
{};

A way to map between sequences of values, and sequences of types. I find types easier to work with:

template<class Seq>
struct seq_to_types;
template<class Seq>
using seq_to_types_t=type<seq_to_types<Seq>>;
template<class T, T...ts>
struct seq_to_types< std::integer_sequence<T,ts...> >:
  tag< types< std::integral_constant<T,ts>... > >
{};
template<class T, class Rhs>
struct types_to_seq:tag<Rhs>{};
template<class T, class types>
using types_to_seq_t=type<types_to_seq<T,types>>;
template<class T, T...ts>
struct types_to_seq<T, types<std::integral_constant<T, ts>...>>:
  tag<std::integer_sequence<T, ts...>>
{};
template<class T, class...Ts>
struct types_to_seq<T, types<Ts...>>:
  types< types_to_seq_t<T, Ts>... >
{};

now we can take a std::integer_sequence<int, 1,2,3> and produce types< std::integral_constant<int,1>, std::integral_constant<int,2>, std::integral_constant<int,3> > which in my opinion is far easier to work with. We can even map back.

This takes a types<Ts...> and a function on the types, and does the map:

template<template<class...>class M, class Seq>
struct mapper;
template<template<class...>class M, class Seq>
using mapper_t=type<mapper<M,Seq>>;
template<template<class...>class M, class...Ts>
struct mapper<M, types<Ts...>>:
  types<M<Ts>...>
{};

mapper_t< some_metafunction, types<blah...>> will map each blah through the some_metafunction to produce a new list of types.

Next, a way to take a type function, and bind the first argument to X:

template<template<class...>class F, class X>
struct bind_1st {
  template<class...Ts>
  using apply=F<X,Ts...>;
};

which can use do a cross product easily (together with cat_t and mapper_t):

template<class...Ts>
struct cross_product:types<types<>>{};
template<class...Ts>
using cross_product_t=type<cross_product<Ts...>>;

template<class...T0s, class...Ts>
struct cross_product<types<T0s...>, Ts...>:cat<
  mapper_t<
    bind_1st<cat_t, types<T0s>>::template apply,
    cross_product_t<Ts...>
  >...
>{};

Now we work on the next problem. We have a set of points, and we want to generate their cross product.

template<class...Seq>
struct coords;
template<class...Seq>
using coords_t=type<coords<Seq...>>;
template<class T, T...ts, class...Ts>
struct coords< std::integer_sequence<T,ts...>, Ts... >:
  types_to_seq<
    T,
    cross_product_t<
      seq_to_types_t<std::integer_sequence<T,ts...>>,
      seq_to_types_t<Ts>...
    >
  >
{};

should explode nicely.

live example.

The next step is to build your syntax.

template<class T, T t0, class Seq>
struct offset_sequence;
template<class T, T t0, class Seq>
using offset_sequence_t=type<offset_sequence<T, t0, Seq>>;
template<class T, T t0, T...ts>
struct offset_sequence<T, t0, std::integer_sequence<T, ts...>>:
  tag<std::integer_sequence<T, (t0+ts)...>>
{};
template<int start, int finish>
using axis_limits = offset_sequence_t<int, start,
  std::make_integer_sequence<finish-start>
>;

template<class T>
using point = std::vector<T>;

template<class T, T...Is>
point<T> make_point( std::integer_sequence<T, Is...> ) {
  return {Is...};
}
template<class...Pts>
std::vector<point<int>> make_space( types<Pts...> ) {
  return { make_point( Pts{} )... };
}
template<class...Ts>
std::vector<point<int>> generate_point_space() {
  return make_space( coords_t<Ts...>{} );
}

and we have the syntax you want.

We can make things into arrays and everything constexpr if we want. Simply change make_point to return an array of sizeof...(Is) and the like.

how I'd like to read a book on this art. I'm missing this in the c++ bookshelf, modern template metaprogramming (with functional insights). — oblitum, Aug 10 '15 at 01:33

deduce entire vector space at compile time

3 Answers3