一、vector成员变量
库里实现用的就是这三个成员变量,咱们实现跟库里一样,
namespace myvector {
template<class T>
class vector
{
public:
//vecttor的迭代器是原生指针
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start=nullptr;//数据块的开始--------------_begin
iterator _finish=nullptr;//有效数据的尾-------------_end
iterator _end_of_storage=nullptr;//存储容量的尾-----_capacity
}
这里把T*重命名为iterator,因为vector的迭代器就是原生指针,所以直接用就行。
二、默认成员函数
1.构造函数
//我们在成员变量声明处给了缺省值,这里就可以不用初始化了
vector()
{}
//T()是匿名对象,初始化n个value
vector(size_t n, const T& value = T())
{
resize(n, value);
}
/*
* 理论上讲,提供了vector(size_t n, const T& value = T())之后
* vector(int n, const T& value = T())就不需要提供了,但是对于:
* vector<int> v(10, 5);
* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型
* 就不会走vector(size_t n, const T& value = T())这个构造方法,
* 最终选择的是:vector(InputIterator first, InputIterator last)
* 因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int
* 但是10和5根本不是一个区间,编译时就报错了
* 故需要增加该构造方法
*/
//初始化 n个value
vector(int n, const T& value = T())
{
resize(n, value);
}
// 若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)只能是vector的迭代器
// 重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器
//初始化一段空间
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
2.拷贝构造和赋值运算符重载
//拷贝构造
vector(const vector<T>&v)
{
_start = new T[v.capacity()];
//vector是深拷贝,但是vector空间上存一个开空间的自定义类型数组,例:string的数组
//使用memcpy导致string对象的浅拷贝
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < v.size(); i++)
{
//假设T是string类型,这里调用string的赋值运算符重载,是深拷贝
_start[i]=v._start[i];
}
_finish = v.size() + _start;
_end_of_storage = v.capacity() + _start;
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
void swap(vector<T>& v)
{
std::swap(v._start, _start);
std::swap(v._finish, _finish);
std::swap(v._end_of_storage, _end_of_storage);
}
这里赋值运算符重载的形参是传值, 会调用拷贝构造出一个临时对象v,(深拷贝),然后用库里的swap把v的参数交换,交换完后待赋值运算符重载结束后会自动析构掉临时对象v。
- memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。
结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。
3.迭代器
//vecttor的迭代器是原生指针
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.析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage;
}
}
为空就没有可释放的资源。
三、空间增长接口
size_t capacity()const
{
return _end_of_storage - _start;
}
size_t size()const
{
return _finish - _start;
}
void reserve(size_t n)
{
//只扩容,不缩容
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
//如果_start为空,直接把tmp赋值给_start就行,不用释放旧空间
if (_start)
{
//vector是深拷贝,但是vector空间上存一个开空间的自定义类型数组,例:
//string的数组
//使用memcpy导致string对象的浅拷贝
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i=0;i<size();i++)
{
//假设T是string类型,这里调用string的赋值运算符重载,是深拷贝
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = tmp + sz;
_end_of_storage = tmp + n;
}
}
void resize(size_t n, const T& value = T())
{
//三种情况
//n<size
if (n < size())
{
iterator pos = _start + n;
while (pos != _finish)
{
erase(pos);
}
}
//n>容量,要扩容
else if (n > size())
{
//n大于size但小于容量
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
push_back(value);
}
}
}
这里只要注意临界条件就行了。
四、增删接口
void push_back(const T& value)
{
满了,扩容
//if (_finish == _end_of_storage)
//{
// size_t newcapacity = capacity() < 4 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
//*_finish = value;
//++_finish;
insert(_finish, value);
}
void pop_back()
{
erase(_finish-1);
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish);
// 空间不够先进行增容
if (_finish == _end_of_storage)
{
//size_t size = size();
size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;
reserve(newCapacity);
// 如果发生了增容,需要重置pos,防止迭代器失效
pos = _start + size();
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
// 返回删除数据的下一个数据
// 方便解决:一边遍历一边删除的迭代器失效问题
iterator erase(iterator pos)
{
// 挪动数据进行删除
iterator begin = pos + 1;
while (begin != _finish) {
*(begin - 1) = *begin;
++begin;
}
--_finish;
return pos;
}
五、其他
T& front()
{
return *_start;
}
T& back()
{
return *(_finish - 1);
}
T& operator[](size_t pos)
{
//判断pos位置合法性
assert(pos < size());
return *(_start + pos);
}
const T& operator[](size_t pos)const
{
//判断pos位置合法性
assert(pos < size());
return *(_start + pos);
}
总结
vector实现只要注意迭代器失效的问题和拷贝不能用memcpy这俩问题。
蟹蟹观看!点赞!关注!收藏!评论!一键三连!