C++ vector如何實現動態擴容

在 C++ 中，std::vector 是一個動態數組，它可以根據需要自動調整大小。當向 vector 添加元素且當前容量不足以容納新元素時，vector 會自動擴容。默認情況下，vector 的容量每次擴容時都會翻倍，但也可以通過傳遞自定義分配器來改變擴容策略。

要實現類似 std::vector 的動態擴容功能，可以定義一個類，并為其提供一個 reallocate 方法來管理內存分配和擴容。以下是一個簡單的示例：

#include <iostream>
#include <algorithm>
#include <memory>

template <typename T>
class DynamicArray {
public:
    DynamicArray() : data(nullptr), size(0), capacity(0) {}

    ~DynamicArray() {
        delete[] data;
    }

    void push_back(const T& value) {
        if (size == capacity) {
            reallocate(capacity == 0 ? 1 : capacity * 2);
        }
        data[size++] = value;
    }

    T& operator[](size_t index) {
        if (index >= size) {
            throw std::out_of_range("Index out of range");
        }
        return data[index];
    }

    size_t getSize() const {
        return size;
    }

private:
    void reallocate(size_t newCapacity) {
        T* newData = static_cast<T*>(std::allocator<T>().allocate(newCapacity));
        for (size_t i = 0; i < size; ++i) {
            std::allocator<T>().construct(newData + i, std::move_if_noexcept(data[i]));
            std::allocator<T>().destroy(data + i);
        }
        delete[] data;
        data = newData;
        capacity = newCapacity;
    }

    T* data;
    size_t size;
    size_t capacity;
};

int main() {
    DynamicArray<int> arr;
    for (int i = 0; i < 10; ++i) {
        arr.push_back(i);
    }

    for (size_t i = 0; i < arr.getSize(); ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

在這個示例中，我們定義了一個名為 DynamicArray 的類，它具有與 std::vector 類似的功能。當 push_back 方法被調用且當前容量不足以容納新元素時，reallocate 方法會被調用以分配新的內存空間，并將現有元素復制到新的內存空間中。