淘宝了做网站卖什么好,公司网站制作公司倒闭,微信分身网页版网址,网站动态和静态的区别欢迎来到我的Blog#xff0c;点击关注哦#x1f495; 【C】vector介绍以及模拟实现 前言vector介绍 vector常见操作构造函数iteratorcapacitymodify vector模拟实现存储结构默认构造函数构造函数拷贝构造函数赋值运算符重载析构函数 容量#xff08;capacity#xff09;si…欢迎来到我的Blog点击关注哦 【C】vector介绍以及模拟实现 前言vector介绍 vector常见操作构造函数iteratorcapacitymodify vector模拟实现存储结构默认构造函数构造函数拷贝构造函数赋值运算符重载析构函数 容量capacitysize和capzcityreserveresize 修改modifypush_back直接将_finsih位置解引用赋值_finsih pop_backinserterase 元素访问Element accessoperator [ ] 迭代器iterator 源码 前言 string的特性和用法以及底层的探索已经虽然string不算container的成员之一但是也见到了其的影子接下来让我们看看vector vector介绍
vector 是 C 标准模板库STL中的一个动态数组容器它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存不需要手动分配和释放支持常见容器操作如插入、删除、遍历等.
vector常见操作
构造函数
(constructor)构造函数声明接口说明vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
iterator
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置
capacity
函数声明接口说明capacity获取容量大小sizesize 获取数据个数empty判断是否为空resize改变vector的sizereserve改变vector的capacity
modify
vector增删查改接口说明push_back重点尾插pop_back 重点尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[]像数组一样访问
vector模拟实现
存储结构
结构上使用命名空间myvector进行封装防止与库冲突使用class封装成为对象vector
这样typedef的一点是和STL保持一致
写vector写成类模板可以支持存贮多种类型数据_start表示数据存储的开始地址_finish表示数据存贮的的下一个地址_end_of_storage表示数据当前开辟的最大空间的地址
namespace myvector
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}默认构造函数
构造函数
初始化是使用的都是空指针
vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}使用n个val初始化对象
vector(size_t n, const T val T())
{
resize(n, val);
}根据可以模板的嵌套的性质再次进行模板的定义这是使用两个迭代器的进行初始化
templateclass InputIteratorvector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}拷贝构造函数
利用一个对象初始化另外一个对象传引用new出和传递的对象一样大小的空间在string类中我们利用了mencpy进行拷贝在vector中不采用mencpy mencpy拷贝只能进行内置类型的浅拷贝不能进行自定义类型的深拷贝在这里面进行依次赋值或者push_back 最后进行_finish和_end_of_storage的初始化
vector(const vectorT v)
{_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();}赋值运算符重载
在operator的参数中是值传递是实参的拷贝这里面利用这个特性进数据的交换返回this指针就是赋值的内容了
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;
}析构函数
判断_start是否为空为空避免再次析构
~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}}容量capacity
size和capzcity
vector的size和capacity不同于string类中的不一样vector定义的是指针充分利用只针的特性指针—指针是数值可以计算出capacity和size
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}reserve
开始判断需要扩容的大小是否大于capacity以避免重复扩容效率低下在开始时候记录原始空间的大小是为了避免迭代器失效 进行空间的扩容会将原来的空间析构原始的计算空间大小已经已释放指向的_start _finish _end_of_storage已经失效 这里还是采用在这里面进行依次赋值或者push_back更新_start _finish _end_of_storage
void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];size_t sz size();if (_start){//memcpy(tmp, _start, sizeof(T)*capacity());//string 类深拷贝for (int i 0; i sz; i){tmp [i] _start[i];}delete[] _start;}_start tmp;_finish sz _start;_end_of_storage _start n;}
}resize 两种情况 Ncapacity 直接进行移动_finish Ncapacity 进行容量的检查和扩容依次赋值val const T val T()这句话是针对内置类型和自定义类型C这里将内置类型进行了升级 int 1; int(1);//这里int有点像构造函数void resize(size_t n, const T val T())
{if (n capacity()){_finish n _start;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}
}修改modify
push_back 首先进行容量的检查 直接将_finsih位置解引用赋值_finsih
void push_back(const T x)
{if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;
}pop_back
复用erase
void pop_back()
{
erase(end()-1);
}insert
进行断言防止pos越界访问判断空间的大小_finish _end_of_storagesize_t step pos - _start用step记录距离 _start距离扩容的时候将原空间释放pos将无法访问,扩容完成后进行pos的恢复将pos位置的数据依次进行移动、插入pos位置的值修改_finish为了避免迭代器失效返回现在的位置pos
iterator insert(iterator pos, const T x)
{assert(pos _finish pos _start);if (_finish _end_of_storage){//防止迭代器失效size_t step pos - _start;size_t newcapacity capacity() 0 ? 0 : capacity() * 2;reserve(newcapacity);//防止迭代器失效pos _start step;}iterator end _finish - 1;while (end pos){*(end 1) *end;end;}*pos x;_finish;return pos
}erase
进行断言防止pos越界访问将pos后面的元素向前面移动进行覆盖为了避免迭代器失效返回现在的位置pos
iterator erase(iterator pos)
{assert(pos _finish pos _start);while (pos ! _finish){*pos *(pos 1);pos;}--_finish;return pos
}元素访问Element access
operator [ ]
实现const和非const两种只读和可读可改充分利用字符串特性可以进行下标的访问
T operator[](size_t pos)
{assert(pos 0 pos size());return _start[pos];
}const T operator[](size_t pos)const
{assert(pos 0 pos size());return _start[pos];
}迭代器iterator
本质还是指针直接进行指针的返回就好
//iterator
const_iterator cbegin()
{return _finish;
}const_iterator cend() const
{return _start;
}
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin()const
{return _start;
}
const_iterator end()const
{return _finish;源码
#include string.h
#include assert.h
#include iostreamnamespace MyVector
{template class Tclass vector{public://iteratorconst_iterator cbegin(){return _finish;}const_iterator cend() const{return _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}//默认构造vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}vector(size_t n, const T val T()){resize(n, val);}~vector(){if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}}vector(const vectorT v){_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}vectorT operator(vectorT v){swap(v);return *this;}//capacityvoid reserve(size_t n){if (n capacity()){std::cout reserve(size_t n) std::endl;T* tmp new T[n];size_t sz size();if (_start){//memcpy(tmp, _start, sizeof(T)*capacity());//string 类深拷贝for (int i 0; i sz; i){tmp [i] _start[i];}delete[] _start;}_start tmp;_finish sz _start;_end_of_storage _start n;}}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}size_t size()const {return _finish - _start;}size_t capacity()const {return _end_of_storage - _start;}//modifyvoid push_back(const T x){if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;}void pop_back(){erase(end()-1);}void insert(iterator pos, const T x){assert(pos _finish pos _start);if (_finish _end_of_storage){//防止迭代器失效size_t step pos - _start;size_t newcapacity capacity() 0 ? 0 : capacity() * 2;reserve(newcapacity);//防止迭代器失效pos _start step;}iterator end _finish - 1;while (end pos){*(end 1) *end;end;}*pos x;_finish;return pos;}void erase(iterator pos){assert(pos _finish pos _start);while (pos ! _finish){*pos *(pos 1);pos;}--_finish;return pos;}void resize(size_t n, const T val T()){if (n capacity()){_finish n _start;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}T operator[](size_t pos){assert(pos 0 pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos 0 pos size());return _start[pos];}private:iterator _start;iterator _finish;iterator _end_of_storage;};}
