c++ notes

Defining 1D, 2D and 3D vectors

typedef vector<float> float_1D;

typedef vector<vector<float>> float_2D;

typedef vector<vector<vector<float>>> float_3D;

float_1D A(x,0);

float_2D B(x,float_1D(y,0));

float_3D C(x,float_2D(y,float_1D(z,0)));

1D index to 2D index

If your 2D matrix is symmetric where [i][j] = [j][i], you can reduce the memory footprint by 2 fold when storing only values where i < j in a 1D vector of size l(l-1)/2; instead of a l^2. Where l = length. To access the values, you can use the follow functions:

To go from 2D index to 1D index:

int ij_n (int l, int i, int j){

// exact solution

return j - i - 1

+ l*(l-1)/2

- (l-i)*((l-i)-1)/2;

}

To go from 1D index to 2D index:

int n_i_slow (int l, int n){

// iterative solution

int i = 0; n *= 2;

while((i+1)*(2*l-i-2) <= n){i++;}

return(i);

}

int n_i_fast (int l, int n){

// approx. solution, using integer rounding

int i = (2*l - sqrt(-8*n + 4*l*l - 4*l) - 1)/2;

return(i);

}

int ni_j (int l, int n, int i){

// exact solution

return n + i + 1

- l*(l-1)/2

+ (l-i)*((l-i)-1)/2;

}

1D index to 3D index

If your 3D matrix is symmetric where [i][j][k] = [i][k][j] = [j][i][k] = [j][k][i] = [k][i][j] = [k][j][i], you can reduce the memory footprint by 6 fold when storing only values where i < j < k in a 1D vector of size

l(l-1)(l-2)/6; instead of a l^3. Where l = length.

To go from 3D index to 1D index:

int ijk_n (int l, int i, int j, int k){

// exact solution

return k - j - 1

+ l*(l-1)*(l-2)/6

- (l-i)*((l-i)-1)*((l-i)-2)/6

+ (l-i-1)*((l-i-1)-1)/2

- (l-j)*((l-j)-1)/2;

}

To go from 1D index to 3D index:

int n_i (int l, int n){

// iterative approach

int i = 0; n *= 6;

while((i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6) <= n){i++;}

return(i);

}

int ni_j_slow (int l, int n, int i){

int n_i = ((i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6)/6 - n) * 2;

// iterative solution

int j = i+1; while((j*j-2*j*l+3*j+l*l-3*l+2) >= n_i){j++;}

return(j);

}

int ni_j_fast (int l, int n, int i){

int n_i = (i+1)*(3*l*l-3*l*i-9*l+i*i+5*i+6)/6 - n;

// faster using integer rounding

int j = (2*l - sqrt(8*n_i) - 1)/2;

return(j);

}

int nij_k (int l, int n, int i, int j){

// exact solution

return n + j + 1

- l*(l-1)*(l-2)/6

+ (l-i)*((l-i)-1)*((l-i)-2)/6

- (l-i-1)*((l-i-1)-1)/2

+ (l-j)*((l-j)-1)/2;

}