C++的STL简介（三）

目录

1.vector的模拟实现

 1.1begin（）

 1.2end（）

 1.3打印信息

 1.4 reserve（）

 1.5 size（）

 1.6 capacity（）

 1.7 push_back()

 1.8[ ]

 1.9 pop_back()

 1.10 insert（）

 1.11拷贝构造

1.12析构函数

 1.13 =

 1.14chear

 1.15区间构造

 1.16默认构造

 2.完整代码

 3.迭代器失效问题

1.类似野指针

​编辑2.位置意义变了

C++ 中的 vector 是一种序列容器，它允许你在运行时动态地插入和删除元素。

vector 是基于数组的数据结构，但它可以自动管理内存，这意味着你不需要手动分配和释放内存。

与 C++ 数组相比，vector 具有更多的灵活性和功能，使其成为 C++ 中常用的数据结构之一。

vector 是 C++ 标准模板库（STL）的一部分，提供了灵活的接口和高效的操作。

基本特性:

• 动态大小：vector 的大小可以根据需要自动增长和缩小。
• 连续存储：vector 中的元素在内存中是连续存储的，这使得访问元素非常快速。
• 可迭代：vector 可以被迭代，你可以使用循环（如 for 循环）来访问它的元素。
• 元素类型：vector 可以存储任何类型的元素，包括内置类型、对象、指针等。

使用场景：

• 当你需要一个可以动态增长和缩小的数组时。
• 当你需要频繁地在序列的末尾添加或移除元素时。
• 当你需要一个可以高效随机访问元素的容器时。

1.vector的模拟实现

基本框架

namespace V
{template<class T>class vector{public:typedef T* iterator;typedef  const T* const_iterator;iterator _start=nullptr;//开始iterator _finish=nullptr;//存数据iterator _end_of_storage=nullptr;//结束};

 1.1begin（）

开始位置的迭代器

iterator begin(){return _start;}const_iterator begin() const{return _start;}

 1.2end（）

结束位置的迭代器

iterator end(){return _finish;}const_iterator end() const{return _finish;}

 1.3打印信息

template<class T>void print_vector(const  vector<T>& v){//没有实例化的类模板里面取东西,编译器不能区分这里const_iterator是类型还是静态成员变量typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";cout << endl;}}typename void print_vector(  vector<T>& v){vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";cout << endl;}}

 1.4 reserve（）

扩容

	void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_finish =  tmp + old_size();_start = tmp;_end_of_storage = _start + n;}}

 1.5 size（）

内容个数

size_t size(){return _finish - _start;}

 1.6 capacity（）

容量

size_t capacity(){return _end_of_storage - _start;}

 1.7 push_back()

尾插

	void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}

 1.8[ ]

下标访问

T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}bool empty(){return _start == _finish;}

 1.9 pop_back()

尾删

void pop_back(){assert(empty());--_finish;}

 1.10 insert（）

插入

	void insert(iterator pos, const T& x){if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finsh - 1;while (end>=pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}

 1.11拷贝构造

vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}

1.12析构函数

	~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}

 1.13 =

vector<T>& operator=(const vector<T>& v)
{if (this != &v){chear();reserve(v.size());for(ayto& e:v){push_back(e);}}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=(vextor<T> v)
{swap(v);return *this;
}

 1.14chear

清除数据

	void clear(){_finish = _start;}

 1.15区间构造

	//类模板的成员函数还可以继续是函数模板//区间构造template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++firsh;}}

 1.16默认构造

n个T（）初始化

	vector(size_t n ,const T& val=T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

 2.完整代码

#include<iostream>
#include<assert.h>
#define _CRT_SECURE_NO_WARNINGS 1
using namespace std;
namespace V
{template<class T>class vector{public:typedef T* iterator;typedef  const T* const_iterator;vector(){}vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}template<class T>void print_vector(const  vector<T>& v){//没有实例化的类模板里面取东西,编译器不能区分这里const_iterator是类型还是静态成员变量typename vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";cout << endl;}}typename void print_vector(  vector<T>& v){vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";cout << endl;}}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_finish =  tmp + old_size();_start = tmp;_end_of_storage = _start + n;}}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}void clear(){_finish = _start;}
/*		vector<T>& operator=(const vector<T>& v){if (this != &v){chear();reserve(v.size());for(ayto& e:v){push_back(e);}}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<T> v){swap(v);return *this;}//类模板的成员函数还可以继续是函数模板//区间构造template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++firsh;}}vector(size_t n ,const T& val=T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}bool empty(){return _start == _finish;}void pop_back(){assert(empty());--_finish;}void insert(iterator pos, const T& x){if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end>=pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}private:iterator _start=nullptr;//开始iterator _finish=nullptr;//存数据iterator _end_of_storage=nullptr;//结束};}

 3.迭代器失效问题

1.类似野指针

最开始_finish=_start=_end_of_storage=0;经过扩容,_start已经不为nullptr了，用一个nullptr减一个地址，用扩容前的地址减去扩容后的地址，_finish访问后地址就类似野指针，本意是想_finish存储最后一个数据的地址，可是实际差强人意这段代码肯定有问题但是编译器不报错

 修正一下，用old_size存储相对位置在进行计算就更合理

	void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_finish =  tmp + old_size();_start = tmp;_end_of_storage = _start + n;}}

1.2

 扩容后，pos还指向旧空间，while循环end-pos次，迭代器失效

 任然是用相对位置

void insert(iterator pos, const T& x){if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finsh - 1;while (end>=pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}

  pos被释放后失效了虽然后面修正了形参的改变不影响实参实参仍然指向旧空间，访问旧空间，迭代器失效

2.位置意义变了