高效實現動態數組

一、什麼是動態數組

動態數組是一種可以在運行時根據需要擴展或縮小大小的數組結構。相較於靜態數組，動態數組具有更高的靈活性。

在C++中，我們可以使用STL中的vector來實現動態數組。

二、使用vector的基本操作

C++ STL中的vector是一個動態數組，提供了方便的操作方法。

1. 定義vector

#include 
using namespace std;

vector vec; //定義一個空的整型vector
vector vec(size); //定義一個有size個元素的整型vector

2. 添加元素

我們可以使用push_back()或insert()函數來添加元素。

vec.push_back(1); //在vector的尾部添加元素1
vec.insert(vec.begin()+index, 1); //在vector的指定位置添加元素1，index表示位置

3. 刪除元素

我們可以使用erase()函數來刪除元素。

vec.erase(vec.begin()+index); //刪除vector的指定位置元素，index表示位置

4. 訪問元素

我們可以使用下標操作符[]、at()函數或迭代器訪問vector中的元素。

vec[index]; //通過下標訪問vector中的元素
vec.at(index); //通過at()函數訪問vector中的元素
for (auto it=vec.begin(); it!=vec.end(); ++it) //通過迭代器訪問vector中的元素
    cout << *it << " ";
cout << endl;

5. 獲取vector大小

我們可以使用size()函數獲取vector中元素的數量。

vec.size(); //獲取vector中元素的個數

三、自定義動態數組

除了使用STL中的vector，我們也可以手動實現動態數組。

1. 實現原理

動態數組可以理解為一個靜態數組加上一個計數器。當靜態數組存儲空間不足時，我們可以使用new運算符動態申請更多的空間，並將舊數據複製到新空間中。

2. 實現代碼

以下是一個簡單的動態數組實現：

template 
class Array {
private:
    T* data; //指向數據的指針
    int size; //數組中元素的數量
    int capacity; //數組中可以存儲的元素數量

public:
    Array(int cap=10) : size(0), capacity(cap) { //構造函數
        data = new T[capacity];
    }

    ~Array() { //析構函數
        delete[] data;
    }

    void resize(int new_cap) { //調整數組大小
        T* new_data = new T[new_cap];
        for (int i=0; i= capacity) {
            resize(2*capacity); //如果存儲空間滿了，擴大空間
        }
        data[size++] = elem;
    }

    void insert(T elem, int index) { //在指定位置插入元素
        if (size >= capacity) {
            resize(2*capacity); //如果存儲空間滿了，擴大空間
        }
        for (int i=size; i>index; --i) {
            data[i] = data[i-1]; //元素後移
        }
        data[index] = elem;
        ++size;
    }

    void erase(int index) { //刪除指定位置的元素
        for (int i=index+1; i<size; ++i) {
            data[i-1] = data[i]; //元素前移
        }
        --size;
        if (size <= capacity/4) {
            resize(capacity/2); //如果存儲空間過多，縮小空間
        }
    }

    T operator[](int index) { //重載下標操作符
        return data[index];
    }

    int getSize() { //獲取數組中元素數量
        return size;
    }
};

四、動態數組的優缺點

1. 優點

動態數組的大小是動態可變的，可以根據需要靈活調整。

動態數組支持尾部添加元素的高效操作，相較鏈表，具有更高的內存緩存優化效果。

2. 缺點

動態數組的調整操作需要消耗一定的時間，刪除操作可能會導致數組空間浪費，增加空間時可能分配不到連續的內存塊。

五、總結

本文介紹了如何使用STL中的vector來實現動態數組，以及手動實現動態數組的基本原理和代碼示例。動態數組相較於靜態數組具有更高的靈活性和操作效率，但也存在空間浪費等問題。