面试题：自定义实现类似C++ vector的动态扩容机制

Question

假设你需要在C++中自定义一个类似于vector的动态数组类MyVector，要求实现动态扩容机制。请给出该类的主要成员函数和数据结构设计，并详细描述动态扩容函数的实现逻辑，包括如何处理内存释放、数据拷贝以及避免内存碎片化等问题。

Answer 1

1. 数据结构设计

template <typename T>
class MyVector {
private:
    T* data;    // 存储数据的指针
    size_t size_; // 当前元素个数
    size_t capacity_; // 当前容量

    // 内存管理辅助函数
    void reallocate();
    void copy_data(T* new_data, T* old_data, size_t length);
};

2. 主要成员函数

构造函数

template <typename T>
MyVector<T>::MyVector() : size_(0), capacity_(1) {
    data = new T[capacity_];
}

析构函数

template <typename T>
MyVector<T>::~MyVector() {
    delete[] data;
}

拷贝构造函数

template <typename T>
MyVector<T>::MyVector(const MyVector& other) : size_(other.size_), capacity_(other.capacity_) {
    data = new T[capacity_];
    copy_data(data, other.data, size_);
}

赋值运算符重载

template <typename T>
MyVector<T>& MyVector<T>::operator=(const MyVector& other) {
    if (this != &other) {
        delete[] data;
        size_ = other.size_;
        capacity_ = other.capacity_;
        data = new T[capacity_];
        copy_data(data, other.data, size_);
    }
    return *this;
}

push_back 函数

template <typename T>
void MyVector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        reallocate();
    }
    data[size_++] = value;
}

operator[] 重载

template <typename T>
T& MyVector<T>::operator[](size_t index) {
    return data[index];
}

template <typename T>
const T& MyVector<T>::operator[](size_t index) const {
    return data[index];
}

size 函数

template <typename T>
size_t MyVector<T>::size() const {
    return size_;
}

capacity 函数

template <typename T>
size_t MyVector<T>::capacity() const {
    return capacity_;
}

3. 动态扩容函数的实现逻辑

reallocate 函数

template <typename T>
void MyVector<T>::reallocate() {
    capacity_ *= 2; // 通常扩容为原来的2倍
    T* new_data = new T[capacity_];
    copy_data(new_data, data, size_);
    delete[] data;
    data = new_data;
}

copy_data 函数

template <typename T>
void MyVector<T>::copy_data(T* new_data, T* old_data, size_t length) {
    for (size_t i = 0; i < length; ++i) {
        new_data[i] = old_data[i];
    }
}

4. 内存相关问题处理

• 内存释放：在析构函数中，使用delete[]释放动态分配的内存，避免内存泄漏。在扩容时，先分配新的内存，再释放旧的内存，保证数据的连续性。
• 数据拷贝：通过copy_data函数进行数据拷贝，确保新内存中数据与旧内存数据一致。在拷贝构造函数和赋值运算符重载中也使用该函数进行数据拷贝。
• 避免内存碎片化：采用成倍扩容策略（如扩容为原来的2倍），减少频繁扩容导致的内存碎片化。因为每次扩容时分配的内存空间相对较大，减少了小块内存频繁分配和释放的情况。