陣列是絕大多數程式設計語言中的內建資料結構. 陣列的索引具有如下的形式 :

[i_{1}][i_{2}]...[i_{k}]

其中, i_{j} \geq 0 (j = 1, 2, ..., k). 當 k = 1 時, 陣列的維度是一維的; 當 k = 2 時, 陣列的維度是二維的; 對於一般的 k, 通常稱陣列為 k 維陣列. 其中, k > 0. 稱 i_{j} (j = 1, 2, ..., k) 為陣列注標. 通常來說, 陣列注標是從 0 開始的. 但是有一些程式設計語言的陣列注標是從 1 開始的

陣列的應用需要我們將陣列元素序列化, 即按照一個一維順序進行排列. 令 n 是一個 k 維陣列的元素個數, 該陣列的序列化需要借助一個影射函式. 將陣列注標 [i_{1}][i_{2}]...[i_{k}] 影射為 [0, n - 1] 範圍中的一個數 map(i_{1}, i_{2}, ..., i_{k}). 當陣列維度為 1 的時候, 即 k = 1 時, 影射函式為

map(i) = i

當陣列維度為 2 的時候, 即 k = 2 時, 影射函式為

map(i_{1}, i_{2}) = i

在 C++ 中, 高維陣列使用的影射方式是行主影射, 得到的陣列注標稱為行主次序. 對於行主影射, 是以行為主, 從第一行開始, 從左至右對元素進行編號

另一種影射方式是列主影射, 得到的陣列注標稱為列主次序. 對於列主影射, 是以列為主, 從第一列開始, 從上至下對元素進行編號

設現有 18 個元素的陣列, 被分成了 3 行 6 列, 若使用行主影射的形式, 那麼元素的編號如下 :

若使用列主影射的方式, 則其元素的編號如下 :

在行主次序中, 影射函式為

map(i_{1}, i_{2}) = i_{1} \cdot \max{\left \{ i_{2} \right \}} + i_{2}

其中, \max{\left \{ i_{2} \right \}} 表示 i_{2} 可以取到的最大值. 對於上面展示的陣列來說, \max{\left \{ i_{2} \right \}} = 5. 即為陣列的列數

相應地, 列主次序中, 影射函式為

map(i_{1}, i_{2}) = i_{1} \cdot \max{\left \{ i_{1} \right \}} + i_{2}

二維陣列的行主影射可以拓展至二維甚至以上的陣列. 以三維陣列為例, 首先將三維陣列的第一維度展開, 並且按行排列 :

我們發現, 當第一維度固定的時候, 可以得到一個二維陣列, 而二維陣列的影射可以用二維陣列的影射函式. 配合二維陣列的大小, 可以得到三位陣列的影射函式 :

\begin{aligned} map(i_{1}, i_{2}, i_{3}) &= map(i_{2}, i_{3}) + i_{1} \cdot \max {\left \{ i_{2} \right \}} \cdot \max{\left \{ i_{3} \right \}} \\ &= i_{1} \cdot \max{\left \{ i_{2} \right \}} \cdot \max{\left \{ i_{3} \right \}} + i_{2} \cdot \max{\left \{ i_{2} \right \}} + i_{3} \end{aligned}

對於 n 維陣列來說, 其影射函式為 :

\begin{aligned} map(i_{1}, i_{2}, ..., i_{n}) &= map(i_{2}, i_{3}, ..., i_{n}) + i_{1} \cdot \prod_{j = 2}^{n} \max{\left \{ i_{j} \right \}} \\ &= map(i_{3}, i_{4}, i_{n}) + i_{1} \cdot \prod_{j = 2}^{n} \max{\left \{ i_{j} \right \}} + i_{2} \cdot \prod_{j = 3}^{n} \max{\left \{ i_{j} \right \}} \\ &= \ ... \\ &= map(i_{n - 1}, i_{n}) + i_{1} \cdot \prod_{j = 2}^{n} \max{\left \{ i_{j} \right \}} + i_{2} \cdot \prod_{j = 3}^{n} \max{\left \{ i_{j} \right \}} + ... + \\ &\; \ \ \ \ i_{n - 2} \cdot \max{\left \{ i_{n - 1} \right \}} \cdot \max{\left \{ i_{n} \right \}} \\ &= i_{1} \cdot \prod_{j = 2}^{n} \max{\left \{ i_{j} \right \}} + i_{2} \cdot \prod_{j = 3}^{n} \max{\left \{ i_{j} \right \}} + ... + \\ &\; \ \ \ \ i_{n - 2} \cdot \max{\left \{ i_{n - 1} \right \}} \cdot \max{\left \{ i_{n} \right \}} + i_{n - 1} \cdot \max{\left \{ i_{n} \right \}} + i_{n} \\ &= i_{n} + \sum_{p = 1}^{n}i_{p}\prod_{j = p + 1}^{n}\max{\left \{ i_{j} \right \}} \end{aligned}

根據上述提示, 大家可以自己總結出 n 維陣列下, 影射方式為列主次序的影射函式

對於現代程式設計語言來說, 無論多麼高維度的陣列, 都會將高維陣列最終展開為一個一維陣列連續存取. 再使用對應的影射函式找到元素即可

除此之外, 還有一種方法是宣告一個一維陣列, 但將其當作多維陣列來使用. 即宣告了一維陣列後, 通過影射函式將一維陣列影射為多維陣列. 雖然 C++ 中並不存在這種方式, C++ 可以模擬這一種方式, 然而這正是編碼器對高維陣列所做的事情罷了

第三種方式是不規則陣列, C++ 中不直接提供, 但是可以通過動態記憶體配置做到. 當一個陣列有多個維度的時候, 每一個維度所能夠容納的元素並不一定相同, 這就是不規則的陣列 :

#include <iostream>



using namespace std;



int main(int argc, char *argv[]) {

    constexpr int length[] {6, 3, 4, 2, 7};

    int *irregular_array[sizeof length / sizeof length[0]] {};

    for(auto i {0}; i < sizeof length / sizeof length[0]; ++i) {

        irregular_array[i] = new int[length[i]] {};

    }

    //do something on irregular_array

    //...

    for(auto i {0}; i < sizeof length / sizeof length[0]; ++i) {

        for(auto j {0}; j < length[i]; ++j) {

            cout << irregular_array[i][j] << "\t";

        }

        cout << endl;

        delete[] irregular_array[i];

    }

}

資料結構 array : GitHub 點擊直達

大家在看程式碼的時候, 可能會對 array<T, 0> 的樣板特製化產生疑問, 此處我要解釋一下這個樣板特製化的作用. 當大家使用樣板進行編碼的時候, 很可能出現 sizeof...(args) == 0 或著樣板引數為 0 的情況

template <size_t N>

[[nodiscard]]

constexpr array<int, N> init_array() noexcept {

    return {};

}

當上述函式 N == 0 的時候, 如果沒有針對 array<T, 0> 進行特製化, 各個編碼器的表現各不相同. Clang 以及 GCC 下編碼通過, MSVC 下將會產生編碼錯誤. 另外, 這個特製化就是為了當上述情況出現的時候, 統一行為防止出現編碼錯誤而設定的. 一般來說, 我們不應該主動使用 array<T, 0> 這樣的特製化, 這種特製化被具現化的情況是第二個樣板參數未知的時候被動產生的