vector模拟实现的细节
- 1. vector的模拟实现源码
- 2. 重要接口注意事项
- 2.1 const修饰
- 2.2 begin()和end()
- 2.3 构造函数
- （1）迭代器区间初始化
- （2）构造函数冲突问题
- 发现问题
- 分析问题
- 解决问题
- （3）特殊的构造函数的实现
- 2.4 insert
- 注意点
- 分析原因
- 图解
- 2.5 push_back
- 2.6 reserve
- 发现问题
- 分析问题
- 解决问题
- 图解
- 2.7 resize
- 2.8 swap
- 3. vector的迭代器失效
- 3.1 insert造成的迭代器失效
- 案例：往容量已满的vector容器中插入值（实现时默认为4个空间）
- 分析问题
- 解决方案
- 3.2 erase造成的迭代器失效
- 案例：删除值为偶数的位置
- 图解
- 分析问题
- 解决问题
- 总结
1. vector的模拟实现源码
vector本质是顺序表，因此其迭代器可以理解为原生指针。
我们通过原生指针来模拟实现vector.
namespace B
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//Iterators
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
//constructor and destructor
vector()
:_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{ }
vector(initializer_list<T> il)
{
//const T* it = il.begin();
//while (it != il.end())
//{
//push_back(*it);
//it++;
//}
//il本质是一个类，有begin()和end()，因此也可以使用迭代器
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
vector(size_t n, const T& val = T())
{
//_start = new T[n];
//_finish = _endofstorage = _start + n;
//复用reserve
reserve(n);
for (size_t i = 0; i < n; i++)
push_back(val);
}
vector(int n, const T& val = 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)
{
*_finish = e;
_finish++;
}
}
//现代写法
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
//capacity
bool empty() const
{
return _finish == _start;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
void resize(size_t n , const T& val = T())
{
if (n > size())
{
reserve(n);
for (size_t i = size(); i < n; i++)
push_back(val);
}
else
{
//for (int i = size(); i > n; i--)
// pop_back();
//我们可以直接改变指针
_finish = _start + n;
}
}
void reserve(size_t n)
{
//不会缩容
//错误写法
//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变
//在调用size()时会出错 因为我们size()函数求大小时使用了_finish
//if (n > capacity)
//{
// T* tmp = new T[n];
// memcpy(tmp, _start, sizeof(T) * size());
// delete[] _start;
// _start = tmp;
// _finish = _start + size();
// _endofstorage = _start + n;
//}
//正确
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * size());
//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
//Element access
T& operator[](size_t pos)
{
return *(_start + pos);
}
const T& operator[](size_t pos) const
{
return *(_start + pos);
}
//Modify
void push_back(const T& x)
{
//扩容
//if (_finish == _endofstorage)
//{
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
//*_finish = x;
//_finish++;
//复用insert()
insert(end(), x);
}
void pop_back()
{
assert(!empty());
//_finish--;
//复用erase()
erase(end() - 1);
}
void swap(vector<T>& v)
{
//注意：不能直接写成swap(_start,v._start);
//swap(_start, v._start);
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= begin() && pos <= end());
size_t ret = pos - _start;
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//必须要更新pos--->迭代器失效
pos = _start + len;
}
iterator cur = _finish;
//移动数据
// _start pos _finish(tmp)
// 1 2 3 4 5
while (cur > pos)
{
*cur = *(cur - 1);
cur--;
}
*cur = x;
_finish++;
return _start + ret;
}
iterator erase(iterator pos)
{
assert(pos >= begin() && pos < end());
//移动数据
// _start pos _finish
// 1 2 3 4 5
size_t len = pos - _start;
iterator cur = pos;
while (cur < _finish - 1)
{
*cur = *(cur + 1);
cur++;
}
_finish--;
return pos;
}
void PrintVector()
{
for (auto& e : *this)
{
cout << e << " ";
}
cout << endl;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
}
2. 重要接口注意事项
2.1 const修饰
对于不修改成员变量的函数，如size(),capacity()，需要加上const，否则非const成员不能使用。
2.2 begin()和end()
注意对于常量型也必须写成begin()和end()，不能写成cbegin()和cend()，因为它们是C++11之后为了完整性新增加的，但是范围for迭代器只能替换begin()和end()。
实现代码：
//Iterators
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
2.3 构造函数
（1）迭代器区间初始化
迭代器区间初始化，使用模板的目的是为了不只是vector类的迭代器区间可以使用，string等其他容器的迭代器区间也可以使用。通过模板，无论我们传入的是哪一个容器的迭代器，都可以进行初始化，比如使用库中的list等。
示例：
我们使用string的迭代器来对vector进行初始化。
实现代码：
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
（2）构造函数冲突问题
发现问题
我们在使用如下代码想要初始化时，编译器报错。
void testvector4()
{
//会报错
vector<int> v(10, 1);
v.PrintVector();
//不会报错
//vector<int> v(10u, 1);
//v.PrintVector();
}
分析问题
我们想要调用的是第一个构造函数，但是编译器调用了第二个，调用到了我们所写的模板函数中去，由于int是内置类型，push_back时无法进行解引用，因此报错。
如果我们在10后面加上u，仅仅是传参的类型改变，但是却不会报错，程序正确执行，那么因此我们可以确定是类型引发的问题。
10和1这种内置类型如果我们没有额外说明，那么默认都为int类型，因此两个int类型，符合模板构造函数，而我们想要调用的构造函数由于n的类型为size_t，虽然两个int类型也可以调用，但是需要类型提升，比较麻烦，因此编译器在有两个函数参数类型相同的情况下，选择了调用函数模板实例化的函数。
解决问题
==因为编译器对于同名函数且参数类型相同的函数调用的规则是：有现有的函数调用现有的，没有现有的函数调用函数模板实例化出来的函数。==因此我们可以进行函数重载，重载一份n为int类型的函数，这样的话编译器就会先调用已经实现的函数啦。
实现代码：
vector(int n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
push_back(val);
}
vector(size_t n, const T& val = 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++;
}
}
（3）特殊的构造函数的实现
我们在OJ中经常能看到这种用法：
vector<int> v = { 1, 2, 3, 4 ,5};
而我们自己模拟实现的vector则不支持，会报错。
通过查阅文档，了解到这种用法是在C++11以后新增加的用法。
其中initializer list是一个类模板。
通过该构造函数进行初始化，在内部使用其迭代器进行初始化。
实现代码：
vector(initializer_list<T> il)
{
//方法一：
//const T* it = il.begin();
//while (it != il.end())
//{
//push_back(*it);
//it++;
//}
//方法二：
//il本质是一个类，有begin()和end()，因此也可以使用迭代器
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}
2.4 insert
注意点
如果扩容，不更新pos的位置，会造成内部的迭代器失效问题。
分析原因
如果空间容量不足，那么会进行扩容，而扩容之后由于reserve内部实现了_start 和 _finish的更新，但是pos的迭代器位置错误造成迭代器失效仍然是一个问题。
图解
代码实现：
iterator insert(iterator pos, const T& x)
{
assert(pos >= begin() && pos <= end());
size_t ret = pos - _start;
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//必须要更新pos--->迭代器失效
pos = _start + len;
}
iterator cur = _finish;
//移动数据
// _start pos _finish(tmp)
// 1 2 3 4 5
while (cur > pos)
{
*cur = *(cur - 1);
cur--;
}
*cur = x;
_finish++;
return _start + ret;
}
2.5 push_back
注意点：
函数参数要加const，否则会因为权限放大而报错。
vector<int> v;
v.push_back(1);
//1为常量，具有const属性，如果参数不加const则无法使用，会报错
实现代码：
void push_back(const T& x)
{
//原始写法
//扩容
//if (_finish == _endofstorage)
//{
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
//*_finish = x;
//_finish++;
//复用insert()
insert(end(), x);
}
2.6 reserve
注意事项：
1.memcpy是按照字节数量进行拷贝的---->在使用时会出现问题 如果是有深拷贝的类 会出错
2.扩容的时候提前保留size--->如果后面_finish直接使用_start + size()，size()在计算时使用的是已经释放空间的_finish，而_start指向的是新空间的开始，因此会报错。
3._endofStorge改变时，不能直接让其等于n，因为类型不同
发现问题
如果对于vector< string >这样的容器，由于string类内部也有申请空间，如果还是使用memcpy就会报错。
分析问题
我们在reserve()的时候重新new空间只是对于vector进行了深拷贝，但是由于string也是一个需要深拷贝的类，我们直接使用memcpy拷贝的是字节，属于浅拷贝，即新旧空间中的str指向同一块地址，而旧空间free之后会把那里的空间释放掉，因此程序会出错。
解决问题
直接使用循坏，对于每一个值都采取赋值构造，因为string的赋值构造内部是已经写好的深拷贝，我们不需要关心其内部是如何实现的。在采取赋值构造时它会自己进行深拷贝。
图解
实现代码：
void reserve(size_t n)
{
//不会缩容
//错误写法
//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变
//在调用size()时会出错 因为我们size()函数求大小时使用了_finish
//if (n > capacity)
//{
// T* tmp = new T[n];
// memcpy(tmp, _start, sizeof(T) * size());
// delete[] _start;
// _start = tmp;
// _finish = _start + size();
// _endofstorage = _start + n;
//}
//正确
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * size());
//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错
for (size_t i = 0; i < oldSize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
2.7 resize
注意事项：
1.分情况
（1）n < size()时
由于底层是原生指针因此我们可以直接改变指针的值，不需要循环pop_back()函数，可以直接_start + n
（2）n > size()时
复用reserve，因为reserve内部对于空间足够的情况不会处理，只有空间不足时reserve内部才会重新分配空间
2.参数类型的缺省值如何给：匿名对象
实现代码：
void resize(size_t n , const T& val = T())
{
if (n > size())
{
reserve(n);
for (size_t i = size(); i < n; i++)
push_back(val);
}
else
{
//删除
//for (int i = size(); i > n; i--)
// pop_back();
//我们可以直接改变指针
_finish = _start + n;
}
}
2.8 swap
注意：
1.我们想要调用库的swap函数，因此必须指明std命名空间来调用。
因为编译器在搜索时会先搜索到我们实现的vector类中的swap，然后编译器会报错参数不匹配。
调用代码：
void swap(vector<T>& v)
{
//错误写法
swap(_start, v._start);
swap(_finish, v._finish);
swap(_endofstorage, v._endofstorage);
}
void testvector4()
{
vector<int> v(10, 1);
v.PrintVector();
vector<int> v1(20, 2);
v1.swap(v);
}
程序报错：
实现代码：
void swap(vector<T>& v)
{
//注意：不能直接写成swap(_start,v._start);
//swap(_start, v._start);
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
3. vector的迭代器失效
3.1 insert造成的迭代器失效
在vector中insert导致的迭代器失效多为扩容导致的问题。
案例：往容量已满的vector容器中插入值（实现时默认为4个空间）
void testvector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = v.begin();
cout << *it << endl;
v.insert(it, 40);
cout << *it << endl;
}
输出结果：
分析问题
造成这种问题的原因是因为在insert函数执行时进行了扩容操作，原有的空间被释放，但是it仍然指向被释放的空间，因此打印出来为随机值。
解决方案
错误思路：
可能会有人说，在函数参数部分传引用，这样就可以让迭代器自动更新，但是如果传引用的话，则无法将begin()，end()直接作为参数传递，因为它们的返回值是临时变量，具有常性，如果需要接收则需要在参数部分增加const来修饰，但是增加const之后就不能修改。
正确思路：
stl库在设计insert函数时增加返回值，从而便于使用返回值来更新迭代器。更新迭代器
3.2 erase造成的迭代器失效
案例：删除值为偶数的位置
场景一：
//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
it++;
}
v.PrintVector();
输出结果：正确
场景二：
//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
it++;
}
v.PrintVector();
输出结果：结果不符合预期，有跳过
场景三：
//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
it++;
}
v.PrintVector();
输出结果：编译器报错
我们从画图的过程来理解为什么相似的几段代码但是结果却不相同。
图解
场景一：
场景二：
场景三：
分析问题
出现上面的原因就是因为迭代器it没有及时更新还在使用所导致的。
解决问题
stl库在设计时erase是有返回值的，其返回值为正确的迭代器，因此每次使用后可以通过接收返回值来更新迭代器。
修改后代码：
//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
it++;
}
v.PrintVector();
总结
vector的insert和erase操作都可能使迭代器失效。
迭代器失效以后，不要直接使用，如果需要使用应该按照规则重新更新后使用。
以上是本次所有内容，如有可以提升的地方，希望各位佬可以指点，谢谢观看。
