本文共 4661 字,大约阅读时间需要 15 分钟。
// vector的成员变量// vector底层是可动态扩容的数组,所以protected: _Tp* _M_start; //数组首地址 _Tp* _M_finish; // 数组下一个可用位置 _Tp* _M_end_of_storage; // 数组的末尾
void push_back(const _Tp& __x) { //判断数组是否还有备用位置,如果有,直接添加 if (_M_finish != _M_end_of_storage) { construct(_M_finish, __x); ++_M_finish; } //否则动态扩容后再添加 else _M_insert_aux(end(), __x); }
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x){ //如果又备用空间,则 if (_M_finish != _M_end_of_storage) { //将_M_finish位置的值置为最后一个元素的值 construct(_M_finish, *(_M_finish - 1)); ++_M_finish; _Tp __x_copy = __x; //将插入点之后的元素循环后移一位 copy_backward(__position, _M_finish - 2, _M_finish - 1); //在指定位置插入新的元素 *__position = __x_copy; } else { const size_type __old_size = size(); //二倍扩容的方式进行扩容 const size_type __len = __old_size != 0 ? 2 * __old_size : 1; //申请空间 iterator __new_start = _M_allocate(__len); iterator __new_finish = __new_start; __STL_TRY { //将原来的vector中start 到指定位置__position中的数据copy到新的vector __new_finish = uninitialized_copy(_M_start, __position, __new_start); //添加新的元素 construct(__new_finish, __x); //指针后移 ++__new_finish; //将原来vector 剩余的位置的元素copy到新的vector中 __new_finish = uninitialized_copy(__position, _M_finish, __new_finish); } __STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len))); destroy(begin(), end()); _M_deallocate(_M_start, _M_end_of_storage - _M_start); //扩容之后跟新迭代器的位置 _M_start = __new_start; _M_finish = __new_finish; _M_end_of_storage = __new_start + __len; }}
//插入—个连续的数组,以__first开始,到__last的位置templatevoid vector<_Tp, _Alloc>::insert(iterator __position, const_iterator __first, const_iterator __last){ //如果当前vector中的元素个数不为0 if (__first != __last) { size_type __n = 0; distance(__first, __last, __n); //如果备用空间的大小足够插入一个连续的数组 if (size_type(_M_end_of_storage - _M_finish) >= __n) { //计算插入点之后后移的元素的个数 const size_type __elems_after = _M_finish - __position; iterator __old_finish = _M_finish; //如果后移的元素个数大于插入的元素的个数 if (__elems_after > __n) { //从_M_finish - __n位置开始到_M_finish结束,逐一复制到_M_finish开始的位置 uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); _M_finish += __n; //将__position开始后移 __个位置 copy_backward(__position, __old_finish - __n, __old_finish); //将元素插入到vector中 copy(__first, __last, __position); } else { uninitialized_copy(__first + __elems_after, __last, _M_finish); _M_finish += __n - __elems_after; uninitialized_copy(__position, __old_finish, _M_finish); _M_finish += __elems_after; copy(__first, __first + __elems_after, __position); } } //备用位置不足以插入一个连续的数组 else { const size_type __old_size = size(); //甲酸扩容后的大小,原数组的二倍 和 原数组加上插入数组的个数,取二者中的较大值 const size_type __len = __old_size + max(__old_size, __n); iterator __new_start = _M_allocate(__len); iterator __new_finish = __new_start; __STL_TRY { //将_M_start到__position中的元素拷贝到新的vector __new_finish = uninitialized_copy(_M_start, __position, __new_start); //将__first到__last中的元素拷贝到新的数组 __new_finish = uninitialized_copy(__first, __last, __new_finish); //将原数组中的__position到_M_finish中的元素拷贝到新数组中 __new_finish = uninitialized_copy(__position, _M_finish, __new_finish); } __STL_UNWIND((destroy(__new_start,__new_finish), _M_deallocate(__new_start,__len))); destroy(_M_start, _M_finish); _M_deallocate(_M_start, _M_end_of_storage - _M_start); //修改迭代器的指向 _M_start = __new_start; _M_finish = __new_finish; _M_end_of_storage = __new_start + __len; } }}
//删除单个元素 iterator erase(iterator __position) { //如果删除的不是最后一个元素,组删除点之后的元素往前移动一个位置 if (__position + 1 != end()) copy(__position + 1, _M_finish, __position); --_M_finish; destroy(_M_finish); return __position; } //删除连续的元素 iterator erase(iterator __first, iterator __last) { //从last 开始到_M_finish写入到__first开始的位置,对删除的元素进行覆盖 iterator __i = copy(__last, _M_finish, __first); destroy(__i, _M_finish); _M_finish = _M_finish - (__last - __first); return __first; }
bool empty() const { return begin() == end(); } size_type size() const { return size_type(end() - begin()); } //如果访问__n 越界了, 会抛出异常 reference at(size_type __n) { _M_range_check(__n); return (*this)[__n]; } //如果访问__n 越界了, 程序会直接崩掉 reference operator[](size_type __n) { return *(begin() + __n); }
转载地址:http://zonwi.baihongyu.com/