网站建设中哪些最重要性,南通网站建设推广专家,巢湖市网站建设推广,类似wordpress的建站用了这么久的 vector #xff0c;今天终于有时间来看下STL的实现源码了#xff0c;开心?~最近几个月在刷 leetcode #xff0c;用的较多的数据结构就是STL里面的 vector 了#xff0c;相比较于直接的 array 数组#xff0c;它具备了灵活地根据需求去分配管理内存#xf… 用了这么久的 vector 今天终于有时间来看下STL的实现源码了开心?~最近几个月在刷 leetcode 用的较多的数据结构就是STL里面的 vector 了相比较于直接的 array 数组它具备了灵活地根据需求去分配管理内存用户只管往里面扔东西拿东西而不用费心费力去解决C里面的动态内存问题。那么大致猜想一下要实现一个这样的容器不难想出在 vector 中至少存在这样三个私有成员head(指向列表第一个元素位置), tail(指向列表最后一个元素位置), size(容器大小) 打开源码看看得到验证templatetypename _Tp, typename _Allocstruct _Vector_base { ...... struct _Vector_impl_data { pointer _M_start; // 指向容器中的第一个元素是一个指针指针类型为 Tp 所示类型 pointer _M_finish; // 指向容器最后一个元素也是一个指针 pointer _M_end_of_storage; // 指向容器最后的位置 ...... }}templatetypename _Tp, typename _Alloc std::allocator_tp class vector : protected _Vector_base_tp {typedef _Vector_base_tp _Base; // 如上 _Vector_base 所示是一个基础实现 ......public:typedef _Tp value_type; // 数据类型typedef typename _Base::pointer pointer; // 全局数据指针 ......}总之就是一层套一层封装了一个又一个来完成对数据的抽象。但是最后的接口是放在 vector 上放开的。vector 支持动态内存分配支持随机存取访问因此在数据访问上具备了指针有的特性。那么它在源码上是怎么实现的呢首先来看它的接口(一部分常用接口)都有哪些**注**虽然包含 头文件就可以用 vector 但是它的实现源码其实是在 bits/stl_vector.h 下的而且下面的程序删掉了一些注释类、系统判断类函数。templatetypename _Tp, typename _Alloc std::allocator_tp class vector : protected _Vector_base_tp { ...// 获取指向第一个元素的指针 iterator begin() { return iterator(this-_M_impl._M_start); }// 获取指向容器最后一个可存放位置的下一个位置iterator end(){ return iterator(this-_M_impl._M_finish); }// 获取容器当前存放了多少元素size_type size() const { return size_type(this-_M_impl._M_finish - this-_M_impl._M_start); }// 对容器进行重新分配大小void resize(size_type __new_size) {if (__new_size size()) _M_default_append(__new_size - size());else if (__new_size _M_erase_at_end(this-_M_impl._M_start __new_size); }// 获取容器自身大小size_type capacity() const {return size_type(this-_M_impl._M_end_of_storage - this-_M_impl._M_start); }// 看看容器当前是否为空bool empty() const { return begin() end(); }// 获取一个能够对返回对象读写操作的引用类型其实就是指针 reference operator[](size_type __n) {return *(this-_M_impl._M_start __n); }protected:// 检查访问是否合法void _M_range_check(size_type __n) const {if (__n this-size()) __throw_out_of_range_fmt(__N(vector::_M_range_check: __n (which is %zu) this-size() (which is %zu)), __n, this-size()); }public:// 跟 [] 操作符差不多只不过多了一层范围检查reference at(size_type __n) { _M_range_check(__n);return (*this)[__n]; }// 获取能够对头部元素读写的指针reference front() { return *begin(); }// 获取最后一个元素reference back() { return *(end() - 1); }// 向容器末尾追加一个元素进来void push_back(value_type __x) { emplace_back(std::move(__x)); }templatetypename... _Args#if __cplusplus 201402L reference#elsevoid#endif emplace_back(_Args ... __args);// 将最后一个元素从容器中删掉void pop_back() { --this-_M_impl._M_finish; _Alloc_traits::destroy(this-_M_impl, this-_M_impl._M_finish); }// 在指定位置插入 n 个 __xiterator insert(const_iterator __position, size_type __n, const value_type __x) { difference_type __offset __position - cbegin(); _M_fill_insert(begin() __offset, __n, __x);return begin() __offset; }// 擦除掉某一个位置上的元素iterator erase(const_iterator __position) { return _M_erase(begin() (__position - cbegin())); }// 交换两个容器中的东西void swap(vector __x) {this-_M_impl._M_swap_data(__x._M_impl); _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); }// 将容器内所有元素清空void clear() { _M_erase_at_end(this-_M_impl._M_start); }};程序中大量出现的 allocator 是来自SGI STL的空间分配器说白了就是用来分配空间内存的。在拿到这部分源码后vector 的实现原理也就可以大致有所掌握了(毕竟每个接口也不过几行?这可能就是优秀设计的结果?)。而在调用过程中无非就是 vector 调用 vector_base 再调用 allocator 再对 _Vector_impl_data 进行操作。还有一个问题在添加元素过程中如果容器满了那么容器的容量是按照怎样的规则递增呢参考了《STL源码刨析》之后得到这样的结论如果超过当前容器容量那么容量会扩增至两倍如果两倍容量仍不够那么就扩张至足够大的容量。在容量的扩张过程中必须经历“重新分配内存元素移动释放原有空间”三个操作这是因为原有的空间之后不一定能够满足需求所以统一进行这三个操作来完成。如何知道是扩增两倍的呢最直观直接的方法就是执行一下这个过程看看例如int main() { vectorint v; v.push_back(1); cout endl; // : 1 1 v.push_back(2); cout endl; // : 2 2 v.push_back(3); cout endl; // : 3 4 v.push_back(4); cout endl; // : 4 4 v.push_back(5); cout endl; // : 5 8}这样的容量扩张过程也带来另一个问题当容量为 2 时获取到的 iterator 那么在容量为 8 时还可以用嘛答案是不一定行例如int main() { vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); auto iter v.begin(); cout endl; // : 1 v.push_back(4); cout endl; // : 1 v.push_back(5); cout endl; // : 310076128[具体运行结果视内存情况而定] iter v.begin(); cout endl; // : 1}由此可知如果当时的内存环境允许会直接拼到原有容器后面去如果不允许那么就需要把当前容器的内容移动到其他地方去了这时候原来的 iterator 就不能用了。务必小心从这一方面也可以体会到其实 iterator 就是一个类型为传入 vector 中 T 类型的指针。在所有的接口中觉得最有意思的就是 insert 接口了?它的实现过程比较好玩。首先假设调用函数为insert(position, n, x) 而且剩余空间够用那么它需要分成两种情况插入元素个数 n 插入点之后的元素个数 。插入元素个数 n 插入点之后的元素个数 。上面两种情况分别对应下面图中的左右两边内存操作示意图(参考自《STL源码刨析》)在有限的过程和空间里实现最高效的操作不愧是STL???。
