成都建站模板公司,wordpress 预订 插件,网站seo解决方案,专业做婚庆的网站cplusplus.com/reference/vector/vector/https://cplusplus.com/reference/vector/vector/
vector在实际中非常的重要#xff0c;在实际中我们熟悉常见的接口就可以#xff0c;有了string的基础#xff0c;vector其实大体使用方法上二者是类似的#xff1a;
这里我们先给…cplusplus.com/reference/vector/vector/https://cplusplus.com/reference/vector/vector/
vector在实际中非常的重要在实际中我们熟悉常见的接口就可以有了string的基础vector其实大体使用方法上二者是类似的
这里我们先给出我们简单模拟实现时所用的成员函数
private:iterator _start;iterator _finish;iterator _end_of_storage;
下文在介绍与string实现方式基本相同的地方或者用法与string中相同函数基本一致的地方均会直接以表格加实现代码的方式进行介绍以便于我们重点介绍vector中我们需要了解的两个新知识迭代器失效和更深层次的深浅拷贝问题。
一vector的定义
1.1(constructor)构造函数声明
cplusplus.com/reference/vector/vector/vector/https://cplusplus.com/reference/vector/vector/vector/其中我们需要重点掌握的是以下几个构造函数 以下是我们的简单实现代码
templateclass T
class vector
{
public: vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}templateclass InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){assert(first last);InputIterator itor first;for (; itor last; itor){push_back(*itor);}}vector(size_t n, const T value T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){resize(n, value);}vector(const vectorT v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());_finish _start v.size();for (size_t i 0; i size(); i){(*this)[i] v[i];}}vectorT operator(vectorT v){swap(this, v);return *this;}
}
其中的swap,push_back,resize以及reserve与string中的功能基本一样我们后面在来介绍实现它们 这里我们先不管它们如何实现。我们要重点说的是这里拷贝构造时遇到的深浅拷贝问题这里先埋个伏笔。
1.2vector iterator 的使用
cplusplus.com/reference/vector/vector/begin/
cplusplus.com/reference/vector/vector/end/ cplusplus.com/reference/vector/vector/rbegin/ cplusplus.com/reference/vector/vector/rend/ typedef T* iterator;
typedef const T* const_iterator;
//iterator
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}
二vector 空间增长问题
cplusplus.com/reference/vector/vector/size/
cplusplus.com/reference/vector/vector/capacity/
cplusplus.com/reference/vector/vector/empty/
cplusplus.com/reference/vector/vector/resize/
cplusplus.com/reference/vector/vector/reserve/ size_t size()const
{return _finish - _start;
}size_t capacity()const
{return _end_of_storage - _start;
}
void resize(size_t n, const T pos T())
{while (size() n){push_back(pos);}if (n size())_finish _start n;
}
接下来的reserve我们需要单独拎出来讲先来看下我们在实现string的reserve时的模拟实现代码
void string::reserve(size_t n)
{if (n _capacity){char* tmp new char[n 1] {\0};strcpy(tmp, _str);delete[] _str;_str tmp;_capacity n;}
}
从string的模拟实现我们第一时间会想到去用memcpy来完成对ncapacity时的数据拷贝。当然这种方法对于我们所有的内置类型都没有问题比如vectorint,vectorchar等等 但如果是vectorstring这种成员元素是标准库类型的数据呢 如果我们只是简单的去拷贝每一个字节其实是对每一个元素的浅拷贝就像这样
void reserve(size_t n)
{if (n capacity()){size_t oldsize size();T* tmp new T[n];if (_start){memcpy(tmp, _start, oldsize * sizeof(T));delete[] _start;}_start tmp;_finish _start oldsize;_end_of_storage _start n;}
}
很明显的问题接下来tmp中的string对象都会指向一块随即空间也就是它们中的成员指针全部成了野指针。直接就会报错解决方法其实也很简单我们只需要改用for循环去拷贝数据即可虽然会些许浪费时间但是是我们简单模拟时一种较好的解决方法
void reserve(size_t n)
{
if (n capacity())
{size_t oldsize size();T* tmp new T[n];if (_start){for (size_t i 0; i oldsize; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start oldsize;_end_of_storage _start n;}
} 除此之外需要注意的点还有
1.capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。 2.reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代 价缺陷问题。 3.resize在开空间的同时还会进行初始化影响size。
三vector 增删查改 cplusplus.com/reference/vector/vector/reserve/
cplusplus.com/reference/vector/vector/push_back/ cplusplus.com/reference/vector/vector/pop_back/
cplusplus.com/reference/algorithm/find/?kwfind
cplusplus.com/reference/vector/vector/insert/
cplusplus.com/reference/vector/vector/erase/
cplusplus.com/reference/vector/vector/swap/ cplusplus.com/reference/vector/vector/operator[]/
//access
T operator[](size_t i)
{assert(i size());return _start[i];
}const T operator[](size_t i)const
{assert(i size());return _start[i];
}//modify
void push_back(T n)
{if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish n;_finish;
}void pop_back()
{assert(size());_finish--;
}void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_sstorage);
} TIPS:迭代器失效问题
注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
这里我们借助insert与erase来介绍
iterator insert(iterator pos, const T x){assert(pos _start pos _finish);if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator itor _finish;while (itor pos){*(itor 1) *itor;--itor;}*pos x;_finish;return pos;
}iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator itor pos;while (itor _finish - 1){*pos *(pos 1);}_finish--;return pos;
}
这里给出insert与erase主要是为了便于我们去对照vs与linux下实现代码的差异下面我们来看第一种失效
1.扩容引起的野指针
我们来看下面一组例子
void test_vector3()
{ELY::vectorint v1;//ELY是我实现的vector所在的命名空间v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//v1.push_back(4);for (auto e : v1){cout e ;}cout endl;int x;cin x;auto it find(v1.begin(), v1.end(), x);if (it ! v1.end()){v1.insert(it, 10 * x);cout *it endl;}for (auto e : v1){cout e ;}cout endl;
}
这串代码在vs下的运行结果如下图 显然此时我们的it已经失效因为扩容后it如果没有更新此时it指向的空间已经被释放了导致it迭代器成了野指针致使迭代器失效。
2.删除数据导致数据的挪动致使迭代器失效
void test_vector4(){std::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;int x;cin x;auto it find(v1.begin(), v1.end(), x);if (it ! v1.end()){v1.erase(it);cout *it endl;}} vs下面会直接报错 g 下面正常运行 再来看这样一组例子删除数据中的所有偶数
void test_vector4()
{std::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;auto it v1.begin();while (it ! v1.end()){if (*it % 2 0)v1.erase(it);it;}for (auto i : v1){cout i ;}cout endl;
}
vs下面还是直接报错: g上面运行 这里直接端错误。 换一组数据我们会发现偶数并没有被删干净。
///
从上述三个例子中可以看到SGI STL中迭代器失效后代码并不一定会崩溃但是运行 结果肯定不对如果it不在begin和end范围内肯定会崩溃的。
所以我们在使用迭代器的时候一定要注意迭代器失效的问题要及时更新我们的迭代器。
迭代器失效解决办法在使用前对迭代器重新赋值即可。
