文章目录
一、vector中常用类成员
namespace sjj//自定义命名空间与标准库中的以区别开来
{
template<class T>//类模板
class vector
{
public:
typedef T* iterator; //类型指针
typedef const T* const_iterator;
vector(); //构造函数1
template<class InputIterator>;//用一段迭代器区间去初始化，为了支持任意类型，用到了模板
vector(InputIterator first, InputIterator last);//构造函数2
vector(const vector<T>& v); //拷贝构造函数
vector<T>& operator=(vector v); //赋值运算符重载
~vector(); //析构函数
//迭代器相关的函数
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end()const;
//容量大小相关的函数
size_t size()const;
size_t capacity()const;
bool empty();
//扩容相关的函数
void reserve(size_t n);
void resize(size_t n, const T& val = T());
//插入数据相关的函数
iterator insert(iterator pos, const T& x);//在pos位置之前插入数据x
void push_back(const T& x); //尾插
//删除数据相关的函数
void pop_back();
iterator erase(iterator pos);
//下标访问相关的函数
T& operator[](size_t i);
const T& operator[](size_t i)const;
//其他函数
void Swap(vector<T>& v);
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
二、vector的底层结构
我们就用这三个私有成员来模拟实现我们的vector
iterator _start;//开始位置的指针
iterator _finish;//结束的下一个位置的指针
iterator _endofstorage;//最大容量的下一个位置的指针
三、vector的默认成员函数
构造函数1—空构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
构造函数2—迭代器区间构造
//用一段迭代器区间去初始化，为了支持任意类型，用到了模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
拷贝构造函数
写法一：传统写法
//传统写法
vector(const vector<T>& v)
{
_start = new T[v.capacity()];
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
//void * memcpy ( void * destination, const void * source, size_t num );
memcpy(_start,v._start,sizeof(T)*v.size());
}
写法二：现代写法（更推荐）
//现代写法
vector(const vector<T>& v)//v是一个局部对象，出了作用域自动调用析构函数，不用管它
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());//利用迭代器区间进行初始化tmp
Swap(tmp);//交换this对象和tmp对象里面的值
}
赋值运算符重载
写法一：传统写法
//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己给自己赋值
{
delete[] _start; //释放原来的空间
_start = new T[v.capacity()]; //新开辟一块和容器v大小相同的空间
for (size_t i = 0; i < v.size(); i++) //将容器v当中的数据一个个拷贝过来
{
_start[i] = v[i];
}
_finish = _start + v.size(); //更新_finish
_endofstorage = _start + v.capacity(); //更新_endofstorage
}
return *this; //支持连续赋值，返回引用
}
写法二：现代写法(更加推荐)
vector<T>& operator=(vector v)
{
Swap(v);
return *this;//为了支持连续赋值，返回引用
}
析构函数
//析构
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
//全部置空
四、迭代器相关的函数
迭代器的分类
每一种迭代器都有着命名的规范，我们可以通过英文见名知意。
每一个迭代器越往上，权限就越小，我们可以把下面的迭代器看做父类，越往上的迭代器就是子类，它们有着父类的相关操作，但是我们传入迭代器时，只能传入权限大于等于当前迭代器的类型,例如我们reverse函数，需要传入双向迭代器，它可以传双向、随机，但是不能传权限比他小的迭代器，否则就会报错
通过查看文档我们可以看到一些函数需要传入迭代器类型：
迭代器对应的STL容器分类
举个例子：
int main()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(4);
v1.push_back(3);
v1.push_back(6);
sort(v1.begin(), v1.end());//正确使用
list<int> lt;
lt.push_back(1);
lt.push_back(3);
lt.push_back(2);
lt.push_back(4);
sort(lt.begin(),lt.end());//这里会报错
return 0;
}
list使用的是双向迭代器，sort要求传入随机迭代器，权限被缩小了，这是错误的使用
迭代器失效问题
问题引出：
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);//暴力检查
if (_finish == _endofstorage)//检查是否需要扩容
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//插入x
iterator end = _finish - 1;
while (end>=pos)
{
*(end +1) = *end;//前一个挪到后一个位置
--end;
}
*pos = x;
++_finish;
}
//测试
void test()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector<int>::iterator it = find(v.begin(), v.end(), 2);//找到值为2的位置
if (it != v.end())
{ // 如果insert中发生了扩容，那么会导致it指向空间被释放
// it本质就是一个野指针，这种问题，我们就叫迭代器失效
v.insert(it, 20);
}
for (auto e : v)
{
cout << e << " ";
}
}
怎么造成迭代器失效的呢？
原因：插入数据扩容的时候，我们定义了一个pos位置和end位置两个迭代器，新空间中，没有pos位置，但是原来的就空间还有个pos迭代器，任然指向一个已经被返还给操作系统的空间，但是最后居然*pos，解引用插入数据了，这显然是个野指针问题，存在着内存泄漏的风险。
改正解决迭代器失效的办法：在使用前，对迭代器重新进行赋值即可，我们需要更新一下扩容后的新的pos位置，并且我们在外部传参时，形参的改变不会影响实参，所以我们要传insert的pos位置的返回值，我们才能真正的删除pos位置的数据
//在pos位置之前插入数据x
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);//暴力检查
assert(pos <= _finish);
if (_finish == _endofstorage)//检查是否需要扩容
{
//扩容会导致pos位置迭代器失效，所以需要更新一下新位置的pos
size_t len = pos - _start;//记录一下pos距离_start位置的长度
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新一下扩容后的pos
}
//插入x
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;//返回新空间pos位置，因为形参的改变不会影响实参
}
同样erase中也存在着迭代器失效的问题
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
}
void test()
{
// 三种场景去测试
// 1 2 3 4 5 -> 正常
// 1 2 3 4 -> 崩溃
// 1 2 4 5 -> 没删除完
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(4);
v1.push_back(5);
//v1.push_back(5);
// 要求删除v1所有的偶数
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
v1.erase(it);
}
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
这里最大的问题就是，erase(it)后，it的意义已经变了，就是迭代器失效了，直接++it可能不导致一些意料之外的结果，如果是连续的偶数，会直接跳过后一个偶数，导致后一个偶数没有被删除掉。
正确的erase函数：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
return pos;//传pos位置的迭代器，防止迭代器失效
}
void test()
{
// 三种场景去测试
// 1 2 3 4 5 -> 正常
// 1 2 3 4 -> 崩溃
// 1 2 4 5 -> 没删除完
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(4);
v1.push_back(5);
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.erase(it);//传it位置的返回值，更新pos位置，这样就不会导致迭代器失效的问题了
}
else
{
++it;
}
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
迭代器相关的函数
其实vector中的迭代器就是原生类型的指针，只不过是经过typedef的
typedef T* iterator;
typedef const T* const_iterator;
begin()和end()函数
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const版本的begin()和end()函数
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
五、vector中容量大小相关的函数
我们这里就可以利用C语言学到的，两个指针的差值就是两个指针指向间的元素个数
size()函数
size_t size()const
{
return _finish - _start; //返回容器当中有效数据的个数
}
capacity()函数
size_t capacity()const
{
return _endofstorage - _start; //返回当前容器的最大容量
}
empty()函数
bool empty()const
{
return _start == _finish;
}
六、vector中扩容相关的函数
reserve()函数
void reserve(size_t n)
{
if (n > capacity())
{
//扩容
size_t sz = size();
T* tmp = new T[n];//新开一段空间
if (_start)
{
//void* memcpy(void* dest, const void* src, size_t count);
memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝，数据是内置类型不影响，是自定义类型会崩溃
delete[] _start;//释放掉原来的空间
}
_start = tmp;//交换指针指向
//扩完容以后_finsih _endodstorage也要处理一下
//要把原来的size保存一下
//_finish = _start + size();//size=finish-start start已经被更新了
_finish = _start + sz;
_endofstorage = _start + n;
}
}
使用memcpy拷贝问题
我们这里如果vector中存入的是string等自定义类型，使用memcpy进行拷贝，会出现什么问题呢？
int main()
{
sjj::vector <string> v;
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
v.push_back("11111111111111111");
return 0;
}
问题分析：
- memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
- 如果拷贝的是内置类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
- 插入的字符串长一些的话，就会出现乱码
结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
我们作出的改变就是不用memcpy，我们手动将数据一个一个的拷贝过去。我们能够间接调用string的赋值运算符重载，实现string的深拷贝。
出现乱码：VS下作了一个优化，当数据字长较小时(小于16时)，它会把数据存入一个char _Buf[16]的数组中，当数据长一点，它会把数据存入一个堆上开辟的大数组中char * _ptr中。
//代码修正
//memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝
for (size_t i = 0; i < sz; ++i)
{
//当T是int等内置类型，一个一个拷贝没有问题
//当T是string等内置类型，会去调用它的深拷贝
tmp[i] = _start[i];
}
resize()函数
我们这里需要考虑两种情况
第一种：
第二种：
void resize(size_t n, const T& val = T())// 给T()缺省值，int()
{
//分两种情况
//第一种n<size
//第二种n>capacity需要扩容
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
七、vector的增加数据相关的函数
push_back( )
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
//复用reserve函数
reserve(capacity() == 0 ? 4 : capacity() * 2);
//如果当前的capacity是0，扩到4，如果不是0，就扩2倍
}
*_finish = x;
++_finish;
}
insert()函数
//在pos位置之前插入数据x
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);//暴力检查
assert(pos <= _finish);
if (_finish == _endofstorage)//检查是否需要扩容
{
//扩容会导致pos位置迭代器失效，所以需要更新一下新位置的pos
size_t len = pos - _start;//记录一下pos距离_start位置的长度
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;//更新一下扩容后的pos
}
//插入x
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;//返回新空间pos位置，因为形参的改变不会影响实参
}
八、vector的删除数据相关的函数
pop_back()函数
void pop_back()
{
assert(_finish > _start);//暴力检查一下，防止越界
--_finish;//将_finish减减，相当于就把尾上的数据删除了
}
erase()函数
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;//pos的下一个位置记作begin
while (begin < _finish)
{
*(begin - 1) = *begin;//数据从后往前覆盖
++begin;
}
--_finish;//数据个数减一，finish也减一
return pos;//传pos位置的迭代器，防止迭代器失效
}
九、vector的查找数据相关的函数
operator[ ]下标查找
//普通版本
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
//const版本
const T& operator[](size_t i)const
{
assert(i < size());
return _start[i];
}
十、其他函数
swap()函数
void Swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}