-is-this-fft-'s blog

[Implementation trick] Arrays with negative indices in C++
By -is-this-fft-, history, 5 years ago, In English

Inspired by people losing their mind over dp[mask][-1] here...

Motivation

Sometimes you need to implement an array with negative indices. For example you may want to have an array dp[i] which stores values for all $$$i$$$, $$$-10^5 \le i \le 10^5$$$. One way is to make dp an (unordered) map. But this is slow and can get TLE in certain problems. Another way is this:

const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp [MAX_N];

and instead of calling dp[i] you call dp[ZERO + i]. If I want to access dp[-5] for example, I access dp[ZERO - 5]. But this is tedious and error-prone. It's very easy to make a mistake by forgetting to write ZERO somewhere.

The solution

Do the above, but do it like this!

const int MAX_N = 2e5 + 20;
const int ZERO = 1e5 + 5;
int dp_ [MAX_N];

int& dp (int idx) { // the '&' is very important!
  return dp_[ZERO + idx];
}

A very important part is that dp doesn't return an int; it returns an int& — a reference to the given position in the array. This means that it's very convenient to use. We can assign to dp(i), modify dp(i) etc.

int main () {
  int main () {
  dp(-300) = 7;
  dp(40) = 5;
  dp(-300) += 777; // All of those are fine!
  cout << dp(40) << " " << dp(-300) << endl;
  
  swap(dp(40), dp(-300)); // Even this works!
  cout << dp(40) << " " << dp(-300) << endl;
}
  • Vote: I like it
  • +121
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it +268 Vote: I do not like it

Your method is very dangerous because it's very easy to just type dp[i] somewhere (instead of dp(i)) and it will compile. EDIT: -is-this-fft- is right below that this mistake won't compile but I will still claim that it's very inconvenient to use dp(i) and I would keep writing it wrong way all the time.

Instead, in the middle of an array save a new pointer that will pretend to be a new array:

#include <bits/stdc++.h>
using namespace std;
const int M = 10; // I want indices from -M to +M
int _a[2*M+1]; // underlying array of size 2*M+1
int* a = _a + M; // array that has index [0] in the middle of the big array
int main() {
	a[-10] = a[1] = 7;
	cout << a[-10] << " " << a[3] << " " << a[10] << endl;
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I use dp_ as the array name for this exact reason. Typing dp[i] results in something like error: cannot convert ‘int’ to ‘int&(int)’ in assignment.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +29 Vote: I do not like it

    Second that. Trick from original post is very dangerous, it's literally shooting ourselves in a foot, while method mentioned by Errichto is much much better. (EDIT: Ahhh, I now see the above OP's response, I guess it is fine in that case)

    Follow-up question: how to make multi-dimensional array with range [-M..M][-M..M][-M..M]?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      I always used a complicated struct for that, where I would implement [] operator.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        It is possible to do this with similar trick to yours, just much more complicated. Resulting type will contain a lot of & and *, but I was never good with these things :p. C++ magicians (at least from my point of view) are required here.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 4   Vote: I like it +37 Vote: I do not like it

          Theoretically you can do the same — put a pointer into the center of array. You just need to typecast it, if your array has more than one dimension. I'm sure that C++ standard looks bad at this kind of casts, so some unobvious pitfalls can arise.

          // Array [-N..N][-N..N][-N..N]
const int N = 3;
int _arr[2*N + 1][2*N + 1][2*N + 1];
auto a = reinterpret_cast<int (*)[2*N + 1][2*N +1]>(&_arr[N][N][N]);

int main() {
	for (int i = -N; i <= N; ++i)
		for (int j = -N; j <= N; ++j)
			for (int k = -N; k <= N; ++k)
				cout << a[i][j][k] << " ";
}
          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it 
      template<class T>
struct MyArray {
	int offset;
	vector<T> vec;

	MyArray(int n, int off, T &&values = T()) {
		vec.resize(n, values);
		offset = off;
	}

	T& operator[](int i) {
		i += offset;
		assert(0 <= i and i < int(vec.size()));
		return vec[i];
	}
};

      MyArray<int> dp(2 * n, m) creates a vector with 2n elements, where i-th element has index i-m. It is possible to create multi-dimensional vectors, just like normal vectors: example

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    this is beyond geniosity

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Just wondering but will the pointer method be slower than adding an offset manually, like for example if u access the array many times? Because i heard pointers take up more time, so yea just curious. Thanks in advance.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      A pointer is an integer (which happens to contain a memory address) and arithmetic on it doesn't work much differently.$$$\textrm{}^{\dagger}$$$ Both approaches dereference only once. The method in the original post has the additional overhead of a function call, but we can expect the compiler to inline it since it's so short.

      $$$^{\dagger}$$$ Note that a[i] or *(a + i) is going to involve multiplication, since the correct address is that of a plus i * sizeof(datatype).

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it 
int * dp = dp_ + ZERO;
dp[-1]++;
int a = (-1)[dp];
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

There is a similar trick when you have a problem about some matrix (like "find the shortest path in a labirint etc"), and you want to work with pairs so that you won't need to mess up with double indices.

You can write:

using pii = pair<int, int>;

template <typename T, size_t N, size_t M>
struct darray : array<array<T, M>, N> {
    T& operator()(const pii &k) {
        return (*this)[k.first][k.second];
    }
};

pii operator+(const pii &a, const pii &b) {
    return {a.X + b.X, a.Y + b.Y};
}

pii operator-(const pii &a, const pii &b) {
    return {a.X - b.X, a.Y - b.Y};
}

And now it's pretty simple to manage any kind of dfs:

darray<int, MAXN, MAXN> clr; // computing color here
darray<int, MAXN, MAXN> tbl; // holding your matrix here
vector<pii> deltas = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

void dfs_color(const pii &v, int color) {
    clr(v) = color;
    for (const auto &d : deltas) {
        if (tbl(v+d) == '.' && clr(v+d) == 0) {
            dfs_color(v+d, color);
        }
    }
}
→ Reply