Last active
September 19, 2017 00:17
-
-
Save airekans/8807a6d45476dd5e4e25da5cbbc0d57b to your computer and use it in GitHub Desktop.
A technique to initialize array data when accessing it at the first time. This is presented in Programming Pearls' exercises. Here's a very nice explanation of what the following code does: https://research.swtch.com/sparse
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template<unsigned int N> | |
| struct Array | |
| { | |
| Array() : top(0) {} | |
| // Invariant: if a data has been initialized, it will have the following properties: | |
| // 1. index_key[i] < top | |
| // 2. indexes[index_key[i]] == i | |
| int Get(unsigned int i) { | |
| if (index_key[i] < top && indexes[index_key[i]] == i) { | |
| // the key has been initialized, we just return it | |
| return data[i]; | |
| } | |
| // otherwise, we initialize the data. | |
| // Here for simplicity, we set the data to 0. | |
| index_key[i] = top; | |
| indexes[top] = i; | |
| ++top; | |
| data[i] = 0; | |
| return data[i]; | |
| } | |
| int data[N]; | |
| unsigned int index_key[N]; | |
| unsigned int indexes[N]; | |
| unsigned int top; | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment