Generic Constexpr Lookup Table C++11

Question

I'm trying to construct a generic lookup table that takes a generator function and creates the table at compile time.Here is the code for the table and generation:

#ifndef CONSTEXPR_LOOKUPTABLE_H
#define CONSTEXPR_LOOKUPTABLE_H

#include <cstddef>

/* Generate a range */
template <std::size_t... Is>
struct seq{};

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

template <std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

/*
    The lookup table consisting of values to be 
    computed at compile-time
*/
template<std::size_t N, class T>
struct LookUpTable{
    std::size_t indexes[N];
    T values[N];

    static constexpr std::size_t length = N;
};

/*
   Generate the table from a generator function
*/
template <class Lambda, std::size_t... Is>
constexpr auto LookUpTableGenerator(seq<Is...>, Lambda f) ->
LookUpTable<sizeof...(Is), decltype(f(Is)...)>
{
    return {{ Is... }, { f(Is)... }};
}

template <std::size_t N, class Lambda>
constexpr auto LookUpTableGenerator(Lambda f) ->
decltype(LookUpTableGenerator(gen_seq<N>{}, f))
{
    return LookUpTableGenerator(gen_seq<N>{}, f);
}

#endif

Here is the main function:

#include <iostream>
#include <memory>
#include <vector>
#include <string>
#include "ConstExprLookupTable.h"

typedef unsigned short ushort;
typedef unsigned char byte;

/*
    There are only 10 digits (0 - 9)
*/
static constexpr ushort DIGITS = 10;
/*
   A table to prevent repeated division calculation:
        table[i][j] = (i + j) / 10;
*/
static constexpr ushort carry_table[DIGITS][DIGITS] = \
{ 
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
    {0, 0, 0, 0, 0, 0, 0, 1, 1, 1},
    {0, 0, 0, 0, 0, 0, 1, 1, 1, 1},
    {0, 0, 0, 0, 0, 1, 1, 1, 1, 1},
    {0, 0, 0, 0, 1, 1, 1, 1, 1, 1},
    {0, 0, 0, 1, 1, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1, 1, 1, 1, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

static constexpr double myFunc(double x)
{
    return x / DIGITS;
}

int main()
{
    constexpr std::size_t length = 100;
    auto table = LookUpTableGenerator<length>(myFunc);
    for (auto v : table.values){
        std::cout << v << " ";
    }
    std::cout << "\n";
}

However, this generates the following compile-time errors:

ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
 LookUpTable<sizeof...(Is), decltype(f(Is)...)>
                                              ^
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:46: error: template argument 2 is invalid
ConstExprLookupTable.h:33:1: error: invalid use of template-name ‘LookUpTable’ without an argument list
 LookUpTable<sizeof...(Is), decltype(f(Is)...)>
 ^
ConstExprLookupTable.h:33:12: error: expected initializer before ‘<’ token
 LookUpTable<sizeof...(Is), decltype(f(Is)...)>
            ^
virt.cpp: In function ‘int main()’:
virt.cpp:88:53: error: no matching function for call to ‘LookUpTableGenerator(double (&)(double))’
     auto table = LookUpTableGenerator<length>(myFunc);

My questions are (finally!): 1) Is this possible to do? When I replace the class T parameter of the lookup table with a concrete type (like a double), the code compiles fine. 2) I think the error is here:

template <class Lambda, std::size_t... Is>
    constexpr auto LookUpTableGenerator(seq<Is...>, Lambda f) ->
    LookUpTable<sizeof...(Is), decltype(f(Is)...)>
    {
        return {{ Is... }, { f(Is)... }};
    }

It seems to not like the decltype. What should the decltype be in this case?

N.B. it might be beneficial to pass the info you have at compile time to `f`, that is, `f(std::integral_constant{})` instead of `f(Is)`. — dyp, Aug 02 '15 at 21:54
Hmm it might be in fact more useful to pass the size of the range to `f`. At least, it was necessary [in my sample application](http://stackoverflow.com/a/19016627/420683) of constexpr lookup table generation. — dyp, Aug 02 '15 at 22:02

Barry · Accepted Answer · 2015-08-02T21:57:31.697

4

There are lots of contexts where a pack can be expanded, but decltype isn't one of them. You'd have to just wrap your pack in some metafunction that pulls out the type. Something as easy as:

template <typename T, typename... >
using first = T;

And then use it:

template <class Lambda, std::size_t... Is>
constexpr auto LookUpTableGenerator(seq<Is...>, Lambda f) ->
LookUpTable<sizeof...(Is), first<decltype(f(Is))...>>

Though since all the Is are the same type anyway (size_t), you could just use that directly:

template <class Lambda, std::size_t... Is>
constexpr auto LookUpTableGenerator(seq<Is...>, Lambda f) ->
LookUpTable<sizeof...(Is), decltype(f(std::declval<size_t>()))>

edited Aug 02 '15 at 21:57

answered Aug 02 '15 at 21:56

Barry

286,269
29
621
977

@dyp Ha, yeah. Though for some reason I didn't think to write `size_t{}`... `declval` forever! – Barry Aug 02 '15 at 21:57
And I was thinking whether or not to use the more conventional `declval` :) -- Well it's used typically in such a scenario, so why deviate. – dyp Aug 02 '15 at 21:58
Thank you for the clear explanation Barry; your solution and dyp's helped clear things up! I ended up using dyp's solution since it just made the code look a little more concise. – Bizkit Aug 02 '15 at 22:02
@Bizkit It's very common to use `declval` within `decltype` because the types used for arguments can sometimes have nasty restrictions which prevent creation of dummies via `{}` value-init (e.g. types which are not default constructible or not destructible). So there's a trade-off between conciseness and sticking to conventions. – dyp Aug 02 '15 at 22:05
Since a `size_t` is default constructible/destructible, does `declval` provide any extra safety in this case? – Bizkit Aug 02 '15 at 22:07
@Bizkit No technical benefits for `size_t`, it just follows the convention of using `declval` to create arguments for return type deduction of function call expressions within `decltype`. – dyp Aug 02 '15 at 22:09

Generic Constexpr Lookup Table C++11

1 Answers1