阿里云网站备案登陆,上海网络技术有限公司,正规网站建设套餐报价,wordpress图片加速文章目录 vector的底层结构迭代器容量操作size()capacity()reserve()resize() 默认成员函数构造无参构造函数带参构造函数 析构拷贝构造赋值重载 operator[ ]插入删除操作insert()任意位置插入erase()任意位置删除push_back()尾插pop_back()尾删 vector的底层结构
我们的目的不… 文章目录 vector的底层结构迭代器容量操作size()capacity()reserve()resize() 默认成员函数构造无参构造函数带参构造函数 析构拷贝构造赋值重载 operator[ ]插入删除操作insert()任意位置插入erase()任意位置删除push_back()尾插pop_back()尾删 vector的底层结构
我们的目的不是去模拟实现vector而是更深入地理解vector的底层原理更好地提升自己。本篇将简单地模拟实现vector更好地理解它的构造和原理。参考vector使用说明
在C的STL中vector是最常用的容器之一底层是一段连续的线性内存空间泛型的动态类型顺序表可以支持随机访问。vector可以存储各种类型int、char、string等所以它是一种类模板可以套用各种类型。 STL标准库中vector的核心是这样定义的这里的alloc涉及到内存池的知识我们可以先不用管。 vector的底层会用三个指针利用三个指针相减来实现动态存储。 我们自己定义一个vector类
templateclass T
class vector
{
public:typedef T* iterator;//迭代器typedef const T* const_iterator;//常量迭代器
private:iterator _start;iterator _finish;iterator _end_of_storage;
}迭代器 vector的迭代器是一个原生指针,他的迭代器和string相同都是操作指针来遍历数据。 迭代器返回的是存储数据的起始位置和末尾的下一个位置区间是左开右闭的[_start, _finish) 实现了迭代器我们在代码测试时就可以使用范围for了。
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}容量操作
size()
size_t size() const
{return _finish - _start;
}capacity()
size_t capacity() const
{return _end_of_storage - _start;
}reserve()
这个函数十分重要因为vector许多地方都会用reserve()去扩容并且还有几个非常容易搞错的地方。
reserve只能扩容不能增容因此要进行判断是否需要扩容缩容就不进行操作。 扩容的步骤是申请一块更大的新空间再将旧空间数据移动到新空间中最后释放旧空间。 下面这种写法有什么问题
void reserve(size_t n)
{if (n capacity()){//申请新空间T* tmp new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * old_size);//释放旧空间delete[] _start;}_start tmp;_finish tmp size();_end_of_storage _start n;}
}错误一倒数第二行的_finish没有发生变化 看这段代码的最后三行_start先指向新空间的起始位置_finish再调用size()的话此刻的size()已经不是当初的size()了。size()的返回值是_finish - _start而原本的_start已经改变成了tmp此时_finish的值 _start _finish - _start _finish所以_finish没有发生变化。 解决方法有两种 1._start和_finish赋值的顺序调换一下先改变_finish再改变_start。 2.挪动数据前先保留原本的size() 我们这里采用第二种写法。 void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];size_t old_size size();//保留之前的sizeif (_start){memcpy(tmp, _start, sizeof(T) * old_size);delete[] _start;}_start tmp;_finish tmp old_size;_end_of_storage _start n;}
}2.不能用memcpy去拷贝内容而用赋值去拷贝内容。
对于int、char等内置类型可以使用memcpy不会出问题。对于自定义类型一般也没有问题但是对于动态申请资源的自定义类型memcpy就会发生浅拷贝导致一块空间析构两次。
比如vectorstring类型此时的T是string类型。上一篇我们了解过string的底层原理string底层用的是char*指针_str来存储字符串的地址因此需要动态申请空间。 所以我们是在申请的空间_start上面又申请了一块空间_str如果我们使用memcpy去拷贝_start中的内容到tmp中就会把申请的_str指向的地址拷贝给tmp这样_start和tmp中的_str就会指向同一块空间再执行delete[] _start;的时候就会执行string的析构函数把这块空间释放。 所以不能用memcpy浅拷贝解决方法 一个个遍历用赋值对于string这种深拷贝的类调用的是string的赋值重载完成深拷贝。 注意这里的string使用的是STL库中的string类。 void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];size_t old_size size();//保留之前的sizeif (_start){for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish tmp old_size;_end_of_storage _start n;}
}resize()
resize函数用于改变vector的大小调整vector中元素的数量。 n size()多余空间添加元素第二个参数 n size()删除n后面的元素。 void resize(size_t n, const T val T())//匿名对象
{if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;}}
}默认成员函数
构造
无参构造函数
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}使用
vectorint v1;
vectorstring s2;带参构造函数
vector(size_t n, const T val T())
{resize(n, val);
}使用
vectorint v1(10);//开辟5个int大小空间默认初始化为0
vectorint v2(10, 1);//开辟10个int大小空间并初始化为1
vectorstring s2(10,abc);//开辟10个string大小空间并初始化为abc析构
~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}
}拷贝构造
写法一尾插法
vector(const vectorT v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(v.size());for (auto e : v)//引用防止调用拷贝构造{push_back(e);}
}写法二常规法
vector(const vectorT v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start new T[v.size()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();
}赋值重载
和string一样我们直接复用标准库的swap函数。 注意用swap的话拷贝构造的参数要用传值传递不能改变实参且不能用const修饰发生交换 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;
}operator[ ]
两个重载版本一个普通对象调用一个const对象调用。
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}插入删除操作
insert()任意位置插入
插入之后如果原始空间发生扩容则pos指针仍指向原来空间的位置迭代器就会发生失效。所以我们需要在扩容之前保存pos的相对位置然后重新指向正确位置。
//insert后 迭代器可能会失效扩容就会引起失效
iterator insert(iterator pos, const T val)
{assert(pos _start pos _finish);if (_finish _end_of_storage){size_t len pos - _start;//保存pos相对位置防止失效size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);//解决迭代器失效问题pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;
}但是这样只保证了能正确插入数据。如果在使用时我们insert()一个元素后迭代器还会可能失效因为我们使用的传值传递形参不会影响实参。因此insert()函数返回pos这个位置的迭代器我们在外部使用的时候更新迭代器即可。
vectorint v(5, 1);
vectorint::iterator p v.begin() 1;
p v.insert(p, 10);//更新迭代器erase()任意位置删除
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos;while (end _finish - 1) {*end *(end 1);end;}_finish--;return pos;
}删除虽然不会扩容不用保存pos指针的相对位置但是删除一个元素后后面的元素都会向前移动此时迭代器指向空间虽然不变但内容变成了下一个元素我们在使用的时候要注意这个问题。
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(6);auto it v1.begin();//法一边使用边更新while (it ! v1.end()){if (*it % 2 0){it v1.erase(it);}else{it;}}//法二使用完将迭代器减一防止出现走两步的情况while (it ! v1.end()){if (*it % 2 0){v1.erase(it);it--;}it;}
}push_back()尾插
实现insert()函数后我们就可以直接复用。
void push_back(const T val)
{/*if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish val;*/insert(end(), val);
}pop_back()尾删
同样直接复用erase()让erase()自己判断合法性。
void pop_back()
{/*assert(size() 0);_finish--;*/erase(_finish - 1);
}vector模拟实现代码
