软件开发流程详细,深圳seo云哥,大连网络科技有限公司,上传下载网站建设vector 构造函数析构函数[]push_backsize()capacity()reserve()push_back() 迭代器实现非const和const版本 pop_back()resize()insert()***重点erase()***重点再谈构造函数#xff01;拷贝构造函数****#xff08;重点#xff09;运算符重载***#xff08;重点#xff09;… vector 构造函数析构函数[]push_backsize()capacity()reserve()push_back() 迭代器实现非const和const版本 pop_back()resize()insert()***重点erase()***重点再谈构造函数拷贝构造函数****重点运算符重载***重点 基本框架
namespace xty
{templateclass Tclass vector {public:typedef T* iterator;/////...///private:iterator _strat; //起始位置iterator _finish; //最后一个元素的下一个地址iterator _end_of_storage; //容量的最后一个元素};
}vector的大致形状如下黄色代表每天满的地方。
构造函数
使用初始化列表实现一个简单的无参构造函数。 //无参构造函数vector():_finish(nullptr),_start(nullptr),_end_of_storage(nullptr){}析构函数
记住要带[]即可。 ~vector(){delete[] _start; //用带括号的_start nullptr;_finish nullptr;_end_of_storage nullptr;}
[] T operator[](size_t pos){assert(pos size());return *(_start pos);}const T operator[](size_t pos) const{assert(pos size());return *(_start pos);}push_back
size() size_t size() const{return _finish - _start;}capacity() size_t capacity() const {return _end_of_storage - _start;}reserve()
因为push_back涉及到扩容函数需要实现reserve()。
如下示例 void reserve(size_t n){if (n capacity()){T* tem new T[n];if (_start){memcpy(tem, _start, sizeof(T)*size()); //拷贝过去delete[] _start;}_start tem;_finish _start size(); //error_end_of_storage _start n;}}问题1_finish赋值出错出bug了是因为size()函数调用了空指针导致报错。 改正 因为delete之后原数据就被清空了所以可以提前保存一下size()的大小。 void reserve(size_t n){if (n capacity()){T* tem new T[n];const size_t sz size(); //提前保存szif (_start){memcpy(tem, _start, sizeof(T)*size()); //拷贝过去delete[] _start;}_start tem;_finish _start sz; //使用sz赋值_end_of_storage _start n;}}push_back()
逻辑比较简单在vector的尾部添加一个val就需要一些前置函数。 //尾插void push_back(const T val){//满了扩容if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}//插入数据*_finish val;_finish;}迭代器实现
该逻辑也比较简单注意实现const的版本。
非const和const版本
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;}pop_back()
尾删。
bool empty(){return _start _finish;}//尾删void pop_back(){assert(!empty());_finish--;}resize()
和string逻辑差不多。 void resize(size_t n, const T val T()){//一样大直接返回if (n size()) {return;}if (nsize()) //小于直接修改_finish{while (n ! size()){--_finish; }}else{if (n capacity()) //大于容量先扩容{reserve(n);}while (n ! size()){push_back(val);}}}优化该函数多次调用push_back()使用while效率低。 void resize(size_t n, const T val T()){if (n size()){return;}if (n size()){ _finish _start n; //直接移动_finish}else{if (n capacity()){reserve(n);}while (_finish ! _start n) //使用指针操作减少调用{*_finish val;_finish;}}}insert()***重点
传入迭代器的位置插入一个元素。 void insert(iterator pos ,const T val){//检测pos位置是否合法assert(pos _start);assert(pos _finish);// 满了需要扩容if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}//从后往前移动iterator end _finish;while (end pos){*end *(end - 1);end--;}*pos val; //在该位置赋值_finish;}算法问题1会造成迭代器失效迭代器失效实际就是迭代器底层对应指针所指[空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 该程序正常来说没有问题当出现扩容的时候reserve会删除原来的空间去申请新的空间因此会导致pos指向的那段空间被释放掉pos变成野指针。
改正记录插入的相对位置扩容后根据相对位置更新pos的值。 void insert(iterator pos, const T val){//检测pos位置是否合法assert(pos _start);assert(pos _finish);// 满了需要扩容if (_finish _end_of_storage){size_t len pos - _start;//扩容前记住相对位置reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len; //扩容后重新给pos值}//从后往前移动iterator end _finish;while (end pos){*end *(end - 1);end--;}*pos val; //在该位置赋值_finish;}算法问题2执行insert后如果扩容pos位置已经改变了而函数外面的pos因为是值传递并没有修改同样导致了野指针的问题。迭代器再一次失效 解决办法
pos传引用可以吗 不可以。如下图如果传入v.begin()会报错。因为begin()是传值返回传值返回有一个临时变量而临时变量具有常性不能被修改insert里面就不能修改了 通过返回值解决可以吗 可以我们可以利用insert返回值的特性来更新pos防止失效 如下图这样就解决问题了。
最终版本 iterator insert(iterator pos, const T val){//检测pos位置是否合法assert(pos _start);assert(pos _finish);// 满了需要扩容if (_finish _end_of_storage){size_t len pos - _start;//扩容前记住相对位置reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len; //扩容后重新给pos值}//从后往前移动iterator end _finish;while (end pos){*end *(end - 1);end--;}*pos val; //在该位置赋值_finish;return pos;}总结使用insert后我们默认迭代器失效因为我们不知道何时执行扩容操作因此需要重新对pos赋值防止这类情况发生
erase()***重点
指定位置执行删除操作。 void erase(iterator pos){assert(pos _start);assert(pos _finish);auto end pos 1;while (end _finish){//后给前从前往后*(end - 1) *end;end;}_finish--;}问题1erase会导致迭代器失效 会导致如果删除最后一个位置最后一个位置就变成了空位置导致pos也指向了不该指向的位置。因此erase()执行过后应该重新给pos赋值再使用
最终版本添加返回值。 iterator erase(iterator pos){assert(pos _start);assert(pos _finish);auto end pos 1;while (end _finish){//后给前从前往后*(end - 1) *end;end;}_finish--;return pos;}最后给大家一个例子自己感受 该例子在VS2019会报错
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}return 0;
}
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;}return 0;
}再谈构造函数
这次实现一个可以规定数量和内容的构造函数。
//正常实现vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);size_t len n;while (n--){push_back(val);}}//构造函数由迭代器实现templateclass InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first ! last){push_back(*first);first;}}当我们满心欢喜的实现好这两个构造函数后想要测试一下。结果报错了。 输入 vector vx(10,5); 这是为什么呢因为105都被编译器认为是int类型而编译器在函数重载时会自动调用最合适的而它认为第二个函数更适合自己()因此解引用的时候产生非法间接寻址
因此我们需要再次实现一个int型的函数重载 vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);size_t len n;while (len--){push_back(val);}}迭代器构造还支持以下方法 int a[] { 1, 2, 3 };vectorint v4(a, a 3);for (auto e : v4){std::cout e ;}std::cout std::endl;
}拷贝构造函数****重点
如果我们不自己实现拷贝构造函数编译器就会默认生成一个但是编译器默认生成的是浅拷贝不可以。
//拷贝构造vector(const vectorT v){//扩容reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_finish _start v.size();}现在我们写完这个函数的拷贝构造之后看看是否有问题 提前告诉大家这个程序会崩溃因为memcpy()实现的是浅拷贝他仅仅会拷贝v3的首尾指针并不会开一个新的空间去存储相应的字符串。所以程序结束时调用析构函数会连续析构两次
**解决办法**不适用memcpy()自己实现深拷贝使用‘’即可实现因为string赋值操作就是深拷贝string的赋值就会先开空间再拷贝 //拷贝构造vector(const vectorT v){//扩容reserve(v.capacity());//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i 0; i v.size(); i){_start[i] v._start[i]; //变成string对象的拷贝}_finish _start v.size();}但是reverse()也会产生这个浅拷贝的问题因此将reserve也应该改成深拷贝。 void reserve(size_t n){if (n capacity()){T* tem new T[n];const size_t sz size(); //提前保存szif (_start){//memcpy(tem, _start, sizeof(T)*size()); //拷贝过去for (size_t i 0; i size(); i){tem[i] _start[i];}delete[] _start;}_start tem;_finish _start sz; //使用sz赋值_end_of_storage _start n;}}这样vector的问题就解决了。但是vectorvectorint还有问题请看赋值重载的部分。
运算符重载***重点
这里暴露了一个问题就是虽然外面的vector是深拷贝但是里面的vector是浅拷贝是由于没有写vector的赋值重载再补充一个赋值重载即可 vectorT operator(vectorT v){swap(v);return *this;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}运算符重载和拷贝构造这里写的不太详细后续还会补充
