Search code examples
c++arraysc++17inlineconstexpr

How to generate an inline constexpr plain array of array in c++17

The question

I am writing a software in c++17 for which performances are absolutely critical. I would like available in a few key functions constants in arrays themselves in arrays. It matters that both these array are accessible by a integer value in such (or similar) manner : 
int main()
{
    for (int i = 0; i < size_of_A ; i++)
    {
        for (int j = 0; j < size_of_B_in_A(i); j++)
        {
            std::cout << A[i][j];
        }
    }
}

This would be the kind of array we would like to create assuming some function int f(a, b)

A
{
    // B1
    {
        f(1, 1),
        f(1, 2),
        f(1, 3),
           ...
        f(1, large number)
    },
    // B2
    {
        f(2, 1),
           ...
        f(2, some other large number)
    },
    ... etc
}

The Twist

Each inner array may be of different size which we have will stored elsewhere, we have to find the size at compile time. I would rather not use std::vector for they are assumed slightly slower . Also an I suppose a std::vector would be stored on the heap which would be a performance issue in my specific case. Furthermore, std::vector cannot be used as "inline constexpr" which would be necessary as I expect to have a large amount of value in those array never going to change. I am fine with recompiling all those values each time but not keeping them in an external file by policy as I am to follow a strict coding style.

What I Have Tried

brace initializer

// A.hh

#pragma once

#include <iostream>

void test1();
void test2();

inline constexpr int B1[1] = {1};
inline constexpr int B2[2] = {2, 3};
inline constexpr int B3[3] = {4, 5, 6};

inline constexpr const int *A[3] = {B1, B2, B3};


// main.cc

#include "A.hh"

int main()
{
    std::cout << "values : ";
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            std::cout << A[i][j];
        }
    }

    std::cout << "\n\naddress test : \n";
    std::cout << &A << '\n';
    test1();
    test2();
}

// somewhere.cc

#include "A.hh"

void test1()
{
    std::cout << &A << '\n';
}


// elsewhere.cc

#include "A.hh"

void test2()
{
    std::cout << &A << '\n';
}

which prints :

./a.out
values : 123456

address test :
0x56180505cd70
0x56180505cd70
0x56180505cd70

Therefore A has not been copied in main.cc, somewhere.cc and elsewhere.cc which is good. I would like to go further and be able to create a huge amount of values.

struct with constexpr

using tips found here , I do this to be able to perform operations during array construction. 
// B.hh

#pragma once

#include <iostream>

template <int N>
struct X
{
    int arr[N];
    constexpr X(): arr()
    {
        for (int i = 0; i < N; i++)
        {
            arr[i] = i % 3;
        }
    }
};

inline constexpr auto A = X<500>();

// main.cc

#include "B.hh"

int main()
{
    for (int i = 0; i < 500; i++)
    {
        std::cout << A.arr[i];
    }
}

Which unsuspectingly prints out

012012 (etc)...

Finally an array of array

And this where I am stuck 
#pragma once

#include <iostream>

template <int N>
struct sub_array
{
    int arr[N];
    constexpr sub_array() : arr()
    {
        for (int i = 0; i < N; i++)
        {
            arr[i] = i;
        }
    }
};

struct array
{
    sub_array</*what here ?*/> arr[100];

    constexpr array() : arr()
    {
        for (int i = 0; i < 100; i++)
        {
            int size = i * 2; // a very large number

            // the value of 'size' is not usable in a constant expression
            //
            // I see why it is, but I can't think of any other way
            arr[i] = sub_array<size>;
        }
    }
};

inline constexpr array A = array();

How can I build such kind of array ?

Thank you for your time and consideration.

Solution

  • Just use std::array<std::span<int>, N>, which is a fixed size array of spans of different sizes. To generate this, use an std::index_sequence

    Header:

    constexpr std::size_t size_of_A = 500;
extern const std::array<const std::span<const int>, size_of_A>& A;

    Implementation:

    constexpr std::size_t size_of_B_in_A(std::size_t i) { return i%10+1;}
constexpr int f(std::size_t i, std::size_t j) {return static_cast<int>(i%(j+1));}

template <int I, int N>
struct B
{
    std::array<int,N> arr;
    explicit constexpr B()
    {
        for (int j = 0; j < N; j++)
            arr[j] = f(I, j);
    }
    constexpr operator const std::span<const int>() const {return {arr};}
};

template<class index_sequence>
class BGen;
template<std::size_t... I>
struct BGen<std::integer_sequence<std::size_t,I...>> {
    static constexpr std::tuple<B<I, size_of_B_in_A(I)>...> bs{};
    static constexpr std::array<const std::span<const int>, sizeof...(I)> A {std::get<I>(bs)...};
};
const std::array<const std::span<const int>, size_of_A>& A 
    = BGen<decltype(std::make_index_sequence<size_of_A>{})>::A;

    Usage:

    int main()
{
    for (unsigned i = 0; i < A.size() ; i++)
    {
        for (unsigned j = 0; j < A[i].size(); j++)
        {
            std::cout << A[i][j];
        }
    }
}

    http://coliru.stacked-crooked.com/a/d68b0e9fd6142f86

    However, stepping back: This solution is NOT the normal way to go about solving this problem. Since it's all constexpr, this is all data not code. Ergo, the most performant solution is two programs. One generates the data and saves it to a file that ships with (inside?) your program. Then your program simply maps the file into memory, and uses the data directly.