vector模拟实现
- 一、看源代码
- 简单实现
- 1. push_back
- capacity(容量)
- size
- reserve(扩容)
- operator[ ] (元素访问)
- 2. pop_back
- 3. itorator(迭代器)
- 4.insert & erase (头插头删)
- 5. 拷贝构造和析构函数
- default关键字(强制编译器生成)
- 其他问题
一、看源代码
- 在我们自己实现 vector 的时候,我们可以参考 vector 的源代码
- 大致功能初步了解
-
- 成员变量
-
- 核心成员函数
- 根据名字连蒙带猜,通过时间看源码细节确认
我们自定义的成员变量:
template<class T>
class vector
{
public:private:T* _a;size_t _size;size_t _capacity;
};
修改后:
namespace bit //同一个域内,就不会和编译器里面的vector弄混
{template<class T>class vector{public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}
简单实现
前情提要:我们分离定义不分离是因为分离会出现连接问题,这个我们后面会提到
1. push_back
下面是push-back的大致框架:
void push_back(const T& x)
{//如果满了就扩容if(_finish == _end_of_storage){//扩容}
}
注意:在这里我们还要实现三个前提函数:capacity()、size()、reserve()
capacity(容量)
size_t capacity()
{return _end_of_storage - _start;
}
size
size_t size()
{return _finish - _start;
}
reserve(扩容)
void reserve(size_t n)
{//直接扩容if (n > capacity()){T* tmp = new T[n]; //开辟空间memcpy(tmp, _start, sizeof(T) * size()); //拷贝delete[] _start; //释放旧空间_start = tmp; //指向新空间}_finish = _start + size();_end_of_storage = _start + n;
}
⭐通过以上代码,我们就可以开始实现👇
void push_back(const T& x)
{//如果满了就扩容if (_finish == _end_of_storage){//如果capacity 是 0 那么就给四个空间,不是就乘二倍size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;
}
operator[ ] (元素访问)
T& operator[](size_t i)
{assert(i < size());//断言检查越界情况return _start[i];
}
问题一:测试会发现,我们没有包iostream头文件,所以cout无法使用
- 这里就涉及到一个问题 头文件 .h 在 .cpp 文件里面会展开
所以当我们在Test.cpp里面展开vector.h时,又可以使用了
- 因为展开时他会向上查找
但但但是,又有一个问题,运行报错了
- 空指针问题,通过测试,我们可以发现的是,size算法出现问题
start 是新的 但是 finish 是旧的
当我们重新扩容之后,_start == tmp , 而_ finish还是原来的那个t
- 修改后代码如下:
void reserve(size_t n)
{//直接扩容if (n > capacity()){size_t oldsize = size();T* tmp = new T[n]; //开辟空间if (_start) {memcpy(tmp, _start, sizeof(T) * size()); //拷贝delete[] _start; //释放旧空间 }_start = tmp; //指向新空间_finish = tmp + oldsize;_end_of_storage = _start + n;}}
2. pop_back
那么这个就比较简单了,代码实现如下👇:
void pop_back()
{assert(size() > 0);--_finish
}
3. itorator(迭代器)
- 在没有迭代器的情况下时,我们是不能使用范围for的
迭代器代码实现👇
typedef T* iterator;
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
- 当然,也有const迭代器
是指迭代器指向的内容不可修改
typedef const T* const_iterator;iterator begin() const
{return _start;
}
iterator end() const
{return _finish;
}
4.insert & erase (头插头删)
void test_vector3()
{bit::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin(), 0); //头插v1.erase(v1.begin()); //头删
}
运行结果:
⭐insert的的实现
void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}
注意:这里的扩容会导致迭代器失效,本质上也是一种野指针,pos指向的位置已经失效了
- 所以我们只需要将pos指向新空间对应的位置就好
修改后的insert👇
void insert(iterator pos, const T& x)
{if (_finish == _end_of_storage){size_t len = pos - _start; //加上这一句计算pos的位置size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len; //重置为新pos的位置}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}
- 紧接而来的问题,当我们调用自己写insert时,pos会失效,使得在后面不能重新在调用pos
insert(pos,100);
erase的实现代码👇
void erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it != _finish){*(it - 1) = *it;**it;}--_finish;
}
- 当我们使用erase但是也会出现失效的可能性,这也说明迭代器失效不只是野指针的问题
- 这取决于VS的编译器对于iterator,我们出了作用域时,会类似标记为 false ,此时再次调用,就会报错
5. 拷贝构造和析构函数
- 拷贝构造
问题一:如果我们不写拷贝构造的话,在VS里面默认是什么
在内置类型里面,我们完成的是值拷贝,也就是所谓的浅拷贝,这不是我们所需要的
拷贝构造函数代码如下👇
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 = v3
vector<T>& operator=(vector<T>& v)
{this->swap(v);return *this;
}
//v2(v1)
vector(const vector<T>& v)
{for (auto e : v){push_back(e);}
}//但是现在并没有写构造
- 但是在这里并没有运行,所以在这里我们需要提前了解一下关键字
default关键字(强制编译器生成)
//强制编译器生成默认的
vector() = dafault;
析构函数代码如下👇
~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}
}
其他问题
- 有人在编译的时候可能会出现内部编译器出错
- 因为有模板的原因,编译器报错比较混乱
- 一般都是少了分号的原因
- 可以用分段注释的方法来解决