网站建设pad版本是什么,小程序开发教程资料,秦皇岛海三建设一分公司,佛山网约车驾驶员资格证网上报名vector的基本使用和模拟实现 一、std::vector基本介绍
1.1 常用接口说明 std::vector是STL中的一个动态数组容器#xff0c;它可以自动调整大小#xff0c;支持在数组末尾快速添加和删除元素#xff0c;还支持随机访问元素。
以下是std::vector常用的接口及其说明#xf…vector的基本使用和模拟实现 一、std::vector基本介绍
1.1 常用接口说明 std::vector是STL中的一个动态数组容器它可以自动调整大小支持在数组末尾快速添加和删除元素还支持随机访问元素。
以下是std::vector常用的接口及其说明
push_back(): 在容器末尾添加元素
std::vectorint vec{1, 2, 3};
vec.push_back(4);pop_back(): 删除容器末尾的元素
std::vectorint vec{1, 2, 3};
vec.pop_back();size(): 返回容器中元素的个数
std::vectorint vec{1, 2, 3};
std::cout vec.size() std::endl; //输出3empty(): 判断容器是否为空 reserve(): 分配容器的内部存储空间但不改变元素个数
std::vectorint vec{1, 2, 3};
vec.reserve(10); // 分配10个int大小的空间其中的reserve接口你说是分配容器空间这是在堆上还是栈上开辟空间那如果重新分配的空间比现有空间小会发生什么以及重新分配的空间大于现有空间是在现有的基础上直接扩容还是舍弃现有空间将现有数据拷贝到新的空间上
新分配的内存空间位于堆上。如果重新分配的空间比现有空间小std::vector 会舍弃多余的元素。如果新分配的空间比现有空间大std::vector 会重新分配内存并将原有数据复制到新的内存空间中。
需要注意的是重新分配内存并将原有数据复制到新的内存空间中可能会导致性能问题。因此如果您能够预估存储的数据量建议在创建 std::vector 时就预分配足够的内存空间以避免频繁地重新分配内存。
resize(): 改变容器的元素个数
std::vectorint vec{1, 2, 3};
vec.resize(5);clear(): 删除容器中的所有元素 at(): 返回指定位置的元素
std::vectorint vec{1, 2, 3};
std::cout vec.at(1) std::endl; //输出2front(): 返回容器中第一个元素 back(): 返回容器中最后一个元素 begin(): 返回指向容器中第一个元素的迭代器end(): 返回指向容器中最后一个元素之后位置的迭代器
std::vectorint vec{1, 2, 3};
for (auto it vec.begin(); it ! vec.end(); it) {std::cout *it ;
}reverse()反转vector
std::vector::reverse 不是重新分配容器空间的接口它是用于反转容器中元素的顺序。也就是将容器中第一个元素和最后一个元素交换第二个元素和倒数第二个元素交换以此类推。
1.2 代码示例 1.2.1 遍历vector的几种方式
以下示例中分别提到了:下标[], 迭代器, 范围for, 反向迭代器
void test_vector1()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i 0; i v.size(); i) //1、下标[]{cout v[i] ;}vectorint::iterator it v.begin(); //2、迭代器while (it ! v.end()){cout *it ;it;}for (auto e : v) //3、范围for{cout e ;}vectorint::reverse_iterator rit v.rbegin(); // 4、反向迭代器while (rit ! v.rend()){cout *rit ;rit;}// 5 4 3 2 1
}不难发现用范围for访问的元素可以直接输出而通过for循环从v.begin()开始的迭代器it却需要解引用。这是因为在范围for循环中迭代器是被自动解引用的。
在范围for循环中循环变量的类型是根据容器元素的类型自动推导出来的而不是容器的迭代器类型。对于std::vectorint容器其元素类型是int因此在范围for循环中循环变量的类型是int而不是std::vectorint::iterator。
1.2.2 使用迭代器区间构造对象
vectorint v2(v.begin(), --v.end()); //利用迭代器区间构造对象————区间左闭右开
// 2 3 4
string s(hello world);
vectorchar v3(s.begin(), s.end()); //其它容器的迭代器只要类型匹配同样适用vectorint v4;
v4.assign(s.begin(), s.end()); //assign接口类似————中文意思为分配以上示例中提到了利用迭代器区间构建对象这种方式是左闭右开的例如(v.begin() 1, v.begin() 4)这代表下标为[2, 5)的元素。
只要迭代器的类型与vector所存储的元素类型相同就可以使用迭代器区间构建新的vector对象。例如上面提到的char类型的vector和char类型的string是可以匹配的。 1.2.3 vector的初始化
void test_vector2()
{vectorint v;v.reserve(10);//开空间改变容量但不初始化//错误访问——————下标引用操作符会检查插入位置是否合法即小于_size//for (size_t i 0; i 10; i)//{// v[i] i;//}//正确访问for (size_t i 0; i 10; i){v.push_back(i);}v.resize(20);//开空间初始化
}上述示例中提到了我在OJ题中经常弄糊涂的内容使用reserve进行初始化是最好的因为不会像resize那样擅自向vector中填入值但使用后记得不要使用下标引用操作符去访问而是使用push_back
1.2.4 insert\查找\排序
void test_vector3()
{int a[] { 1,2,3,4,5 };vectorint v(a, a 5);//头插v.insert(v.begin(), 0); //第一个参数传入的是迭代器//在2前面插入vectorint::iterator pos find(v.begin(), v.end(), 2); //find函数位于算法库中algorithmif (pos ! v.end()) //查找失败会返回end位置的迭代器{v.insert(pos, 20);}// 0 1 20 2 3 4 5 //sort排序sort(v.begin(), v.end()); // 0 1 2 3 4 5 20 sort(v.begin(), v.end(), greaterint()); //greaterint是一个仿函数类需要调用库函数是functional// 20 5 4 3 2 1 0
}上述例子注释写得很清楚印象最深的是二叉树后序遍历可以巧用头插获取返回结果。下面主要讲解sort的第三个参数
sort函数的第三个参数是可选的比较函数用于指定排序时的元素比较规则。当不指定比较函数时默认使用小于号进行比较即升序。
在sort(v.begin(), v.end(), greaterint())中greaterint()是一个函数对象用于指定降序排序的比较规则。greaterint()是一个模板类它重载了函数调用运算符operator()实现了比较规则。对于两个元素x和y如果greaterint()(x, y)返回true则x会被排在y之前。
因此sort(v.begin(), v.end(), greaterint())实现了对容器v进行降序排序的操作greaterint()是用于指定比较规则的函数对象它实现了元素的比较运算。
下面是一个简单的实现
templatetypename T
struct greater
{bool operator()(const T x, const T y) const{return x y;}
};这个定义了一个模板类greater它有一个函数调用运算符operator()。operator()接受两个参数x和y表示要比较的两个元素它的返回值是一个bool类型表示x是否应该排在y之前。在这个实现中operator()的比较规则是x大于y即从大到小排序。
1.2.5 erase删除
void test_vector4()
{int a[] { 1,2,3,4,5 };vectorint v(a, a 5);//头删v.erase(v.begin()); //参数传入下标位置的迭代器或迭代器区间//删除2vectorint::iterator pos find(v.begin(), v.end(), 2);if (pos ! v.end()){v.erase(pos);}
}上述例子中主要写了erase的使用方式参数是一个vector的迭代器。
二、vector模拟实现 这个 vector 类中包含了构造函数、拷贝构造、使用迭代器区间初始化的构造函数、析构。
实现了普通迭代器和只读迭代器及其对应的begin()和end()函数。
这个类中的成员变量为私有类型的普通迭代器类型的。记录了vector开始位置、最后一个数据的下一个位置、最大容量的下一个位置。
size()和capacity()能返回容器的元素个数和已开辟空间大小。
reserve()用于为容器重新分配空间如果分配的空间小于现有空间容量则不处理。否则会重新分配空间拷贝现有数据到新空间并修改成员变量。
insert()用于向容器中插入元素插入时需要将所在位置及其以后的元素全部向后移动移动时是从后往前。
erase()用于删除某个元素参数为要删除元素的迭代器。删除后还需要从前往后开始逐一将元素向前移动。
resize()用于调整空间大小并将未初始化的位置赋予指定的值。当调整的空间小于现有元素个数会舍弃掉多出的元素。当调整的大小介于元素个数和有效空间之间时会初始化这些多出来的部分。当调整的大小大于有效空间时会重新开辟空间并将现有数据拷贝过去然后初始化多余部分。
其他接口比较简单就不再单独描述。 templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());for (const auto e : v) {push_back(e);}}template class InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (first ! last) {push_back(*first);first;}}~vector() {delete[] _start;_start _finish _endofstorage nullptr;}iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin()const {return _start;}const_iterator end()const {return _finish;}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t num) {if (num capacity()) {size_t sz size();T* tmp new T[num];memcpy(tmp, _start, sz * sizeof(T));_start tmp;_finish _start sz;_endofstorage _start num;}}iterator insert(iterator pos, const T num){assert(pos begin() pos end());if (_finish _endofstorage) {size_t len pos - _start;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 num;_finish;return pos;}iterator erase(iterator pos) {assert(pos begin() pos end());//删除指定下标的数据并把其后的数据依次向前挪动iterator it pos 1;while (it ! end()){*(it - 1) *it;it;}--_finish;return pos;}void push_back(const T num){insert(end(), num);}T operator[](size_t i) {assert(i size());return *(_start i);}void swap(vectorT v) {std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._endofstorage, _endofstorage);}vectorT operator(vectorT v) {swap(v);return *this;}void resize(size_t n, const T val T()) {//开的空间小于size把超出范围的舍弃介于size和capacity初始化_finish以后的空间//大于capacity要重新开空间并且初始化_finish以后的空间if (n size()){_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish _start n) {*_finish val;_finish;}}}private:iterator _start;iterator _finish;iterator _endofstorage;};三、reverse浅拷贝Bug
不难发现在上述模拟实现的vector::reverse()中如果模版类型T为std::string那string中含有一些指针成员变量通过memcpy将其浅拷贝到新空间后又进行了一次delete在生命周期结束时也会进行delete就会造成崩溃。
3.1 解决方案
既然要销毁原有空间那为何不通过std::move将左值转换为右值然后拷贝到新空间去。
下面通过伪代码进行举例
template typename T
void MyVectorT::reserve(size_t newCapacity)
{if (newCapacity m_capacity)return;T* newData new T[newCapacity];for (size_t i 0; i m_size; i){newData[i] std::move(m_data[i]); // 深复制}delete[] m_data;m_data newData;m_capacity newCapacity;
}上述代码没有考虑使用迭代器成员变量容量和有效数据数量均为size_t类型数据类型为T*
在这个实现中我们使用了 std::move 函数将 m_data[i] 的内容移动到 newData[i] 中从而进行深复制避免了多个 std::string 对象共享同一块内存空间的问题。同时在析构函数中也只需要简单地使用 delete[] 删除 m_data 指向的内存即可。
3.2 move函数
std::move 是一个 C11 中引入的函数它能够将一个对象的值转移到另一个对象中同时将原对象置于一种“移动状态”从而避免不必要的对象复制和销毁。
std::move 本质上是将一个左值引用转换成右值引用。在 C 中左值引用是指向左值的引用右值引用是指向右值的引用。左值是可以取地址的、有持久性的、具名的、具有明确定义的生命周期的值而右值则是无法取地址的、临时的、没有名称的、生命周期不确定的值。在 C11 中我们可以通过使用 运算符来声明右值引用。
具体来说当我们调用 std::move 函数时它将接受一个左值引用并返回一个右值引用表示该对象的值可以被移动。通常情况下我们会将返回的右值引用绑定到另一个对象上从而将原对象的值移动到新对象中。例如
std::vectorint v1{1, 2, 3};
std::vectorint v2 std::move(v1); // 将 v1 的值移动到 v2 中需要注意的是在使用 std::move 移动对象时只会移动对象的值也就是说会将对象的成员变量的值复制到新的内存位置但不会复制对象的状态比如对象的引用计数、对象的资源句柄等等。移动完成后原对象的值会被置为“移后”的状态这个状态下对象的行为是未定义的我们不能再对其进行读取或修改。在移动一个对象之后如果我们需要继续使用该对象就必须重新对其进行赋值或初始化。
