C++ -- vector

1. 关于vector

1.1 对比原生数组

1. 固定大小，缺乏动态扩展能力
   • 原生数组需在编译时确定大小
   • vector可根据需求动态扩容
2. 安全性问题
   • 原生数组越界访问会导致未定义行为，甚至程序崩溃
   • vector提供边界检查
3. 功能缺失
   • 原生数组不支持直接插入、删除或动态调整
   • vector提供丰富接口

1.2 vector的核心优势

1. 动态数组特性：自动管理内存，无需手动new/delete；支持动态扩容
2. 连续内存布局：数据在内存中连续存储，可通过下标直接定位元素
3. 高性能操作：尾部插入/删除均摊O(1)时间复杂度

2. 扩容

2.1 底层实现

在vector上有三个迭代器：_start指向头部，_finish指向有效数据的下一个位置，_endofstorage指向存储容量的尾

2.2 扩容过程

在插入数据时，是否扩容的前提是_finish是否等于_endofstorage，如果是则会进行扩容。
扩容时，编译器会开辟一块新空间，将原有数据拷贝到新空间上，并将迭代器指向新的空间，最后释放掉旧空间。

3. 构造函数

vector的构造函数有这几种

int main()
{vector<int> v1;vector<int> v2(10, 0);// 创建n个，并给其初始值string str = "hello world";vector<int> v3(str.begin(), str.end());// 用迭代器vector<int> v4(v3);// 拷贝构造return 0;
}

4. 接口模拟实现

template<class T>
class vector
{
public:// ......private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾
};

4.1 实现迭代器

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator cbegin() const
{return _start;
}const_iterator cend() const
{return _finish;
}

4.2 扩容

void reserve(size_t n)
{// 开辟新空间 把旧空间上的数据拷贝到新空间上 释放旧空间size_t oldsize = size();T* tmp = new T[n];// 如果原空间上有数据就要先拷贝到新空间上if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_endOfStorage = _start + n;//_finish = _start + size();// 有问题：此时的_start是新空间上的，不是原空间_finish = _start + oldsize;
}void resize(size_t n, const T& value = T())
{// 判断是否要扩容if (_finish == _endOfStorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}
}

4.3 重载[]

T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}const T& operator[](size_t pos)const
{return _start[pos];
}

4.4 插入和删除

void push_back(const T& x)
{if (_finish == _endOfStorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*(_finish) = x;++_finish;
}void pop_back()
{--_finish;
}iterator insert(iterator pos, const T& x)
{assert(pos <= _finish);assert(pos >= _start);if (_finish == _endOfStorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator tmp = _finish - 1;while (pos <= tmp){*(tmp + 1) = *tmp;--tmp;}*pos = x;++_finish;return pos;
}iterator erase(iterator pos)
{assert(pos <= _finish);assert(pos >= _start);iterator tmp = _finish - 1;while (pos < tmp){*pos = *(pos + 1);pos++;}--_finish;return pos;
}

4.5 构造函数和析构函数

vector()
{if (_finish == _endOfStorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}
}vector(int n, const T& value = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}vector(const vector<T>& v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}vector<T>& operator= (vector<T> v)
{_start = v._start;_finish = v._finish;_endOfStorage = v._endOfStorage;
}~vector()
{if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}
}

5. 迭代器失效

迭代器失效常发生在扩容和越界时。

5.1 扩容后失效

void reserve(size_t n)
{// 开辟新空间 把旧空间上的数据拷贝到新空间上 释放旧空间size_t oldsize = size();T* tmp = new T[n];// 如果原空间上有数据就要先拷贝到新空间上if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_endOfStorage = _start + n;//_finish = _start + size();// 有问题：此时的_start是新空间上的，不是原空间_finish = _start + oldsize;
}

在实现插入接口时，如果不考虑记录oldsize就会出现迭代器失效问题。

在插入数据时，如果涉及扩容，也可能出现这种情况

iterator insert(iterator pos, const T& x)
{assert(pos <= _finish);assert(pos >= _start);if (_finish == _endOfStorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator tmp = _finish - 1;while (pos <= tmp){*(tmp + 1) = *tmp;--tmp;}*pos = x;++_finish;return pos;
}

5.2 越界失效

可能会发生在删除数据时

6. 深浅拷贝

if (_start)
{memcpy(tmp, _start, sizeof(T) * size());delete[] _start;
}

这段代码不用strcpy的原因是浅拷贝会引发二次析构。浅拷贝后的对象指向的空间和拷贝目标为同一块空间，第一次delete后这段空间消失，此时tmp相当于被析构了。但后续中，tmp还会再析构一次，造成二次析构导致程序崩溃。所以这里需要实现深拷贝。