什么是网站建设与优化,网站建设是专业,用帝国cms做门户网站,做网站 网络映射1. 基础框架 这里我们有三个私有变量#xff0c;使用 _finish - _start 代表 _size#xff0c;_end_of_storage - _start 代表 _capacity#xff0c;并且使用到了模版#xff0c;可以灵活定义存储不同类型的 vector#xff0c;这里将代码量较小的函数直接定义在类的内部使… 1. 基础框架 这里我们有三个私有变量使用 _finish - _start 代表 _size_end_of_storage - _start 代表 _capacity并且使用到了模版可以灵活定义存储不同类型的 vector这里将代码量较小的函数直接定义在类的内部使其成为内联函数 namespace bit
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const 迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}//可读可写T operator[](size_t i){assert(i size());return _start[i];}//只读const T operator[](size_t i) const{assert(i size());return _start[i];}bool empty(){return _start _finish;}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
} 2. 核心接口 2.1 增删与扩容 增删接口主要讲解的有尾删尾删、插入删除以及扩容 2.1.1 push_back pop_back 尾插尾删 这里的尾插首先要判断是否需要扩容然后在数据尾部插入数据即可 尾删则只需要保证所给的位置不超出范围后直接 --_finish 即可 //尾插
void push_back(const T x)
{if (finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*finish x;finish;
}
//尾删
void pop_back()
{assert(!empty());--_finish;
} 2.1.2 insert 在指定位置插入数据 这里首先判断是否需要扩容然后将指定位置pos之后的数据均向后移动最后插入数据即可这里需要注意的是在扩容后原来的pos位置就会失效也就是迭代器失效这里就相当于成为了野指针所以解决方法是将原来的位置记录下来在扩容后更新即可 void insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_stroage){size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (pos ! end){*(end 1) *end;--end;}_finish;
} 2.1.3 erase 删除指定位置数据 这里删除就是保证所给位置在范围内然后直接将要删除的位置之后的数据覆盖到原来位置即可需要注意的是在erase操作后也会出现迭代器失效所以要继续使用pos的话需要记录原来的位置然后更新 //erase后的迭代器也看做是失效的
void erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator it pos 1;while (it ! end()){*(it 1) *it;it;}_finish--;
} 2.1.4 resize 初始化指定长度的指定数据 这里主要注意的是要分三种情况1. n size()这时就直接缩容即可2. size() n capacity()这里就直接插入数据不用扩容3. capacity() n这里需要扩容后插入数据 //这里的T可以是string类也可以是内置类型int等string类有自己的默认构造函数
//内置类型同样有自己的默认构造函数
void resize(size_t n, T val T())
{if (n size())//n小于_size则缩容{_finish _start n;}else{reserve(n);//如果n超过_capacity则扩容while (_finish ! _start n){*_finish val;_finish;}}
} 2.1.5 reserve 判断空间是否充足后进行扩容 扩容操作就是判断原容量是否足够插入新数据不够则二倍扩容即可这里的注意事项有1. 要将原来的size()保存成为old_size以保证之后的_finish在计算时不会出现野指针的情况因为如果不保存原来的size()那么在之后size()就会更新成为新的size()这里计算就会出现差错 2. 注意memcpy是浅拷贝在处理内置类型int、double这样的数据不会出错但是如果是string或者vector这样需要深拷贝类型的数据就会出错导致内存泄漏解决方法就是使用其本身的赋值运算这样可以兼顾二者 //扩容
void reserve(size_t n)
{if (n capacity()){size_t old_size size();T* tmp new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//拷贝数据for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;//释放旧空间_start tmp;//指向新空间_finish tmp old_size;//tmp(新的) _finish(原来) - _start(原来)_end_of_storage tmp n;}
} 2.2 拷贝构造 2.2.1 构造函数与析构函数 这里涉及的知识点有 1. 类模版的成员函数仍然可以是函数模版 2. 在迭代器区间构造的函数时可以使用函数模版这样可以使用任意容器的迭代器初始化例如链表 //直接走初始化列表如果没有则使用缺省值
vector()
{}
//C11强制生成默认构造
//vector() default;//类模版的成员函数仍然可以是函数模版
//迭代器区间构造
//可以使用任意容器的迭代器初始化
//例如链表
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}//使用n个val初始化
vector(size_t n, const T val T())
{reserve(n);for (size_t i 0; i n; i){ push_back(val);}
}~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage;}
} 2.2.2 拷贝构造函数 这里直接只用范围for进行深拷贝操作简单便捷并且提前保存空间减少扩容带来的消耗 //拷贝构造
vector(const vectorT v)
{reserve(v.size());for (auto e : v){//这里默认有一个this指针//直接完成了深拷贝的工作push_back(e);}
} 2.3 赋值重载 这里涉及了两种写法 1. 自己完成赋值人为进行赋值的操作过程比较清晰 2. 交给编译器完成赋值交给编译器直接完成交换以达到赋值的目的操作更加简便 //赋值重载
1、传统写法
void clear()
{_finish _start;
}vectorT operator(const vectorT v)//传地址
{if (this ! v){clear();reserve(v.size());for (auto e : v){push_back(e);}}return *this;
}//2、现代写法
void swap(const vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
vectorT operator(const vectorT v)//传值
{swap(v);return *this;
} 3. 常见问题 3.1 迭代器失效 这里的迭代器失效有两种情况 1. 扩容后迭代器失效这里首先了解扩容的原理是开辟一个原来空间二倍的空间将原空间数据拷贝到扩容后的空间然后释放原空间所以由于pos在扩容后仍然指向的是原空间而原空间已经释放所以导致了类似野指针的效果也就是第一种迭代器失效 2. 未扩容但是挪动数据导致的迭代器失效即在使用原来pos完成挪动数据的操作后pos已经不指向原来的位置这时如果仍然想要访问原来位置就会导致迭代器失效 解决方法保存原来的迭代器指向的位置或者相对位置然后在扩容或者挪动数据之后更新pos指向的位置即可 void insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);//1.扩容,注意避免迭代器失效即pos在扩容后仍然指向之前的空间//在之后对新空间的操作时会失效类似野指针就是迭代器失效//这里使用相对位置来避免迭代器失效//还需要注意在insert之后的迭代器是失效的不可以直接继续访问但是可以在更新后访问//2.不扩容,但是由于数据的挪动导致p不再指向原来的位置也看做迭代器失效//关于迭代器失效的处理方法就是接收操作之后的迭代器然后对更新后的迭代器进行操作即可if (_finish _end_of_stroage){size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (pos ! end){*(end 1) *end;--end;}_finish;
}
//erase后的迭代器也看做是失效的
void erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator it pos 1;while (it ! end()){*(it 1) *it;it;}_finish--;
} 3.2 浅拷贝 浅拷贝就是指两个指针指向同一块空间这时如果一个指针对该空间进行释放或者其他操作会影响另一个指针导致内存泄漏等后果解决方法很简单就是深拷贝使两指针指向不同的空间然后使其数据保持一致即可 //扩容
void reserve(size_t n)
{if (n capacity()){size_t old_size size();T* tmp new T[n];//memcpy(tmp, _start, old_size * sizeof(T));//拷贝数据//这里的T如果是string或者vector类型这种需要深拷贝的类型// 则需要赋值进行拷贝数据否则浅拷贝会导致内存泄漏//这里调用的赋值就是string/vector的赋值就是深拷贝for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;//释放旧空间_start tmp;//指向新空间_finish tmp old_size;//tmp(新的) _finish(原来) - _start(原来)_end_of_storage tmp n;}
} 3.3 类型转换 这个问题是因为由于给出的代码编译器不知道该代码是类型还是变量所以导致识别不出来解决方法就是改为 auto 自动转换或者前面加上 typename 来告诉编译器即可 templateclass T
void print_vector(const vectorT v)
{//编译器无法确定此处的const_iterator是类型还是静态成员变量//所以规定不能从未实例化的类模版内取东西需要程序员自己规定//即加一个 typename 来表示这里的const_iterator是类型即可typename vectorT::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;for (auto e : v){cout e ;}cout endl;
}
