Lookup table with constexpr

Question

I'm looking to create a lookup table of coordinates, something like:

int a[n][2] = {{0,1},{2,3}, ... }

For a given n, to be created at compile time. I started looking into constexpr, but is seems like a function returning a constexpr std::vector<std::array <int, 2> > isn't an option, as I get:

invalid return type 'std::vector<std::array<int, 2ul> >' of constexpr function

How can create such a compile time array?

`std::vector` is not a literal type and therefore cannot be used in C++11 `constexpr`. C++11's `array` type lacks `constexpr` accessors and therefore also has limited use in `constexpr` functions. If you don't have some of the C++1y lib/compiler support, I suggest using a custom array type instead. — dyp, Sep 25 '13 at 22:23
Would be more useful if you added some details of what you want to do ;) — dyp, Sep 25 '13 at 22:25
@DyP - Just create a list of coordinates that I'd like to have at compile time. An example would be ~100 points on a line. — nbubis, Sep 25 '13 at 22:28
N.B. in C++1y, you can also use an `initializer_list`, as they're [required to be literal types in C++1y](http://stackoverflow.com/q/16063123/420683). — dyp, Sep 25 '13 at 22:33

score 28 · Answer 1 · answered May 24 '16 at 12:19

28

With C++14, you do not need too much template magic. Here an example of how to have a lookup table for f(x) = x^3 with the first coordinate being the x value and the second coordinate being the f(x) value:

#include <iostream>

template<int N>
struct Table
{
    constexpr Table() : values()
    {
        for (auto i = 0; i < N; ++i)
        {
            values[i][0] = i;
            values[i][1] = i * i * i;
        }
    }
    int values[N][2];
};

int main() {
    constexpr auto a = Table<1000>();
    for (auto x : a.values)
        std::cout << "f(" << x[0] << ") = " << x[1] << '\n';
}

answered May 24 '16 at 12:19

IceFire

4,016
2
31
51

3

What is the meaning of: `: values()` in `constexpr Table() : values()`? Does it zero-initialize or something? – Jonas Feb 24 '17 at 07:18
1

&Jonas Yes, it zero-initializes which is necessary because C++ needs to have a compile-const value. It will be set in the constructor later but this is hard to track by the compiler – IceFire Feb 25 '17 at 08:07
@IceFire are you sure? according to http://en.cppreference.com/w/cpp/container/array/operator_at non-const operator[] is constexpr only since C++17 version. This therefore can be troublesome – DawidPi Apr 23 '17 at 22:23
1

@DawidPi We do not have an std::array here, though – IceFire Apr 24 '17 at 05:47
@IceFire Ah sure. Sorry for that. – DawidPi Apr 24 '17 at 07:29
1

It may be noteworthy that this approach may cause issues with the compiler running out of heap for sufficiently large `N` which is not that unlikely for large lookup tables. – Koenigsberg Jul 09 '20 at 08:51

score 20 · Accepted Answer · edited May 23 '17 at 12:16

I'll dump the code first, adding references and comments where necessary/appropriate later. Just leave a comment if the result is somewhat close to what you're looking for.

Indices trick for pack expansion (required here to apply the generator), by Xeo, from this answer, modified to use std::size_t instead of unsigned.

#include <cstddef>

// by Xeo, from https://stackoverflow.com/a/13294458/420683
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...>{};

Generator function:

#include <array>

template<class Generator, std::size_t... Is>
constexpr auto generate_array_helper(Generator g, seq<Is...>)
-> std::array<decltype(g(std::size_t{}, sizeof...(Is))), sizeof...(Is)>
{
    return {{g(Is, sizeof...(Is))...}};
}

template<std::size_t tcount, class Generator>
constexpr auto generate_array(Generator g)
-> decltype( generate_array_helper(g, gen_seq<tcount>{}) )
{
    return generate_array_helper(g, gen_seq<tcount>{});
}

Usage example:

// some literal type
struct point
{
    float x;
    float y;
};
// output support for `std::ostream`
#include <iostream>
std::ostream& operator<<(std::ostream& o, point const& p)
{  return o << p.x << ", " << p.y;  }

// a user-defined generator
constexpr point my_generator(std::size_t curr, std::size_t total)
{
    return {curr*40.0f/(total-1), curr*20.0f/(total-1)};
}

int main()
{
    constexpr auto first_array = generate_array<5>(my_generator);
    constexpr auto second_array = generate_array<10>(my_generator);

    std::cout << "first array: \n";
    for(auto p : first_array)
    {
        std::cout << p << '\n';
    }
    std::cout << "========================\n";

    std::cout << "second array: \n";
    for(auto p : second_array)
    {
        std::cout << p << '\n';
    }
}

Wow - Thats a lot of code! Is that really the shortest way of doing this? — nbubis, Sep 25 '13 at 23:14
@nbubis This is a very general solution. If you narrow down / specify more precisely what you want, there might be a less verbose solution. — dyp, Sep 25 '13 at 23:17
I think he usage example is exactly what I'm looking for, but that sure is a lot of extra code :) — nbubis, Sep 25 '13 at 23:18
@nbubis Short enough now? I realized you don't even need the accessors for this kind of thing. — dyp, Sep 25 '13 at 23:27
+1 [here's what I got](http://stackoverflow.com/a/19023500/819272) before reading your question (I updated it to make the `make_integer_sequence` opaque to callers, like you did, tnx for that idea) — TemplateRex, Sep 26 '13 at 10:37
@TemplateRex I guess this already has lots of duplicates, I just was too lazy / didn't know what to search for. Is there any significant difference between `decltype(g(..))` and `result_of`? — dyp, Sep 26 '13 at 10:41
@DyP I was just wrestling with the correct syntax, got `result_of` to work before `decltype` :-) — TemplateRex, Sep 26 '13 at 10:43

score -7 · Answer 3 · answered Sep 25 '13 at 23:11

-7

What about using GNU gperf or some other code generation utility?

answered Sep 25 '13 at 23:11

youdontneedtothankme

656
4
6

2

Hi. Would you be able to use gperf to initialize a vector at compile time? And if how so? – magu_ Jul 21 '14 at 06:25

Lookup table with constexpr

3 Answers3

Linked