迭代器区间构造函数
vector中可以用如下迭代器区间构造函数创建出一个vector类的对象
template <class InputIterator>
vector(InputIterator first, InputIterator last, const allocator_type& alloc=allocator_type());
也就是说vector类在设计的时候,本身需要一个模版参数,而且如果要使用上述迭代器区间构造,那么还需要在这个类的内部设计一个函数模版
其中vector类的需要的模版参数类型和这个函数模版需要的迭代器参数类型是不同的概念
迭代器区间构造带来的问题
编译器会在编译阶段根据函数模板在调用处的情况推导出实际的函数形参类型,关于函数模板,请看我的另一篇博客:C++函数模板
问题场景演示:
int main(){vector<int> v1(10, 1);
}
这个场景中,函数模版会针对v1处参数的情况推导合适的函数模板,有几个选项,
选项A
vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
选项B
vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}
选项C
template <class InputIterator>
vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}
}
最后main函数推导并调用的函数应该是选项B
引入 initializer_list 类型的对象
在C++11之后,可以使用 initializer_list 类型的对象构造 vector 对象以及给 vector 对象赋值,
① 赋值重载:vector& operator= (initializer_list<value_type> il);
② 构造函数:
vector (initializer_list<value_type>il, const allocator_type&alloc = allocator_type());
https://zhuanlan.zhihu.com/p/354588791,在这篇文章中说到,std::initializer_list 属于一个轻量级的类模板,其内部封装了iterator,还实现size, begin, end等方法。
值得注意的是,设计的顺序是:
reserve() -> push_back() -> 拷贝构造 -> initializer_list -> ② -> swap() -> ①
template<class T>
class vector{
public:size_t size() const{ return _finish - _start;}size_t capacity() const{ return _endofstorage - _start;}vector(const vector<T>& v){reserve(v.capacity());for(auto& e : v){push_back(e);}}/*篇幅有限,假设扩容之前存储的数据个数大于 1*/void reserve(int n){if(n > (_endofstorage - _start)){size_t old_size = size();T* newp = new T[n];for(int i = 0; i < old_size; i++){newp[i] = _start[i];}delete[] _start;_start = newp;_finish = _start + old_size;_endofstorage = _start + n; }}/*篇幅有限,如果发现空间不够,直接二倍扩*/void push_back(T val){if(_finish == _endofstorage){reserve(_finish == _start ? 4 : 2 * capacity());}*_finish = val;_finish++;}/*篇幅有限,不考虑空间配置器*/vector (initializer_list<T>il, const allocator_type&alloc = allocator_type()){reserve(il.size());for(auto& e : il){push_back(e);}}/*篇幅有限,左值引用的swap就不写在这里了*/void swap(vector<T>&& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector& operator=(initializer_list<T> il){swap(vector<T> (il));return *this;}/*其他成员*/
private:T* _start;T* _finish;T* _endofstorage;
};
对 reserve() 的说明
扩容需要进行如下操作:
1. 考虑什么时候开辟新空间,开辟多大的空间,这里采用两倍扩
2. 转移数据的方式:
这里使用了一个for循环,每次都通过赋值表达式将数据从旧空间中移到新空间中
赋值表达式保证了即使T是自定义类型,也可以通过赋值重载将数据深拷贝到新空间中
3. 删除旧空间:
这里简化了分析,假设旧数据都是通过new[n]开辟的空间,则自然能够使用delete[]释放
4. 管理新空间中的数据
在linux中,vector类中管理数据的成员是_start, _finish, _endofstorage,这三者本质
指针所以空间中的数据转移也应该更新这些指针变量的值
对push_back()的说明
每次尾插数据前,先判断是否需要扩容
对②的说明
构造函数一般都可以考虑一开始就调用reserve() 开辟足够大的空间,来保证不会频繁地扩容
对拷贝构造的说明
下面用现代写法(深拷贝的类都可以使用现代写法)进行交换时,需要调用拷贝构造创建匿名对象,而且将会用到swap的右值引用版本
对swap()的说明
1. 事实上需要重载两个版本:左值引用版本和右值引用版本
2. 调用std标准库中的交换函数时,应该指明std,保证不会因为局部优先而导致死循环调用
对①的说明
调用到这个赋值重载是在已经有了一个vector对象以后,
再用 initializer_list类型的对象进行更改,比如下面的场景
vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
v1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
所有深拷贝的类对应的所有赋值重载都可以使用现代写法,只要swap前,使用拷贝构造创建了一个中间对象。
所谓中间对象,既可以是函数传参时,形参对实参的拷贝, 也可以是专门创建的中间对象
vector 中insert() 和 erase() 方法的实现
insert()设计实现时需要考虑的问题
1. 扩容问题
2. 参数传入的问题
2.1 检查需要插入的位置是否越界
2.2 考虑插入位置相对于起始位置的偏移量
insert()的实现如下所示:
template<class T>
class vector{
public:void insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);if(_finish == _endofstorage){int depos = pos - _start;reserve(_start == _finish ? 4 : 2 * capacity();}iterator targetpos = _start + depos;iterator it = _finish - 1;while(it >= targetpos){*(it + 1) = *it;--it;}*(_start + depos) = val;++_finish;}/*其他成员*/
};
erase()设计实现时需要考虑的问题
1. 缩容问题
2. 检查需要插入的位置是否越界
template<class T>
class vector{
public:iterator insert(iterator pos){assert(pos < _finish && pos >= _start);iterator it = pos + 1;while(it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}/*其他成员*/
};
迭代器失效问题
在linux中,vector中的迭代器都是指针,由于扩容和缩容操作可能会改变原始对象中_start,_finish,_endofstorage这三个指针的指向,所以这些一旦调用insert或erase方法,之前定义的迭代器将会失效。以下是失效场景的演示,调用 insert 方法之后,it 这个指针不能直接解引用使用
迭代器的其他问题
在下列场景中,要想删除v1中的偶数,只有当*it % 2为1时,才能对迭代器加加,防止少删除数字
vector<int> v1 = {1, 2, 4, 4, 5, 6, 6, 10};
vector<int>::iterator it = v1.begin();
while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{++it;}
}
更多拓展阅读,请见我的另一篇博客(挖坑!!!!!!!!!!!!!)