Static memory allocation - is it allocated sequentially?

Question

I need to know if it is guaranteed, for all compilers, that &N == &N_neg[MAXN] in the following code.

int N_neg[MAXN], N[MAXN]; // defined in the global scope!
T<N> t; // so I can access N[i] (for i < 0) inside T

If so, I'm done, this is all I need. If not, please read my full problem below.

NOTE: This is meant for programming contests only, so don't worry about maintainability. I'm more concerned about keeping T easy to understand.

---

I have the following definition:

template<int* B> class T { ... }

Inside T, however, I access B[-n], where n > 0. So, this is what I want to do:

#define MAXN 1000
int N[2*MAXN];
T<N + MAXN> t;

This is not allowed, according to the compiler. cppreference even has an example of this particular case saying it does not work, and I have already searched everywhere else for a solution (none to be found yet). I do understand how templates work, and I do know that (and why) the value of each template argument must be known during compilation time, and the address of N is only known later during linking.

Any suggestions?

---

Here is the full code (just in case someone has any suggestion based on the problem):

template<int M, int B[]> struct Hash {
    int h; Hash(int h = 0): h(h) {}
    int disp(int i) { return B[i]; }
    Hash concat(int ch, int i) { return (h + (ll) ch * B[i]) % M; }
    Hash subtract(int hl, int i) { return (ll) (h - hl + M) * B[-i] % M; }
    static void genBase(int n, int b) {
        B[0] = 1, B[-1] = powlg(b, M-2, M); // b^(-1) % M = b^(M-2) % M
        for (int i = 1; i < n; i++)
            B[i] = (ll) B[i-1] * b % M, B[-i] = (ll)B[-i+1] * B[-1] % M;
    }
};

Answer 1

if it is guaranteed, for all compilers, that &N == &N_neg[MAXN]

It is absolutely not guaranteed. The C++ standard does not mandate the relative memory layout of variables. In fact, it places very little restrictions on memory layout in general.

It's technically not even guaranteed that N and N_neg won't be optimized away by the compiler in some cases (though taking their addresses will generally prevent this from happening).

---

To make the layout sequential, you can use a struct:

struct { int N_neg[MAXN], N[MAXN]; } arrays;

Then, in theory you can access N_neg[MAXN] as the same memory location as N[0]. However, this is undefined behavior! It could work for you, but let's say you assign to N_neg[MAXN]. The compiler may assume that N[0] couldn't've been modified, and optimize away any accesses to it, causing your program to behave strangely.

You can get around this to some degree by declaring both arrays volatile, but then you lose out on a ton of potential optimizations.

Therefore, I would be very reluctant to use this approach. It's almost always better to stick to defined behavior.

---

Based on the updated/discovered requirements, this gets you close to needing only one template parameter:

template <typename T, T&>
struct Hash;

template <std::size_t Size, typename T, T (&Array)[Size]>
struct Hash<T[Size], Array>
{
    // Your code here

private:
    static constexpr T *N = &Array[Size / 2];
};

Instantiated like this:

int N_backing[MAXN * 2];
Hash<decltype(N_backing), N_backing> hash;

As N is constexpr, its value is guaranteed to be computed at compile time.