vector的底层实现与模拟

在这里插入图片描述

嗨喽大家好，时隔许久阿鑫又给大家带来了新的博客，关于vector的模拟实现，下面让我们开始今天的学习吧！

vector的底层实现与模拟

1.关于vector中的插入和删除

2. vector中的拷贝构造和赋值

3.vector的构造函数

4.关于vector中浅拷贝的问题

1.关于vector中的插入和删除

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}
size_t capacity()const
{return _end_of_storage - _start;
}size_t size()const
{return _finish - _start;
}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(_finish, x);
}T& operator[](size_t i)
{assert(i < size());return _start[i];
}void pop_back()
{_finish--;
}iterator insert(iterator pos, const T& x)
{//扩容会导致迭代器失效assert(pos >= _start);assert(pos <= _finish);int len = pos - _start;if (_finish == _end_of_storage){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;
}void erase(iterator pos)
{//erase也会导致迭代器失效vassert(pos >= _start);assert(pos < _finish);iterator end = pos;while (end <= _finish-2){*(end ) = *(end + 1);++end;}_finish--;
}

1.1 尾插和插入时，若需要扩容应该提前保存oldsize的值

在这里插入图片描述

我们需要注意的是：size（）返回的是_finish-_start的值，但是_start的地址再扩容后已经发生了变化，所以我们需要用oldsize记录下扩容前的对象个数，从而避免调用size（）

1.2 关于erase和insert中迭代器失效的问题

在这里插入图片描述

有些同学想通过传引用的方法，防止外面的实参迭代器失效
注意：若采用传引用的话，由于v1.begin（）是传值返回，需要调用拷贝构造，临时对象具有常性，所以pos就不能修改，所以无法完成insert成员函数的内部操作，所以不能利用传引用

在这里插入图片描述

string的插入也存在迭代器失效的场景，但大多数时候，string的插入是采用下标，所以平时不太研究string的迭代器失效的场景

在这里插入图片描述

在vs下，访问erase后失效的迭代器会直接崩溃，而在Linux下不会直接崩溃

2. vector中的拷贝构造和赋值

//强制编译器生成默认的
vector() = default;//v1(v3)
vector(const vector<T>& v){reserve(v.capacity());for (auto e:v){push_back(e);}
}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)
{//v3 = v1(this是v3的指针)this->swap(v);return *this;}

3.vector的构造函数

3.1迭代器区间初始化

类模板的成员函数，也可以是函数模板----（支持任意容器的迭代器区间初始化）

//构造函数不能显示的去调用，当一个对象进行实例化的时候
// **编译器会自动调用更匹配的构造函数进行初始化**
// 类模板的成员函数
// 函数模板 -- 目的支持任意容器的迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}
void Test_15()
{vector<int> v3(10,1);v3.insert(v3.begin() + 3, 10);for (auto ch : v3){cout << ch << " ";}cout << endl;vector<int> v4(v3.begin()+3, v3.end());for (auto ch : v4){cout << ch << " ";}cout << endl;string s("hello");vector<int> v5(s.begin(), s.end());for (auto ch : v5){cout << ch << " ";}cout << endl;}

3.2 n个val初始化

vector(size_t n, const T& val = T())//匿名对象
{T* tmp = new T[n];_start =_finish =  tmp;_end_of_storage = _start + n;
/*	reserve(n);*/for (int i = 0; i < n; i++){push_back(val);}
}vector(int n, const T& val = T())//给了一个重载的版本,用来解决编译器的匹配问题
{T* tmp = new T[n];_start = _finish = tmp;_end_of_storage = _start + n;
/*	reserve(n);*/for (int i = 0; i < n; i++){push_back(val);}
}

注意：如果没有第二个重载的版本，当遇到特定情况时，就会发生非法的间接寻址,因为在调用构造时，编译器会选择更对自己口味的构造函数，如果没有重载第二个版本，那么v3的构造就会匹配迭代器区间的初始化，从而造成非法的间接寻址。

在这里插入图片描述

3.3 initializer_list的初始化

在这里插入图片描述

库系统支持的一个类型initializer_list(和iterator有些类似，都是将某些特定功能封装成一个类)

这个类的对象有两个指针，支持范围for

vector(initializer_list <T> il)//采用列表进行初始化
{reserve(il.size());for (auto ch : il){push_back(ch);}}

在这里插入图片描述

关于花括号的初始化

在这里插入图片描述

4.关于vector中浅拷贝的问题

//判断是否扩容
void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];size_t oldsize = size();if (_start){/*for (int i = 0; i < size(); i++){push_back()}*///如果采用上述代码，对内置类型和值拷贝的对象没有影响for (int i = 0; i < size(); i++){tmp[i] = _start[i];//用的是string的赋值}delete[] _start;}_start = tmp;_finish = _start + oldsize;_end_of_storage = _start + n;}
}