目录
vector的模拟实现
一.初定义
vector:
template<class T> class Vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start = nullptr;// 指向数据块的开始 iterator _finish = nullptr;// 指向有效数据的尾 iterator _end_of_storage = nullptr;// 指向存储容量的尾 };
二.相关功能
2.1 迭代器
//迭代器原生指针 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
2.2 capacity
1.size
size_t size() const { return _finish - _start; }
2.capacity
size_t capacity() const { return _end_of_storage - _start; }
3.reserve（扩容）
1.判断是否需要扩容
2.开辟新空间，将原来的数据拷贝过去(存一下原来的size)
3.释放掉旧空间，并更新_start,_finish,_end_of_storage
void reserve(size_t n) { if (n > capacity()) { //存一下size size_t sz = size(); //开新空间，扩容 T* tmp = new T[n]; if (_start) { //拷贝原来的数据(深拷贝) for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start;//释放原来的空间 } _start = tmp;//更新 _finish = tmp + sz; _end_of_storage = tmp + n; } }
4.resize
1.若n < size() : 删除数据（更改_finish）
2.若n > capacity() :扩容（使用reserve复用）
3.将多的空间使用value初始化，并更新_finish
--这里给的缺省值，是使用匿名对象构造生成的
void resize(size_t n, const T& value = T()) { if (n < size()) //小于有效数据删除 { _finish = _start + n; } else { if(n > capacity())//扩容 reserve(n); while (_finish != _start + n) { *_finish = value; ++_finish; } } }
2.3 access
T& operator[](size_t pos) { assert(pos < _size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < _size()); return _start[pos]; }
2.4 modify
1.push_back
1.检查是否需要扩容
2.尾插数据
void push_back(const T& x) { //扩容 if (_finish == _end_of_storage) { reserve(capacity() == 0? 4: 2*capacity()); } //尾插数据 *_finish = x; _finish++; }
2.pop_back
void pop_back() { assert(!empty()); _finish--; }
3.empty
bool empty() { return _finish == _start; }
4.swap
void swap(Vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage,v._end_of_storage); }
5.insert
1.检查pos是否在区间内
2.检查是否需要扩容
--若扩容，更新pos（避免迭代器失效）记录pos相对于_start的位置，扩容后更新
3.挪动数据
4.在pos位置插入数据
iterator insert(iterator pos, const T& x) { assert(pos >= _start && pos <= _finish); //判断是否扩容 if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len;//扩容后更新pos，避免迭代器失效 } //1.挪动数据 iterator end = _finish; while (end > pos) { *end = *(end-1); end--; } //2.在pos位置插入数据 *pos = x; _finish++; return pos; }
6.erase
1.检查pos位置是否合法
2.挪动数据覆盖
iterator erase(iterator pos) { assert(pos>= _start && pos<_finish); //挪动数据 iterator end = pos; while (end < _finish) { *(end) = *(end + 1); end++; } //表示删除数据 _finish--; return pos; }
2.5构造函数与析构函数
1.构造函数
// 构造函数与析构函数 //构造函数 Vector() {} Vector(int n, const T& value = T()) { //尾插n次value reserve(n); for (int i = 0; i < n; i++) { push_back(value); } }效果：
2.析构函数
//析构函数 ~Vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }
3.拷贝构造
1.传统写法：
Vector(const Vector<T>& v) { //开新空间 _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T)*v.size()); //复制元素 for (size_t i = 0; i < v.size(); ++i) { _start[i] = v._start[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }2.现代写法：
//拷贝构造（现代写法） Vector(Vector<T>& v) { Vector<T> tmp(v.begin(),v.end()); swap(tmp); }
效果：
4.运算符重载
传统写法
Vector<T>& operator=(const Vector<T>& v) { if (this == &v) { return *this; // 自我赋值，不执行任何操作 } // 释放原始资源 delete[] _start; // 分配新资源 _start = new T[v.capacity()]; // 复制元素 for (size_t i = 0; i < v.size(); ++i) { _start[i] = v._start[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); return *this; }现代写法
void swap(Vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage,v._end_of_storage); } //v1 = v2,(现代写法) Vector<T>& operator= (Vector<T> v) { swap(v); return *this; }
5.迭代器区间构造
//迭代器区间构造 template<class InputIterator> Vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); ++first; } }
三.迭代器失效与深浅拷贝：
1.迭代器失效
- 野指针：vector扩容后，释放掉之前的空间，开辟新的空间，原来的iterator此时指向了被释放的空间
- 指向内容含义改变：vector的插入操作，可能会挪动数据，挪动后，iterator就不再指向原来的数据（含义改变）
解决：
1.更新迭代器
2.insert等函数，返回删除元素的下一个位置
一般执行相关操作后，都默认该迭代器失效
2.深浅拷贝
- 浅拷贝是指在复制对象时，只复制对象的成员变量的值
- 深拷贝是指在复制对象时，不仅复制对象的成员变量的值，还复制对象所拥有的资源，例如动态分配的内存
在类中，实例化对象后用一个对象拷贝构造另外一个对象，若是浅拷贝（只复制值）则会导致两个对象都指向同一块空间，最后调用析构函数的时候，会释放同一块空间两次，
所以需要深拷贝
