目录
vector(size_t n, const reference val = type_value());
vector(const_iterator first, const_iterator end);(深拷贝)
reference operator[](size_t n);
vector& operator=(const vector& v);(深拷贝)
iterator insert(iterator position, const_reference val);
iterator erase(iterator position);
3.在每一个元素前插入当前元素值的2倍并且删除能被二整除的数
一.框架
1.函数与成员声明
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//模拟实现vector
namespace zsl
{
template<class T>
class vector
{
public:
//类型说明
typedef T type_value;
typedef type_value& reference;
typedef const type_value& const_reference;
typedef type_value* iterator;
typedef const type_value* const_iterator;
//构造函数
vector()
vector(size_t n, const_reference val = type_value());
vector(int n, const_reference val = type_value());
vector(const vector<type_value>& v);
//迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
//operator[]/operator=
reference operator[](size_t n);
const_reference operator[](size_t n) const;
vector& operator=(const vector& v);
//swap
void swap(vector<type_value> v);
//容量/数据个数
size_t capacity();
size_t capacity() const;
size_t size();
size_t size() const;
//reserve/resize
void reserve(size_t n);
void resize(size_t n, const_reference val = type_value());
//尾插/尾删
void push_back(const_reference val);
void pop_back();
//front/back
reference front();
const_reference front() const;
reference back();
const_reference back() const;
//插入/删除
iterator insert(iterator position, const_reference val);
iterator erase(iterator position);
~vector();
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}在STL源码中, vector数组并不是我们熟悉的在数据结构中的顺序表那样的形式实现的, 其属性而是用三个iterator定义的变量
_start指向首端,
_finish指向有效数据末端,
_end_of_storage指向整个vector末端
2.三个概念
vector是一个类模板, 本质是模板
vector<int>/vector<string>/vector<vector<int>>是模板类, 本质是类
vector<int> v/vector<vector<int>> vv是模板类实例化的类对象, 本质是对象
二.常用接口
以下讲解的描述均采用以下格式
????????1.函数声明
????????2.参数解释
????????3.函数定义
????????4.重点摘要
1.构造函数
vector();
vector()
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr) {}vector(size_t n, const reference val = type_value());
第一个参数: size_t本质是unsigned int类型, 无符号整数, 初始化的元素个数
第二个参数: reference是type_value&类型, type_value是T类型, T是模板参数, 并且有缺省值, type_value()是一个调用T的default构造, 实例化出的匿名对象, 仅仅用来赋值形参, 使用完立刻释放
vector(size_t n, const_reference val = type_value())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
for (int i = 0; i < n; i++)
{
push_back(val);
}
}vector(int n, const_reference val = type_value())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
for (int i = 0; i < n; i++)
{
push_back(val);
}
}如果T是int类型呢? int()代表什么呢?
答: C++中为了内置类型与自定义类型的兼容性, 内置类型也可以有int()这样的形式, int a = int()本质就是int a = 0
vector(const_iterator first, const_iterator end);(深拷贝)
两个参数是一个迭代器区间, 将这个迭代器区间拷贝到*this
如果传入的是v.begin() v.end()可以视为拷贝构造
在STL中给出的是这种形式, 但是会与vector(int n, const_reference val = type_value())发生调用错误的问题
假设我vector<int> v(5, 10), 这两个参数都是int类型, 更符合模板那个函数, 但我明显不是去调用InputIterator那个
所以只要给出一个函数重载的版本, 上面已经给出了
vector(int n, const_reference val = type_value())
template <class InputIterator>
vector(InputIterator first, InputIterator end)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
while (first != end)
{
push_back(*first);
++first;
}
}vector(const vector& v);(深拷贝)
第一个参数: 被拷贝的vector对象v, 将v以深拷贝的形式拷贝到*this
//方式一
vector(const vector<type_value>& v)
{
_start = new type_value[v.size()];
//采用深拷贝
if (v.size() != 0)
{
for (size_t i = 0; i < v.size(); i++)
{
*(_start + i) = *(v._start + i);
}
}
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}//方式二
vector(const vector<type_value>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
for (size_t i = 0; i < v.size(); i++)
{
push_back(v[i]);
}
}//方式三
vector(const vector& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
vector<type_value> copy(v.begin(), v.end());
swap(copy);
}这里涉及深浅拷贝问题, 在方式一中是不可以使用memcpy来将v内的数据拷贝到*this中的, 因为memcpy的本质是字节拷贝(浅拷贝)
下面采用了循环遍历, 使用赋值的方式(这里的operator=是我们自己实现的, 是深拷贝)
当我们的模板类是vector<int>时memcpy似乎没有问题, 因为数组内的元素都是内置类型, 值拷贝是可以解决的
但当我们的模板类是vector<vector<int>>时, 数组内的每一个元素都是自定义类型, 也就是说必须要将每个vector<int>以深拷贝的形式拷贝出去, 即使用我们自己实现的operator=
2.迭代器以及其他接口
iterator
迭代器在vector中其实就是指针
typedef T type_value;
typedef type_value* iterator;
typedef const type_value* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
void swap(vector v);
void swap(vector& v)
{
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}cpacity/size
size_t capacity()
{
return _end_of_storage - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size()
{
return _finish - _start;
}
size_t size() const
{
return _finish - _start;
}front/back
reference front()
{
if (_start)
return *_start;
}
const_reference front() const
{
if (_start)
return *_start;
}
reference back()
{
if (_finish)
return *_finish;
}
const_reference back() const
{
if (_finish)
return *_finish;
}析构函数
~vector()
{
delete[] _start;
_finish = _end_of_storage = nullptr;
}3.运算符重载
reference operator[](size_t n);
typedef type_value& reference;
typedef const type_value& const_reference;
以引用的形式返回, 代表接收的返回值是可以直接修改的
reference operator[](size_t n)
{
return *(_start + n);
}
const_reference operator[](size_t n) const
{
return *(_start + n);
}vector& operator=(const vector& v);(深拷贝)
//方式一
vector& operator=(const vector& v)
{
iterator tmp = new type_value[v.size()];
if (v._start)
{
//采用深拷贝(不可使用memcpy)
for (size_t i = 0; i < v.size(); i++)
{
*(tmp + i) = *(v._start + i);
}
delete[] _start;
}
_start = tmp;
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
return *this;
}深拷贝问题, 与上面的拷贝构造相同, 不可使用memcpy, 而是循环遍历, 如果每个元素是自定义类型则调用其自定义类型的operator=
//方式二
vector& operator=(const vector& v)
{
//利用拷贝构造
vector<type_value> tmp(v);
//利用swap
swap(tmp);
return *this;
}以"老板"的方式, 让tmp这个打工人去调用拷贝构造, 以深拷贝的形式构造出tmp, 然后全部和*this交换一下
3.两种扩容
reserve(深拷贝)
void reserve(size_t n)
{
//需要扩容
if (n > capacity())
{
int sz = size();
iterator tmp = new type_value[n];
//对于tmp中的元素的赋值采用深拷贝(不可使用memcpy这是一种浅拷贝的形式!)
if (_start)
{
for (size_t i = 0; i < size(); i++)
tmp[i] = _start[i];
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}1.开辟新空间
2.拷贝旧数据(必须深拷贝)
3.释放旧空间
但要注意, 一定要在释放旧空间之前将旧空间的数据个数size()保存起来
然后才能将新开辟的空间的_finish属性赋值为_start+sz, 否则size()将会发生错误
本质原因是size的内部实现是指针-指针, 而新的finish并没有给出赋值, 此时还未nullptr,
新开辟的空间中, size()函数并不能算出sz
resize
void resize(size_t n, const_reference val = type_value())
{
//对于resize而言分三种情况
//n > capacity - 扩容 + 初始化(新增元素)
//n <= capacity && n > size - 初始化(新增元素)
//n <= size - 删除元素
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
for (size_t i = size(); i < n; i++)
{
*_finish = val;
++_finish;
}
}
else if (n < size())
{
_finish = _start + n;
}
}4.尾插尾删
push_back
void push_back(const_reference val)
{
//判断是否需要扩容
if (capacity() == size())
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
//插入数据
*_finish = val;
++_finish;
}pop_back
void pop_back()
{
if (_finish)
--_finish;
}三.迭代器失效
1.迭代器失效的原因
迭代器失效有三种原因
第一种: 扩容
第二种: 缩容
第三种: 迭代器不再指向原数据
扩容与缩容的本质都是开辟了新空间, 旧空间被释放, 导致原迭代器成为野指针的问题
2.insert&&erase
iterator insert(iterator position, const_reference val);
第一个参数: 是一个迭代器, 一般通过algorithm中的find找到之后传入pos
第二个参数: 要插入的元素, 插入到迭代器指向的位置
iterator insert(iterator position, const_reference val)
{
if (capacity() == size())
{
//扩容
//解决扩容带来的迭代器失效问题
size_t distance = position - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
position = _start + distance;
}
iterator it = end();
while (it != position)
{
*it = *(it - 1);
--it;
}
*position = val;
++_finish;
return position;
}iterator erase(iterator position);
第一个参数: 删除迭代器指向的位置的元素(通常配合algorithm中的find使用)
iterator erase(iterator position)
{
if (_start)
{
iterator it = position;
while (it != end())
{
*it = *(it + 1);
++it;
}
--_finish;
}
return position;
}为何插入与删除都要设置返回值呢?
本质原因就是为了防止迭代器失效(野指针)问题而导致进程崩溃
insert与erase的使用规范: 每一次insert或erase之后, 都要用迭代器接收其返回值, 防止迭代器失效
3.在每一个元素前插入当前元素值的2倍并且删除能被二整除的数
void test_vector()
{
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 pos = v.begin();
while (pos != v.end())
{
pos = v.insert(pos, *pos * 2);//pos每次接收返回值, 防止迭代器失效,
//如果不接收则遇到需要扩容的情况就会发生迭代器失效从而发生野指针问题导致进程崩溃
pos += 2;//由于pos指向插入位置, 原指向的数据向后挪动一个, 所以每次pos跳过两个元素
}
for (auto& elem : v)
{
cout << elem << " ";
}
cout << endl;
cout << "-----------" << endl;
vector<int>::iterator pos2 = v.begin();
while (pos2 != v.end())
{
if (*pos2 % 2 == 0)
pos2 = v.erase(pos2);//这里同样使用pos2接收返回值
//但vector中的erase在删除数据不缩容的情况下其实并不会产生野指针
//但对于迭代器失效的定义是只要迭代器不指向原位置, 就认为是迭代器失效!为什么要这么定义呢?
//因为vector中erase不产生野指针的本质原因是数组是连续的, 那如果是链表erase函数就一定会发生迭代器失效
//所以对于迭代器失效的定义就定义为: 只要迭代器不指向原位置, 就认为是迭代器失效
else
++pos2;
}
cout << "-----------" << endl;
for (auto& elem : v)
{
cout << elem << " ";
}
cout << endl;
}