模拟实现C++版vector的技术要点

小蓝

2023 年 12 月 06 日

116 次浏览

暂无评论

4243字数

Linux 技术杂烩

实现一个C++版本的vector，即一个动态数组，主要需要注意以下几个关键点：

模板类实现： vector是一个泛型容器，可以容纳任意类型的元素。因此，要使用模板编程来使我们的vector类能够处理任意类型的数据。
动态内存管理： vector需要动态分配内存以存储元素。这通常涉及到使用 new和 delete操作符来分配和释放内存。为了效率，vector通常会预分配一定容量的内存，当实际元素数量超出当前容量时再进行扩容。
对象构造和析构： 当一个新元素被添加到vector中，需要调用元素类型的构造函数来创建对象。同样地，当元素被移除或vector被销毁时，需要调用元素类型的析构函数来销毁对象。
元素访问： 提供访问元素的接口，如 operator[]以及 at()方法，同时保证访问的安全性。at()在索引超出范围时应抛出异常。
内存扩容策略： 当vector中的元素个数达到当前容量时，需要扩展其容量。通常扩展策略会将容量增加一倍或者增加固定的数量，这样可以减少内存的频繁重新分配。
拷贝控制： 实现拷贝构造函数、赋值运算符和析构函数，确保vector的复制和赋值能够正确地复制内部的动态数组，并且不会造成内存泄漏。
移动语义： 为了提高效率，vector应支持移动构造函数和移动赋值运算符，允许在临时对象或将要销毁的对象上进行低成本的资源转移。
迭代器支持： 实现迭代器以支持范围for循环和算法库，至少需要提供 begin()、end()方法，以及相应的迭代器类型定义。
接口丰富性： 提供一系列用于容器操作的方法，如 push_back()、pop_back()、insert()、erase()、clear()、resize()等。

下面是一个简化版的C++ vector的实现草案，以作为如何实现这些技术点的参考：

#include <cassert>
#include <initializer_list>
#include <algorithm> // std::copy, std::move
#include <stdexcept> // std::out_of_range
#include <utility>   // std::swap

template<typename T>
class SimpleVector {
private:
    T* mData;
    size_t mSize;
    size_t mCapacity;

    void check_index(size_t index) const {
        if (index >= mSize) throw std::out_of_range("Index out of range");
    }

    void grow() {
        size_t newCapacity = mCapacity ? mCapacity * 2 : 1;
        T* newData = new T[newCapacity];
        std::move(mData, mData + mSize, newData);
        delete[] mData;
        mData = newData;
        mCapacity = newCapacity;
    }

public:
    SimpleVector() : mData(nullptr), mSize(0), mCapacity(0) {}

    explicit SimpleVector(size_t size) : mSize(size), mCapacity(size) {
        mData = new T[mCapacity];
    }

    SimpleVector(const SimpleVector& other)
        : mData(nullptr), mSize(other.mSize), mCapacity(other.mCapacity) {
        mData = new T[mCapacity];
        std::copy(other.mData, other.mData + other.mSize, mData);
    }

    SimpleVector(SimpleVector&& other) noexcept
        : mData(other.mData), mSize(other.mSize), mCapacity(other.mCapacity) {
        other.mData = nullptr;
        other.mSize = 0;
        other.mCapacity = 0;
    }

    SimpleVector& operator=(SimpleVector other) {
        swap(*this, other);
        return *this;
    }

    ~SimpleVector() {
        delete[] mData;
    }

    T& operator[](size_t index) {
        assert(index < mSize);
        return mData[index];
    }

    const T& operator[](size_t index) const {
        assert(index < mSize);
        return mData[index];
    }

    T& at(size_t index) {
        check_index(index);
        return mData[index];
    }

    const T& at(size_t index) const {
        check_index(index);
        return mData[index];
    }

    void push_back(const T& value) {
        if (mSize == mCapacity) grow();
        mData[mSize++] = value;
    }

    void pop_back() {
        if (mSize > 0) {
            mSize--;
            mData[mSize].~T();
        }
    }

    size_t size() const { return mSize; }
    size_t capacity() const { return mCapacity; }
  
    friend void swap(SimpleVector& first, SimpleVector& second) noexcept {
        using std::swap;
        swap(first.mSize, second.mSize);
        swap(first.mCapacity, second.mCapacity);
        swap(first.mData, second.mData);
    }
};

这个代码片段实现了简单的vector，包括基础的容量管理、元素访问、内存分配以及复制控制。在实际使用中，可能还需要对这个基础实现进行优化和功能完善，使其能够满足更广泛的使用场景和性能要求。