邢台市建设局培训中心网站,西安网站建设和推广公司,网站logo下载,离线推广网站规划书一、vector容器的介绍
vector是表示可变大小数组的序列容器。就像数组一样#xff0c;vector也采用的连续存储空间来存储元素#xff0c;但是又不像数组#xff0c;它的大小是可以动态改变的#xff0c;而且它的大小会被容器自动处理。
总结#xff1a;vector是一个动态…一、vector容器的介绍
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。
总结vector是一个动态数组能高效的随机下标访问。
二、主要接口
(constructor)构造函数声明接口说明vector()重点无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造 iterator的使用接口说明begin end重点获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置 的iterator/const_iteratorrbegin rend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的 reverse_iterator 容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变vector的sizereserve 重点改变vector的capacity vector增删查改接口说明push_back重点尾插pop_back 重点尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[] 重点像数组一样访问 三、模拟实现
1.vector 的对象 iterator _start 指向第一个元素的迭代器 iterator _finish: 指向最后一个元素下一个位置的迭代器 iterator _endOfStorage 指向动态空间最后一个位置的迭代器 namespace N
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finish nullptr;iterator _endOfStorage nullptr;};
}
模板命名T vector迭代器的本质是指针
【C11】关于成员对象给缺省在构造函数调用初始化列表的时候会选择用上缺省值 2.迭代器成员函数begin()和end() begin():返回指向容器的起始位置的迭代器非const
end():返回指向容器的最后位置的下一个位置迭代器非const
cbegin():返回指向容器的起始位置的常属性迭代器const
cend():返回指向容器的最后位置的下一个位置常属性迭代器const
iterator begin(){return _start;
}iterator end(){return _finish;
}const_iterator cbegin()const {return _start;
}const_iterator cend() const
{return _finish;
} 区别 非const的版本函数返回的迭代器可以用来访问修改元素 而const版本只能用来访问元素不准修改 3.容量空间
1)size()返回数据个数 元素首位迭代器的相减返回个数 前开后闭返回区间个数
2capacity() 元素容量与头元素迭代器的相减
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endOfStorage - _start;
}
3reserve(size_t n) :改变vector的capacity 如果vector 的capacity大于n 不进行操作 ncapacity扩容拷贝释放原空间 同时更新_start _finish _endofstorage void reserve(size_t n)
{if (n capacity()){return;}T* tmp new T[n];size_t sz size();if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[]_start;}_start tmp;_finish _start sz;_endOfStorage _startn;
} 4)resize :改变vector的size nsize() 改变_finishi nsize() reserve空间size后面的数依次赋值 void resize(size_t n, const T value T())
{if (n size()){_finish _start n;return;}reserve(n);while (_finish n _start){*_finish value;_finish;}
}
关于默认参数
匿名对象T()生命周期只有这一行
const修饰匿名对象 延长生命周期 value销毁时匿名对象才销毁 4.vector增删查改
1push_back():尾插 检查容量不够就reserve扩容 _finish位置插入数据 _finish void push_back(const T x)
{if (_finish _endOfStorage)//扩容{reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;
}
2)pop_back()尾删
--_finish
void pop_back()
{_finish--;
} 3)insert(): pos位置之前插入val 检查pos合法 检查是否扩容注意保存pos的位置(求出pos-_start) 从最后一个数据往前挪动数据插入val 更新_finish iterator insert(iterator pos, const T x)
{assert(pos_start);assert(pos _finish);int len pos - _start;if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}pos _start len;//移动数据iterator end _finish-1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;
}
关于迭代器失效
如果扩容后原来的空间会被释放掉那么pos会变成野指针,如果继续使用迭代器会使用一块已经释放的空间导致程序可能崩溃。
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等
4earse()删除pos的值
检查pos的合法 _startpos_finish
从前往后挪数据
更新_finish
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator cur pos1;while (cur ! _finish){*(cur - 1) *cur;cur;}--_finish;return pos;
}
涉及迭代器失效问题
当earse最后一个位置时迭代器失效vs上认为使用earse后不管删除哪个位置迭代器都失效 5swap 交换俩个vector的数据空间
如果发生赋值会极大降低效率因此在vector容器的交换交换各自的迭代器对象
void swap(vectorT v)
{::swap(_start, v._start);::swap(_finish , v._finish);::swap(_endOfStorage, v._endOfStorage);
} 6operator [ ] 下标访问修改
返回指定空间的引用
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}const T operator[](size_t pos)const
{assert(pos size());return _start[pos];
}
关于const版本和非const版本const只读不可改非const版本可读可改 5.(constructor)构造函数声明
1)无参构造函数 不用写具体内容因为在C11支持成员变量给缺省会自动进入初始化列表
2vectorsize_type n, const value_type val value_type() N个value构造 先开空间附用reverse函数尾插
vector(int n, const T value T())
{reserve(n);for (int i 0; i n; i){push_back(value);}
} 3vector(InputIterator first, InputIterator last)迭代器区间构造
定义迭代器模板依次尾插
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
} 4)vector (const vector x)拷贝构造
开空间尾插
vector(const vectorT v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
} 5operator 赋值
拷贝构造临时空间交换
vectorT operator (vectorT v)
{swap(v);return *this;
} 6析构函数
释放空间 总结
源代码
STL/vector.h · L_may/CStudy - 码云 - 开源中国 (gitee.com)
本文模拟实现vector容器在insert和erase中涉及迭代器失效的问题要多加注意。
作者能力有限希望对大家有所帮助。
