C++ vector如何實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容

c++
小樊
81
2024-10-16 12:28:10

在 C++ 中，std::vector 是一個(gè)動(dòng)態(tài)數(shù)組，它可以根據(jù)需要自動(dòng)調(diào)整大小。當(dāng)向 vector 添加元素且當(dāng)前容量不足以容納新元素時(shí)，vector 會(huì)自動(dòng)擴(kuò)容。默認(rèn)情況下，vector 的容量每次擴(kuò)容時(shí)都會(huì)翻倍，但也可以通過(guò)傳遞自定義分配器來(lái)改變擴(kuò)容策略。

要實(shí)現(xiàn)類似 std::vector 的動(dòng)態(tài)擴(kuò)容功能，可以定義一個(gè)類，并為其提供一個(gè) reallocate 方法來(lái)管理內(nèi)存分配和擴(kuò)容。以下是一個(gè)簡(jiǎn)單的示例：

#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;
}

在這個(gè)示例中，我們定義了一個(gè)名為 DynamicArray 的類，它具有與 std::vector 類似的功能。當(dāng) push_back 方法被調(diào)用且當(dāng)前容量不足以容納新元素時(shí)，reallocate 方法會(huì)被調(diào)用以分配新的內(nèi)存空間，并將現(xiàn)有元素復(fù)制到新的內(nèi)存空間中。

0 踩