STL中vector实现——简单易懂版
本章内容
模拟实现 vector 的部分重要功能
1.迭代器的引入
vector 就是一个动态数组
动态大小：vector的大小可以根据需要自动增长和缩小
连续存储：vector中的元素在内存中是连续存储的，这使得访问元素非常快速
可迭代：vector可以被迭代，你可以使用循环（如for循环）来访问它的元素
元素类型：vector可以存储任何类型的元素，包括内置类型、对象、指针等
1.1 之前写法
学数据结构的时候，我们C表示顺序表都是这样写的
typedef int DataType; struct SeqList { DataType* a; int size; int capacity; };a指向申请的空间
size代表元素个数
capacity 代表申请的元素个数，也就是当前申请的容量可以存多少个元素
1.2 STL库中的写法
C++中有了模板就不需要再去写typedef int DataType;
直接写成类模板，使用类时给明参数即可template<class T> class vector { public: typedef T* iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; }
_start 指向第一个位置
_finish指向最后有效元素的下一个地址
_end_of_storage指向最后一个可存储元素的下一个地址
2.默认成员函数
常用的STL库中的vector构造如下：
vector<int> v1;
vector<int> v2(v1);
vector<int> v3(v1.begin(), v1.end());
vector<int> v4(5,10);
vector<int> v5 = { 1,2,3,4,5 };
2.1构造与拷贝构造
默认构造
什么都不需要传递，三个成员变量都指向nullptr即可
所以我们可以直接给缺省值
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
拷贝构造
因为编译器默认生成的拷贝构造都是浅拷贝，所以拷贝构造需要我们自己写
先学习思路，reserve，push_back后面实现
实现思路：
1.直接开和v一样大的空间
1.再把v的元素全部尾插进要构造的类中就可以了
vector(const vector& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
如果我们写了拷贝构造的话，编译器就不会生成默认的构造函数了，但有一种方法可以强制编译器调用默认构造
vector() = default;
构造函数的重载
vector<int> v3(v1.begin(), v1.end());
vector<int> v4(5,10);
vector<int> v5 = { 1,2,3,4,5 };
1.迭代器版本
2.初始化n个相同类型的值
3.用 {} 初始化
它们实现思路大致相同
// 1
template<class IntputIterator>
vector(IntputIterator begin, IntputIterator end)
{
while (begin != end)
{
push_back(*begin);
++begin;
}
}
// 2.
vector(size_t n, const T& x = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(x);
}
}
// 调用 vector<int> v1(10,5); 这句话可能会调用到
//template<class IntputIterator>
//vector(IntputIterator begin, IntputIterator end)
// vector<int> v1(10,5); 它的目的是使 vector中有10个值，每个值都是5
//要解决此问题 需要在下面 定义 vector(int n, const T& x = T())
//编译器在调用函数时 会调用最合适它的函数，如果没有合适的函数才回去考虑使用模板
vector(int n, const T& x = T())
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(x);
}
}
// 3.
vector(initializer_list<T> il)
{
reserve(it.size());
for (auto e : il)
{
push_back(e);
}
}
1.
template< class IntputIterator>
IntputIterator 可以接收任意类型自定义类型的迭代器
例如可以用链表初始vector
2.
vector(size_t n, const T& x = T())
用n个T类型的值初始化 vector
1.如果是自定义类型调用它的默认构造
2.那如果是 内置类型 呢？？？？
3.C++支持内置类型也有自己的 默认构造
缺省值给一个匿名对象的默认构造
所以可以C++有如下代码：
什么是 initializer_list
答：它是可以接收 { } 内容的类模板
它的成员函数如下：
initializer_list 内成员变量只有两个
一个指向{}的开头位置的地址，一个指向结束位置的下一个地址
2.2拷贝赋值
传统写法
释放原空间，申请新空间，再把需要拷贝的内容拷贝过去
写起来相对后面这种方法比较繁琐
vector<T>& operator= (const vector& v)
{
if (this != &v)
{
delete[] _start;
_start = new T[v.capacity()];
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
memcpy(_start, v._start, sizeof(T) * v.size());
}
return *this;
}
方法二：
拷贝赋值函数参数列表中采用传值拷贝
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator= (vector v)
{
if (this != &v)
{
swap(v);
}
return *this;
}
画图解释如下
2.3析构函数
析构函数也是的我们手动去释放内存的
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
3.增删查改功能
3.1插入
push_back 尾插一个元素
插入元素就需要扩容
扩容时需要注意一个 迭代器失效的问题
这个问题我会再写一篇文章来阐述这个问题，这篇文章主要是vector的实现
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t oldsize = size();
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
insert的实现
C++中vector的插入只提供了迭代器的版本
也存在迭代器失效问题
iterator insert(iterator pos ,const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *(end);
--end;
}
*pos = x;
++_finish;
return pos;
}
3.2删除
尾删
void pop_back()
{
assert(_start != _finish);
--_finish;
}
删除指定位置的元素
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *(it);
it++;
}
--_finish;
}
4.为什么STL中vector没有find函数？
原因是STL把find函数写在了algorithm文件下。
find是模板函数 InputIterator 类型来接收传过来的迭代器。
一劳永逸，体现了程序高内聚
无论vector还是list，都可以使用find。
5.🔥🔥迭代器失效场景（重点）
实现时会失效的函数
reserve
假设现在vector里已经有四个数了，现在还要插入一个数，但是空间不够了需要扩容。扩容后要达成下面的场景。
代码实现
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t oldsize = size();
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
}
注意事项：
size（）的实现如下
size_t size() const
{
return _finish - _start;
}
这里一定要记录旧空间的size
因为如果我们先执行 _start = tmp;
再执行 _finish = _start + size（）;
此时的size（）返回的时旧 _finish - 新_start 的值
所以正确写法：_finish = _start + oldsize;
insert
STL中的 insert 只支持迭代器版本
iterator insert(iterator pos ,const T& x)
假设现在有四个值，要在pos位置插入一个值，插入需要扩容。
要求插入结果如下
代码实现
iterator insert(iterator pos ,const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *(end);
--end;
}
*pos = x;
++_finish;
return pos;
}
注意事项：
如果需要扩容的话，还是得更新pos，使pos指向新空间的对应位置 。
所以需要提前记录pos与_start的位置关系。
使用后会导致迭代器失效的函数
insert
insert的pos是传值调用，所以我们扩容后修改的是函数内的pos。
因为旧空间释放导致外部的pos失效。
可能会有人说这个pos使用引用就不会有迭代器失效的问题了
但是程序会报错
begin返回的时临时对象，临时对象具有常性，不可以被改变
所以这里只能使用传值调用。
我们使用时就得直接去注意这些问题。
erase
erase导致的迭代器失效有两种情况
- 有的编译器删除元素后可能会进行缩容，缩容的话pos就会失效
- 如果删除的是最后一个元素，我们认为这个元素已经被删除，不能被访问，所以就认为它失效
但这样还是可以访问，所以我们在使用erase时不要这样使用
vs2019不允许这样使用：
原文地址：https://blog.csdn.net/sgbscx/article/details/143865020
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！