【C++篇】揭秘STL vector：高效动态数组的深度解析（从使用到模拟实现）

//无参构造
vector<int> v;

//构造并初始化n个val
vector<int> v1(10, 6);
vector<string> v2(10, "1111111");

//使用迭代器进行初始化构造
string str("qwertyuiop");
vector<char> v3(str.begin(), str.end())

//拷贝构造
vector<int> v4(v1);

//赋值运算符重载
v = v1;

typedef T* iterator;
typedef const T* const_iterator;

iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        //创建一个容量更大的新的数组
        T* tmp = new T[n];
        if (_start)
        {
            //元素迁移
            memcpy(tmp, _start, sizeof(T) * size());
            //清理原数组
            delete[] _start;
        }
        
        _start = tmp;
        _finish = _start + sz;
        _endOfStorage = _start + n;
    }
}

for (int i = 0; i < size(); ++i)
{
    tmp[i] = _start[i];
}

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
            //自定义类型会发生浅拷贝
            //memcpy(tmp, _start, sizeof(T) * size());

            //用赋值重载来避免自定义类型发生浅拷贝问题
            for (int i = 0; i < size(); ++i)
            {
                tmp[i] = _start[i];
            }

            delete[] _start;
        }
        
        _start = tmp;
        _finish = _start + sz;
        _endOfStorage = _start + n;
    }
}

iterator insert(iterator pos, const T& x)
{
	//检查pos是否合法
    assert(pos <= _finish && pos >= _start);
	//检查容量，不足就扩
    if (_finish == _endOfStorage)
    {
        int newcapacity = capacity() == 0 ? 1 : capacity() * 2;
        reserve(newcapacity);
    }
	//挪数据
    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
	// 插入数据
    *pos = x;
    ++_finish;

    return pos;
}

iterator insert(iterator pos, const T& x)
{
    assert(pos <= _finish && pos >= _start);

    if (_finish == _endOfStorage)
    {
        int len = pos - _start;

        int newcapacity = capacity() == 0 ? 1 : capacity() * 2;
        reserve(newcapacity);

        //解决迭代器失效问题
        pos = _start + len;
        //如果发生扩容，会使得数据更换空间，此时迭代器指向的空间地址是无效地址（pos变为野指针）
        //因此，要更新迭代器pos。
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;

    return pos;
}

 iterator erase(iterator pos)
 {
     assert(pos < _finish && pos >= _start);
     assert(size() > 0);

     iterator end = pos;
     while (end < _finish - 1)
     {
         *end = *(end + 1);
         ++end;
     }

     --_finish;

     return pos;
 }

void resize(size_t n, const T& value = T());

 void resize(size_t n, const T& value = T())
 {
     if (n > size())
     {
         reserve(n);

         while (_finish != _start + n)
         {
             *_finish = value;
             ++_finish;
         }
     }
     else
     {
         _finish = _start + n;
     }
 }

//构造并初始化n个val
vector(size_t n, const T& val = T())
{
	//直接复用resize的功能可以完美解决
    resize(n, val);
}

// 迭代器构造
// [first, last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

//无参构造
vector()
{}

private:
    iterator _start = nullptr; // 指向数据块的开始
    iterator _finish = nullptr; // 指向有效数据的尾
    iterator _endOfStorage = nullptr; // 指向存储容量的尾

//构造1
vector(size_t n, const T& val = T())
{
    resize(n, val);
}

//构造2
//避免vector<int> v(10, 1) 调用3
//亦或者用vector<int> v(10u, 1)，使其完美匹配1
vector(int n, const T& val = T())
{
    resize(n, val);
}

// 构造3
// 迭代器构造
// [first, last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

vector()
{}

//拷贝构造v1
vector(const vector<T>& v)
{
    _start = new T[v.capacity()];
    int sz = v.size();
    //自定义类型会发生浅拷贝
    //memcpy(_start, v, sizeof(T) * sz);

    //用赋值重载来避免自定义类型发生浅拷贝问题
    for (int i = 0; i < sz; ++i)
    {
        _start[i] = v[i];
    }

    _finish = _start + sz;
    _endOfStorage = _start + v.capacity();
}

//拷贝构造v2
vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    reserve(v.capacity());
    for (auto e : v)
    {
        push_back(e);
    }
}

//赋值重载
vector<T>& operator=(vector<T> v)
{
    swap(v);

    return *this;
}