深圳大型网站建设服务公司,上海最新新闻,网站制作都包括什么,seo北京优化目录
成员变量与迭代器
size
capacity
empty
迭代器有关函数
实现默认成员函数的前置准备
reserve
编辑
编辑
push_back
构造函数
无参构造
迭代器区间构造
n个val来进行构造
析构函数
拷贝构造函数
赋值重载
增删查改
clear
resize
pop_back
inser…目录
成员变量与迭代器
size
capacity
empty
迭代器有关函数
实现默认成员函数的前置准备
reserve
编辑
编辑
push_back
构造函数
无参构造
迭代器区间构造
n个val来进行构造
析构函数
拷贝构造函数
赋值重载
增删查改
clear
resize
pop_back
insert
erase
重载[]
print_Container 成员变量与迭代器
我们还是需要在一个命名空间里模拟实现vector防止和标准库里的起冲突。
namespace zh
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}
解释说明
1.vector是一个非常通用的容器是一个动态大小的数组可以存储任意类型的元素并且能够自动调整大小以适应元素的添加和删除。所以我们的模拟实现要写成类模板。
2.vector可以看做顺序表的升级但是模拟实现vector跟我们以往实现顺序表有所不同顺序表是使用一个动态开辟的数组、数组有效元素个数size和数组容纳最大有效数据的个数capacity维护的而模拟实现vector需要三个模板参数T* 类型的指针而vector的迭代器功能恰恰又和T*类型指针类似所以干脆把T*封装成迭代器。当然迭代器需要有两个版本普通版本和const版本。
3.参数的含义 _start指向数组首元素_finish指向最后一个有效元素的下一个位置 _end_of_storage指向数组空间末尾。
通过三个指针也可以模拟出size和capacity的功能。
size
返回有效数据个数的函数。
size_t size() const
{return _finish - _start;
}
capacity
返回数组最大容纳有效数据个数容量大小的函数。
size_t capacity() const
{return _end_of_storage - _start;
}
empty
判断数组是否为空判断_start与_finish是否相等即可。
bool empty() const
{return _finish _start;
}
迭代器有关函数
主要实现begin函数和end函数。
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}
实现默认成员函数的前置准备
reserve
用于vector数组空间不足时扩容的函数扩容成n个空间。
void reserve(size_t n)
{if (n capacity()) //n大于数组容量才扩容{size_t oldsize size(); //用oldsize避免新_start和老_finish的问题T* tmp new T[n];//memcpy(tmp, _start, size() * sizeof(T)); //这里是浅拷贝如果是内置类型没问题 //如果vector存的是自定义类型就是大坑for (size_t i 0; i oldsize; i){tmp[i] _start[i];}delete _start; //这里delete_start_finish 和_end_of_storage是野指针//更新成员变量_start tmp;_finish tmp oldsize; _end_of_storage tmp n;}
}
reserve有几个问题需要注意
1.开空间的时候要使用new而不要用malloc因为malloc只是去开空间不会去调用构造函数。
2.新_start和_finish的问题。
错误示范。 将原有数据拷贝到新空间后释放了旧空间的资源_strat指向了新的空间但是_finish和_end_of_storage还是指向旧空间这两个指针就变成野指针了。而最关键的是_finish不能被正确赋值。 3.memcpy浅拷贝问题
memcpy(tmp, _start, size() * sizeof(T));
memcpy是浅拷贝如果vector存的是内置类型那么浅拷贝就没有问题如果存的是自定义类型那浅拷贝就是个大坑。假如vector存的是string类型那么扩容时将数据从旧空间拷贝到新空间时因为是浅拷贝所以两个空间里的string的_str是同一个地址释放旧空间的时候就连带这把新空间的资源也释放了。
这样就扩容失败了因为你把原空间的数据丢失了而且搞不好有可能程序还会崩溃。 要解决这个问题我们就得手动实现深拷贝 因为new出来的空间如果是自定义类型的话就自动调用构造函数初始化了所以这里走的是赋值重载来实现深拷贝。
push_back
用于在数组末尾尾插一个元素的函数。
void push_back(const T x)
{//插入之前先判断空间是否足够if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : 2 * capacity());}//插入元素更新_finish*_finish x;_finish;
}
构造函数
vector的构造函数我们实现无参构造、迭代器区间构造和n个val构造。
无参构造
无参构造其实我们并不需要写因为已经在成员变声明时给了缺省值编译器自动生成的无参构造函数走初始化列表满足需求了。但是由于我们写了其他构造函数编译器就不自动生成了。 这里时候可以自己写无参构造也可以用default强制编译器生成C11的用法。
//构造
/*vector()
{}*///c11 强制生成构造
vector() default;
迭代器区间构造
//类模板的成员函数还可以继续是函数模版
templateclass InputIerator
vector(InputIerator first, InputIerator last)
{while (first ! last){push_back(*first); first;}
}
这里给这个函数再套一层模板是为了让vector不仅能用vector的迭代器区间构造还能用其他容器list、string等的迭代器来进行构造。
这里又有个问题就是while循环判断条件的!不能改成因为对于vector的迭代器时可以的但是对于其他容器的迭代器如listlast不一定比first要大。 n个val来进行构造
vector(size_t n, const T val T())
{//先开好空间reserve(n);for (size_t i 0; i n; i){push_back(val);}
}
使用的时候val可能不传参所以要给缺省值。
因为val的类型不确定可能是内置类型也可能是自定义类型。
在不传参使用缺省值时
对于自定义类型比如strng先调用构造函数构造一个匿名对象再拷贝构造给val。编译器会优化直接对val进行构造这样val就有了缺省值。
对于内置类型本来是没有构造函数的说法的但是为了适应这里也支持类似类那种使用构造函数初始化的方式。
int a int();
int b int(2);
int c(3);
cout a endl;
cout b endl;
cout c endl; 析构函数
直接delete就可以了把三个迭代器置空。
//析构
~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}
}
拷贝构造函数
先开好空间然后尾插就可以了。
//拷贝构造
vector(const vectorT v)
{reserve(v.size());for (auto e : v){push_back(e);}
}
赋值重载
首先实现一个交换函数然后传值调用将两个对象交换即可。
//void swap(vector v) 可以这样写
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}vectorT operator(vectorT v)
{swap(v);return *this;
}
增删查改
clear
不需要真的删除直接将更改_finish的值即可。
void clear()
{_finish _start;
}
resize
控制有效数据个数。
若n size直接将_finish更改为_start n即可。若_size n capacity或者n capacity直接扩容成n个空间空间足够就不会扩容从_finish拷贝足够数量的val即可。
void resize(size_t n, T val T())
{if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n) {*_finish val;_finish;}}
}
pop_back
先判断数组是否为空尾删一个元素_finish-- 即可。
void pop_back()
{//判断下数组是否为空assert(!empty());--_finish;
}
insert
在pos位置插入一个元素。
iterator insert(iterator pos, const T x) //pos不会为0因为是有效的迭代器
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage) //涉及到扩容pos会失效pos指向原来的空间{size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}//插入元素更新*pos x;_finish;return pos;
}
注意的问题
1.如果插入涉及到了扩容要提前把pos相对于首元素的相对长度记录下来扩容完毕后更新pos。因为扩容会导致pos失效。
2.插入之后要返回新元素的迭代器。这里其实也算迭代器是失效了因为pos指向的元素发生了更改迭代器失效了就不要在使用了。
erase
删除pos位置的元素删除完后返回删除元素下一位置的迭代器。
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;return pos;
}
抛出一个问题利用迭代器删除vector中所有的偶数。
错误做法
auto it v.begin();
while (it ! v.end())
{if (*it % 2 0){it v.erase(it);}it
}
删完一个偶数后it已经是下一元素的迭代器了it不需要了。
正确做法
auto it v.begin();
while (it ! v.end())
{if (*it % 2 0){it v.erase(it);}else{it;}
}
重载[]
为了方便访问和修改数组中的元素。
T operator[](size_t i)
{assert(i size());return _start[i];
}const T operator[](size_t i) const
{assert(i size());return _start[i];
}
print_Container
通用打印容器函数套一层模板即可。
注意
templateclass Container
void print_Container(const Container v)
{//typename vectorT::const_iterator it v.begin(); //typename标定为类型 //从没有实例化的类模板取出来的可能是类型或者成员变量编译器无法区分auto it v.begin(); while (it ! v.end()){cout *it ;it;}cout endl;/*for (auto num : v){cout num ;}cout endl;*/
}
从未实例化的类取出来的有可能是类型或者成员变量要加关键字typename告诉编译器是类型不加的话会发生编译错误。
当然直接用auto更方便。 拜拜下期再见
摸鱼ing✨
