-is-this-fft-'s blog

By -is-this-fft-, history, 4 days ago, , 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;
} Comments (13)
 » I bet many people do know that.
 » 4 days ago, # | ← Rev. 3 →   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 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  in the middle of the big array int main() { a[-10] = a = 7; cout << a[-10] << " " << a << " " << a << endl; }
•  » » 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.
•  » » 4 days ago, # ^ | ← Rev. 2 →   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]?
•  » » » I always used a complicated struct for that, where I would implement [] operator.
•  » » » » 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.
•  » » » » » 4 days ago, # ^ | ← Rev. 4 →   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(&_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] << " "; }
•  » » » template struct MyArray { int offset; vector 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 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
•  » » this is beyond geniosity
•  » » 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.
•  » » » 4 days ago, # ^ | ← Rev. 2 →   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).
 » int * dp = dp_ + ZERO; dp[-1]++; int a = (-1)[dp];
 » 4 days ago, # | ← Rev. 2 →   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; template struct darray : array, 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 clr; // computing color here darray tbl; // holding your matrix here vector 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); } } }