你們一定都聽說過它的故事……

是的沒錯，就是一個蘿卜一個坑。???

想象一下數組就是那個坑，那么定義數組就是在挖坑。

元素就是蘿卜。

坑就在那里(地上)，整整齊齊地排在那里。

于是數組最重要的一個特性就顯現出來了——隨機存取。還有一個特性就是它在內存里開辟的是一整塊的連續空間，是多少就是多少。一眼望去也可以看出來它是多少。

// 定義一個大小為 10 的靜態數組
int arr[10];// 用 memset 函數把數組的值初始化為 0
memset(arr, 0, sizeof(arr));// 使用索引賦值
arr[0] = 1;
arr[1] = 2;// 使用索引取值
int a = arr[0];

數據定義(安放)的事情我們解決了，下面就是操作了——增刪查改

按理來說我們希望“增刪查改后的數組仍然還是個數組”，就是按順序去看，一個蘿卜一個坑，可以短，但中間不能又空缺的

在尾部增刪查改都好說，可在頭部或者中間就不一樣了。因為會造成空缺！！！

于是就涉及到了「數據搬移」。需要騰位置的騰位置，需要擠一下的擠一下。

插入→

// 大小為 10 的數組已經裝了 4 個元素
int arr[10];
for (int i = 0; i < 4; i++) {arr[i] = i;
}// 在索引 2 置插入元素 666
// 需要把索引 2 以及之后的元素都往后移動一位
// 注意要倒著遍歷數組中已有元素避免覆蓋，不懂的話請看下方可視化面板
for (int i = 4; i > 2; i--) {arr[i] = arr[i - 1];
}// 現在第 3 個位置空出來了，可以插入新元素
arr[2] = 666;

擴容→

// 大小為 10 的數組已經裝滿了
int arr[10];
for (int i = 0; i < 10; i++) {arr[i] = i;
}// 現在想在數組末尾追加一個元素 10
// 需要先擴容數組
int newArr[20];
// 把原來的 10 個元素復制過去
for (int i = 0; i < 10; i++) {newArr[i] = arr[i];
}// 釋放舊數組的內存空間
// ...// 在新的大數組中追加新元素
newArr[10] = 10;

刪除→

// 大小為 10 的數組已經裝了 5 個元素
int arr[10];
for (int i = 0; i < 5; i++) {arr[i] = i;
}// 刪除 arr[1]
// 需要把 arr[1] 之后的元素都往前移動一位
// 注意要正著遍歷數組中已有元素避免覆蓋，不懂的話請看下方可視化面板
for (int i = 1; i < 4; i++) {arr[i] = arr[i + 1];
}// 最后一個元素置為 -1 代表已刪除
arr[4] = -1;

數組的插入、擴容、刪除的時間復雜度是O(N)，因為涉及到數據搬移，給新元素騰地方。

是的這就是靜態數組，就是這么簡單。

Then，動態數組它要來咯！！！

動態數組其實就是我們找了個兔子搬運工。?_?

動態數組底層還是靜態數組，只是自動幫我們進行數組空間的擴縮容，并把增刪查改操作進行了封裝，讓我們使用起來更方便而已。

即C++提供給我們的vector類。?o?

// 創建動態數組
// 不用顯式指定數組大小，它會根據實際存儲的元素數量自動擴縮容
vector<int> arr;for (int i = 0; i < 10; i++) {// 在末尾追加元素，時間復雜度 O(1)arr.push_back(i);
}// 在中間插入元素，時間復雜度 O(N)
// 在索引 2 的位置插入元素 666
arr.insert(arr.begin() + 2, 666);// 在頭部插入元素，時間復雜度 O(N)
arr.insert(arr.begin(), -1);// 刪除末尾元素，時間復雜度 O(1)
arr.pop_back();// 刪除中間元素，時間復雜度 O(N)
// 刪除索引 2 的元素
arr.erase(arr.begin() + 2);// 根據索引查詢元素，時間復雜度 O(1)
int a = arr[0];// 根據索引修改元素，時間復雜度 O(1)
arr[0] = 100;// 根據元素值查找索引，時間復雜度 O(N)
int index = find(arr.begin(), arr.end(), 666) - arr.begin();

???

???

???

(枯燥的)動態數組代碼實現

#include <iostream>
#include <stdexcept>
#include <vector>template<typename E>
class MyArrayList {
private:// 真正存儲數據的底層數組E* data;// 記錄當前元素個數int size;// 最大元素容量int cap;// 默認初始容量static const int INIT_CAP = 1;public:MyArrayList() {this->data = new E[INIT_CAP];this->size = 0;this->cap = INIT_CAP;}MyArrayList(int initCapacity) {this->data = new E[initCapacity];this->size = 0;this->cap = initCapacity;}// 增void addLast(E e) {// 看 data 數組容量夠不夠if (size == cap) {resize(2 * cap);}// 在尾部插入元素data[size] = e;size++;}void add(int index, E e) {// 檢查索引越界checkPositionIndex(index);// 看 data 數組容量夠不夠if (size == cap) {resize(2 * cap);}// 搬移數據 data[index..] -> data[index+1..]// 給新元素騰出位置for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}// 插入新元素data[index] = e;size++;}void addFirst(E e) {add(0, e);}// 刪E removeLast() {if (size == 0) {throw std::out_of_range("NoSuchElementException");}// 可以縮容，節約空間if (size == cap / 4) {resize(cap / 2);}E deletedVal = data[size - 1];// 刪除最后一個元素// 必須給最后一個元素置為 null，否則會內存泄漏data[size - 1] = E();size--;return deletedVal;}E remove(int index) {// 檢查索引越界checkElementIndex(index);// 可以縮容，節約空間if (size == cap / 4) {resize(cap / 2);}E deletedVal = data[index];// 搬移數據 data[index+1..] -> data[index..]for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}data[size - 1] = E();size--;return deletedVal;}E removeFirst() {return remove(0);}// 查E get(int index) {// 檢查索引越界checkElementIndex(index);return data[index];}// 改E set(int index, E element) {// 檢查索引越界checkElementIndex(index);// 修改數據E oldVal = data[index];data[index] = element;return oldVal;}// 工具方法int getSize() {return size;}bool isEmpty() {return size == 0;}// 將 data 的容量改為 newCapvoid resize(int newCap) {E* temp = new E[newCap];for (int i = 0; i < size; i++) {temp[i] = data[i];}// 釋放原數組內存delete[] data;data = temp;cap = newCap;}bool isElementIndex(int index) {return index >= 0 && index < size;}bool isPositionIndex(int index) {return index >= 0 && index <= size;}// 檢查 index 索引位置是否可以存在元素void checkElementIndex(int index) {if (!isElementIndex(index)) {throw std::out_of_range("Index out of bounds");}}// 檢查 index 索引位置是否可以添加元素void checkPositionIndex(int index) {if (!isPositionIndex(index)) {throw std::out_of_range("Index out of bounds");}}void display() {std::cout << "size = " << size << " cap = " << cap << std::endl;for (int i = 0; i < size; i++) {std::cout << data[i] << " ";}std::cout << std::endl;}~MyArrayList() {delete[] data;}
};int main() {// 初始容量設置為 3MyArrayList<int> arr(3);// 添加 5 個元素for (int i = 1; i <= 5; i++) {arr.addLast(i);}arr.remove(3);arr.add(1, 9);arr.addFirst(100);int val = arr.removeLast();// 100 1 9 2 3for (int i = 0; i < arr.getSize(); i++) {std::cout << arr.get(i) << std::endl;}return 0;
}

有兩個檢查越界的方法，分別是?checkElementIndex?和?checkPositionIndex，你可以看到它倆的區別僅僅在于?index < size?和?index <= size。

C++動態數組vector的底層是連續的內存空間，普通的數組，并不使用環形數組

擴展

環形數組

通過取模運算實現。

會方便在頭部增刪元素，避免了數據搬移

環形數組的關鍵在于，它維護了兩個指針?start?和?end，start?指向第一個有效元素的索引，end?指向最后一個有效元素的下一個位置索引。

這樣，當我們在數組頭部添加或刪除元素時，只需要移動?start?索引，而在數組尾部添加或刪除元素時，只需要移動?end?索引。

當?start, end?移動超出數組邊界（< 0?或?>= arr.length）時，我們可以通過求模運算?%?讓它們轉一圈到數組頭部或尾部繼續工作，這樣就實現了環形數組的效果。