STL中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());//如果vector中存的是内置类型，memcpy可以完成拷贝//如果vector中存的是自定义类型，memcpy只能是浅拷贝for(size_t i = 0; i < oldsize(); ++i){tmp[i] = _start[i];	}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;
}

如上图用memcpy，下面代码测试结果是否正确
v1，v2用的是STL库中的vector
v3，v4是memcpy实现的reserve

int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<string> v2;v2.push_back("aaaaaaaaaaaaaaaaaaaa");v2.push_back("bbbbbbbbbbbbbbbbbbbb");v2.push_back("cccccccccccccccccccc");v2.push_back("dddddddddddddddddddd");v2.push_back("ffffffffffffffffffff");for (const auto& e : v1){cout << e << ' ';}cout << endl;for (const auto& e : v2){cout << e << ' ';}cout << endl;cx::vector<int> v3;v3.push_back(1);v3.push_back(2);v3.push_back(3);v3.push_back(4);v3.push_back(5);cx::vector<string> v4;v4.push_back("aaaaaaaaaaaaaaaaaaaa");v4.push_back("bbbbbbbbbbbbbbbbbbbb");v4.push_back("cccccccccccccccccccc");v4.push_back("dddddddddddddddddddd");v4.push_back("ffffffffffffffffffff");for (const auto& e : v3){cout << e << ' ';}cout << endl;for (const auto& e : v4){cout << e << ' ';}cout << endl;return 0;
}

输出结果：
可以看到，使用memcpy浅拷贝是不能完成vector< string >的拷贝功能的

解析如下：

正确写法：

使用赋值
内置类型，直接拷贝
自定义类型，调用它自己的赋值拷贝
指定要类型没有内存申请，就是浅拷贝。如果有内存申请，就是深拷贝

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导致的迭代器失效有两种情况

1. 有的编译器删除元素后可能会进行缩容，缩容的话pos就会失效
2. 如果删除的是最后一个元素，我们认为这个元素已经被删除，不能被访问，所以就认为它失效

但这样还是可以访问，所以我们在使用erase时不要这样使用

vs2019不允许这样使用：