voy a intentar poner un ejemplo...

int vector[2] = {1, 2}
int matriz[2][2] {1, 2, 3, 4};

Primer caso en la memoria
| 1 | 2 |

Segundo caso (matriz):
| 1 | 2 | 3 | 4 |

En el vector para acceder al segundo elemento se hace vector[1]

En la matriz para acceder al tercer elemento (3), se accede mediante matriz[1][0], pero realmente se almaena de forma lineal, y el compilador a partir de los subindices i, j, sabe cuantas posiciones tienen que avanzar a partir del primer elemento, es decir:

El desplazamiento es:
(i * número de elementos columna) + j

Perdona pero no, cualquier compilador actual convierte tu matriz en un vector unidimensional. Por esa razón tienes que indicar el número de columnas cuandos pasas una matriz como parámetro a una función.

Otra cosa son las matrices "dinámicas" que creas con malloc/new. Se suelen hacer con un array de punteros (y ahí si hay perdida de rendimiento porque tienes que redireccionar dos veces).

Hola.

Siempre interpreté que las matrices se almacenan del modo que dice amchacon.

Row major order
Ordering of C++ Arrays

Saludos

Un vector y un array unidimensional son lo mismo, una matriz es bidimensional.