[Implementation trick] Arrays with negative indices in C++

Revision en1, by -is-this-fft-, 2019-10-10 16:30:55

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;
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en1 -is-this-fft- 2019-10-10 16:30:55 1542 Initial revision (published)