网站优化预算,创意江苏网站建设,网站建设公司企业网站,wordpress 归类插件目录 一、vector的介绍二、 标准库中的vector2.1 vector的常见接口说明2.1.1 vector对象的常见构造2.1.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/vector/vector/vector/)2.1.1.2 [有参构造函数#xff08;构造并初始化n个val#xff09;](https://legacy.… 目录 一、vector的介绍二、 标准库中的vector2.1 vector的常见接口说明2.1.1 vector对象的常见构造2.1.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/vector/vector/vector/)2.1.1.2 [有参构造函数构造并初始化n个val](https://legacy.cplusplus.com/reference/vector/vector/vector/)2.1.1.3 [有参构造函数使用迭代器进行初始化构造](https://legacy.cplusplus.com/reference/vector/vector/vector/)2.1.1.4 [拷贝构造函数](https://legacy.cplusplus.com/reference/vector/vector/vector/) 2.1.2 vector iterator 的使用2.1.2.1 [begin()函数](https://legacy.cplusplus.com/reference/vector/vector/begin/) [end()函数](https://legacy.cplusplus.com/reference/vector/vector/end/)2.1.2.2 [rbegin()函数](https://legacy.cplusplus.com/reference/vector/vector/rbegin/) [rend()函数](https://legacy.cplusplus.com/reference/vector/vector/rend/) 2.1.3 vector对象的容量操作2.1.3.1 [size()函数](https://legacy.cplusplus.com/reference/vector/vector/size/)2.1.3.2 [capacity()函数](https://legacy.cplusplus.com/reference/vector/vector/capacity/)2.1.3.3 [empty()函数](https://legacy.cplusplus.com/reference/vector/vector/empty/)2.1.3.4 [resize()函数](https://legacy.cplusplus.com/reference/vector/vector/resize/)2.1.3.5 [reserve()函数](https://legacy.cplusplus.com/reference/vector/vector/reserve/)2.1.3.6 vector空间增长问题 2.1.4 vector对象的增删查改及访问2.1.4.1 [operator[]](https://legacy.cplusplus.com/reference/vector/vector/operator%5B%5D/)2.1.4.2 [push_back()函数](https://legacy.cplusplus.com/reference/vector/vector/push_back/)2.1.4.3 [pop_back()函数](https://legacy.cplusplus.com/reference/vector/vector/pop_back/)2.1.4.4 [find()函数](https://legacy.cplusplus.com/reference/algorithm/find/)2.1.4.5 [insert()函数](https://legacy.cplusplus.com/reference/vector/vector/insert/)2.1.4.6 [erase()函数](https://legacy.cplusplus.com/reference/vector/vector/erase/)2.1.4.7 [swap()函数](https://legacy.cplusplus.com/reference/vector/vector/swap/)2.1.4.8 [front()函数](https://legacy.cplusplus.com/reference/vector/vector/front/) [back()函数](https://legacy.cplusplus.com/reference/vector/vector/back/) 2.1.5 vector迭代器失效问题 三、vector 深度剖析及模拟实现3.1 vector 中 reserve 和 resize 的实现3.2 vector 中 size、capacity 和 empty 的实现3.3 vector 默认成员函数的实现3.4 vector 中 迭代器 和 范围构造函数 的实现3.5 vector 中 insert 、erase、push_back 和pop_back 的实现3.6 vector 中 operator[] 的实现3.7 vector 实现中使用memcpy拷贝问题3.8 vector 实现汇总及函数测试 结尾 一、vector的介绍
vector的文档介绍
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好 二、 标准库中的vector
2.1 vector的常见接口说明
2.1.1 vector对象的常见构造
2.1.1.1 无参构造函数
vector();int main()
{vectorint v;return 0;
}2.1.1.2 有参构造函数构造并初始化n个val
vector (size_type n, const value_type val value_type());int main()
{vectorint v(5,10);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.1.3 有参构造函数使用迭代器进行初始化构造
template class InputIteratorvector (InputIterator first, InputIterator last);使用迭代器进行初始化构造并不是只能使用对应容器的迭代器区间而是所有容器的迭代器区间都可以用来初始化。
int main()
{string s(I Love You);vectorint v(s.begin(),s.end());for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.1.4 拷贝构造函数
vector (const vector x);int main()
{vectorint v1(10,5);vectorint v2(v1);for (int i 0; i v2.size(); i){cout v2[i] ;}cout endl;return 0;
}2.1.2 vector iterator 的使用
2.1.2.1 begin()函数 end()函数 iterator begin();
const_iterator begin() const;
获取第一个数据位置的iterator/const_iteratoriterator end();
const_iterator end() const;
获取最后一个数据的下一个位置的iterator/const_iteratorint main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}2.1.2.2 rbegin()函数 rend()函数 reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
获取最后一个数据位置的reverse_iterator/const_reverse_iterator reverse_iterator rend();
const_reverse_iterator rend() const;
获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);vectorint::reverse_iterator it v.rbegin();while (it ! v.rend()){cout *it ;it;}cout endl;return 0;
}2.1.3 vector对象的容量操作
2.1.3.1 size()函数
size_type size() const;
获取数据个数int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);cout v.size() endl;return 0;
}2.1.3.2 capacity()函数
size_type capacity() const;
获取容量大小int main()
{vectorint v;int old v.capacity();cout 初始: v.capacity() endl;for (int i 0; i 100; i){v.push_back(i);if (old ! v.capacity()){old v.capacity();cout 扩容: v.capacity() endl;}}return 0;
}2.1.3.3 empty()函数
bool empty() const; 判断是否为空int main()
{vectorint v;cout v.empty() endl;v.push_back(1);cout v.empty() endl;return 0;
}2.1.3.4 resize()函数
void resize (size_type n, value_type val value_type());
是将字符串中有效字符个数改变到n个
如果 n 小于当前容器的大小
则容器会被截断为仅包含前 n 个元素
如果 n 大于当前容器的大小
则容器会被扩展到包含 n 个元素并使用 val 值填充新添加的元素。注意resize在改变元素个数时如果是将元素个数增多
可能会改变底层容量的大小如果是将元素个数减少底层空间总大小不变。int main()
{vectorint v(20,20);cout 初始: size: v.size() capacity: v.capacity() endl;v.resize(10);cout 缩小后: size: v.size() capacity: v.capacity() endl;v.resize(30, 5);cout 扩大后: size: v.size() capacity: v.capacity() endl;return 0;
}2.1.3.5 reserve()函数
void reserve (size_type n);
改变vector的capacityint main()
{vectorint v;cout 初始: v.capacity() endl;v.reserve(100);cout 扩容: v.capacity() endl;return 0;
}2.1.3.6 vector空间增长问题
capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。
// 测试vector的默认扩容机制
void TestVectorExpand()
{size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}
vs运行结果vs下使用的STL基本是按照1.5倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 3
capacity changed : 4
capacity changed : 6
capacity changed : 9
capacity changed : 13
capacity changed : 19
capacity changed : 28
capacity changed : 42
capacity changed : 63
capacity changed : 94
capacity changed : 141
g运行结果linux下使用的STL基本是按照2倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 4
capacity changed : 8
capacity changed : 16
capacity changed : 32
capacity changed : 64
capacity changed : 128// 如果已经确定vector中要存储元素大概个数可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{vectorint v;size_t sz v.capacity();v.reserve(100); // 提前将容量设置好可以避免一遍插入一遍扩容cout making bar grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}2.1.4 vector对象的增删查改及访问
2.1.4.1 operator[]
像数组一样访问数据reference operator[] (size_type n);const_reference operator[] (size_type n) const;int main()
{vectorint v(5, 10);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.4.2 push_back()函数
void push_back (const value_type val); 尾插int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.4.3 pop_back()函数
void pop_back(); 尾删int main()
{vectorint v;v.push_back(1);v.push_back(2);for (int i 0; i v.size(); i){ cout v[i] ; }cout endl;v.pop_back();for (int i 0; i v.size(); i){cout v[i] ;}return 0;
}2.1.4.4 find()函数
查找。注意这个是算法模块实现不是vector的成员接口
template class InputIterator, class TInputIterator find (InputIterator first, InputIterator last, const T val);int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);std::vectorint::iterator it;it find(v.begin(), v.end(), 3);if (it ! v.end())std::cout Element found in v: *it \n;elsestd::cout Element not found in v\n;return 0;
}2.1.4.5 insert()函数
iterator insert (iterator position, const value_type val);
insert()函数能够在position之前插入val并返回插入数据位置的 iterator void insert (iterator position, size_type n, const value_type val);
insert()函数能够在position之前插入 n 个 val template class InputIteratorvoid insert (iterator position, InputIterator first, InputIterator last);
insert()函数能够在position之前插入一段迭代器区间的数据 int main()
{vectorint v;string s(I Love You);v.push_back(1);v.push_back(2);for (int i 0; i v.size(); i){ cout v[i] ; }cout endl;// insert()函数能够在position之前插入val并返回插入数据位置的 iterator cout *(v.insert(v.begin(), 30)) endl;for (int i 0; i v.size(); i){cout v[i] ;}cout endl;// insert()函数能够在position之前插入 n 个 val v.insert(v.begin() 2, 5, 10);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;// insert()函数能够在position之前插入一段迭代器区间的数据 v.insert(v.begin() 5, s.begin(),s.end());for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.4.6 erase()函数
iterator erase (iterator position);
erase()函数能够删除在position位的的数据并返回删除数据后面数据位置的 iteratoriterator erase (iterator first, iterator last);
erase()函数能够删除在迭代器区间 [first,last) 的的数据并返回删除数据后面数据位置的 iterator int main()
{vectorint v;for (int i 0; i 10; i){v.push_back(i);}for (int i 0; i v.size(); i){cout v[i] ;}cout endl;// erase()函数能够删除在position位的的数据并返回删除数据后面数据位置的 iteratorcout *(v.erase(v.begin())) endl;for (int i 0; i v.size(); i){cout v[i] ;}cout endl;// erase()函数能够删除在迭代器区间 [first,last) 的的数据// 并返回删除数据后面数据位置的 iterator cout *(v.erase(v.begin(), v.begin() 5)) endl;for (int i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}2.1.4.7 swap()函数
void swap (vector x);
交换两个vector的数据空间int main()
{vectorint v1(4, 5);vectorint v2(5, 10);for (int i 0; i v1.size(); i){ cout v1[i] ; }cout endl;for (int i 0; i v2.size(); i){ cout v2[i] ; }cout endl;v1.swap(v2);for (int i 0; i v1.size(); i){cout v1[i] ;}cout endl;for (int i 0; i v2.size(); i){cout v2[i] ;}cout endl;return 0;
}2.1.4.8 front()函数 back()函数
访问vector中的第一个数据reference front();
const_reference front() const;访问vector中的最后一个数据reference back();
const_reference back() const;2.1.5 vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1,2,3,4,5,6 };auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。*/while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}指定位置元素的删除操作–erase
#include iostream
using namespace std;
#include vector
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
}erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。
以下代码的功能是删除vector中所有的偶数请问那个代码是正确的为什么
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}return 0;
}int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;}return 0;
}解答第一个main函数错误第二个main函数正确因为erase()函数返回的就是删除元素后面元素位置的迭代器it会导致跳过一个元素如果最后一个元素是偶数还会导致程序崩溃。
注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
// 1. 扩容之后迭代器已经失效了程序虽然可以运行但是运行结果已经不对了
int main()
{vectorint v{ 1,2,3,4,5 };for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;auto it v.begin();cout 扩容之前vector的容量为: v.capacity() endl;// 通过reserve将底层空间设置为100目的是为了让vector的迭代器失效v.reserve(100);cout 扩容之后vector的容量为: v.capacity() endl;// 经过上述reserve之后it迭代器肯定会失效在vs下程序就直接崩溃了但是linux下不会// 虽然可能运行但是输出的结果是不对的while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}程序输出
1 2 3 4 5
扩容之前vector的容量为: 5
扩容之后vector的容量为 : 100
0 2 3 4 5 409 1 2 3 4 5// 2. erase删除任意位置代码后linux下迭代器并没有失效
// 因为空间还是原来的空间后序元素往前搬移了it的位置还是有效的
#include vector
#include algorithm
int main()
{vectorint v{ 1,2,3,4,5 };vectorint::iterator it find(v.begin(), v.end(), 3);v.erase(it);cout *it endl;while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}
程序可以正常运行并打印
4 4
5
// 3: erase删除的迭代器如果是最后一个元素删除之后it已经超过end
// 此时迭代器是无效的it导致程序崩溃
int main()
{vectorint v{ 1,2,3,4,5 };// vectorint v{1,2,3,4,5,6};auto it v.begin();while (it ! v.end()){if (*it % 2 0)v.erase(it);it;}for (auto e : v)cout e ;cout endl;return 0;
}// 使用第一组数据时程序可以运行得到的结果是
1 3 5// 使用第二组数据时程序最终会崩溃
Segmentation fault三、vector 深度剖析及模拟实现 3.1 vector 中 reserve 和 resize 的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:void reserve(size_t n){// 这里先将 size()的值记录下来防止下面调用时_start改变导致错误int sz size();if (n capacity()){T* tmp new T[n];if (_start){// 这里不能使用memcpy函数拷贝memcpy函数只会浅拷贝// 如果遇到需要深拷贝的对象的时候会出错for (int i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endOfStorage _start n;}}// 分三种情况 n为新的元素个数// (1) n _size// (2) n _size n _capacity// (3) n _capacity// 第一种情况为缩短第二三种情况为增长// 但第二种情况不需要扩容第三种情况不需要// 由于resize内部当传入的参数小于_capacity 时不会扩容// 所以将第二三种情况放在一起void resize(size_t n, const T value T()){if (_start n _finish){_finish _start n;}else{reserve(n);for (size_t i size(); i n; i){*_finish value;_finish;}}}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.2 vector 中 size、capacity 和 empty 的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty() const{return _start _finish;}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.3 vector 默认成员函数的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:// 函数声明给了缺省值构造时会走初始化列表vector(){ }vector(int n, const T value T()){reserve(n);for (int i 0; i n; i){*_finish value;_finish;}}vector(const vectorT v){_start new T[v.capacity()];_finish _start v.size();_endOfStorage _start v.capacity();for (size_t i 0; i v.size(); i){*(_start i) v[i];}}vectorT operator (vectorT v){swap(v);return *this;}~vector(){delete[] _start;_start _finish _endOfStorage nullptr;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.4 vector 中 迭代器 和 范围构造函数 的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend() const{return _finish;}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish *first;_finish;first;}}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.5 vector 中 insert 、erase、push_back 和pop_back 的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:typedef T* iterator;iterator insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}for (size_t i size(); _start i pos; i--){*(_start i) *(_start i - 1);}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start);assert(pos _finish);int end size() - 1;for (int i pos - _start; i end; i){*(_start i) *(_start i 1);}--_finish;return pos;}void push_back(const T x){if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}void pop_back(){assert(_finish ! _start);_finish--;}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.6 vector 中 operator[] 的实现
#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:T operator[](size_t pos){return *(_start pos);}const T operator[](size_t pos)const{return *(_start pos);}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}3.7 vector 实现中使用memcpy拷贝问题
假设模拟实现的vector中的reserve接口中使用memcpy进行的拷贝以下代码会发生什么问题
int main()
{aj::vectorstring v;v.push_back(1111);v.push_back(2222);v.push_back(3333);return 0;
}问题分析
memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是自定义类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。 结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。 3.8 vector 实现汇总及函数测试
#pragma once#include iostream
#include assert.husing namespace std;namespace aj
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend() const{return _finish;}// construct and destroy// 函数声明给了缺省值构造时会走初始化列表vector(){ }vector(int n, const T value T()){reserve(n);for (int i 0; i n; i){*_finish value;_finish;}}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish *first;_finish;first;}}vector(const vectorT v){_start new T[v.capacity()];_finish _start v.size();_endOfStorage _start v.capacity();for (size_t i 0; i v.size(); i){*(_start i) v[i];}}vectorT operator (vectorT v){swap(v);return *this;}~vector(){delete[] _start;_start _finish _endOfStorage nullptr;}// capacitysize_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty() const{return _start _finish;}void reserve(size_t n){// 这里先将 size()的值记录下来防止下面调用时_start改变导致错误int sz size();if (n capacity()){T* tmp new T[n];if (_start){// 这里不能使用memcpy函数拷贝memcpy函数只会浅拷贝// 如果遇到需要深拷贝的对象的时候会出错for (int i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endOfStorage _start n;}}void resize(size_t n, const T value T()){if (_start n _finish){_finish _start n;}else{reserve(n);for (size_t i size(); i n; i){*_finish value;_finish;}}}///access///T operator[](size_t pos){return *(_start pos);}const T operator[](size_t pos)const{return *(_start pos);}///modify/void push_back(const T x){if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}void pop_back(){assert(_finish ! _start);_finish--;}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish , v._finish);std::swap(_endOfStorage , v._endOfStorage);}iterator insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);if (_finish _endOfStorage){reserve(capacity() 0 ? 4 : capacity() * 2);}for (size_t i size() ; _start i pos; i--){*(_start i) *(_start i - 1);}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start);assert(pos _finish);int end size() - 1;for (int i pos - _start; i end; i){*(_start i) *(_start i 1);}--_finish;return pos;}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};// 测试 reserve resizevoid test_vector1(){vectorint v1;v1.reserve(100);int cp v1.capacity();cout 初始: cp endl;for (int i 0; i 100; i){v1.push_back(i);if (cp ! v1.capacity()){cp v1.capacity();cout 扩容: cp endl;}}vectorint v2;v2.resize(100, 20);for (auto x : v2){cout x ;}}// 测试 push_back pop_back capacity sizevoid test_vector2(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto x : v1){cout x ;}cout endl;cout v1.size() endl;cout v1.capacity() endl;v1.pop_back();v1.pop_back();for (auto x : v1){cout x ;}cout endl;cout v1.size() endl;cout v1.capacity() endl;}// 测试 begin end 范围for 迭代器 []void test_vector3(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;vectorint::iterator it v1.begin();while( it ! v1.end()){(*it);cout *it ;it;}cout endl;for (auto x : v1){cout x ;}cout endl;}// 测试迭代器区间构造 n 个对象构造void test_vector4(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;string s(chineseperson);vectorint v2(s.begin(), s.end());for (size_t i 0; i v2.size(); i){cout v2[i] ;}cout endl;vectorint v3(10 , 520);for (size_t i 0; i v3.size(); i){cout v3[i] ;}cout endl;vectorstring v4;v4.push_back(5201314);v4.push_back(5201314);v4.push_back(5201314);v4.push_back(5201314);v4.push_back(5201314);for (size_t i 0; i v4.size(); i){cout v4[i] ;}cout endl;}// 测试拷贝构造 赋值void test_vector5(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;vectorint v2(v1);for (size_t i 0; i v2.size(); i){cout v2[i] ;}cout endl;vectorint v3(10, 520);for (size_t i 0; i v3.size(); i){cout v3[i] ;}cout endl;v2 v3;for (size_t i 0; i v2.size(); i){cout v2[i] ;}cout endl;}// 测试insert erasevoid test_vector6(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.insert(v1.begin(), 520);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.insert(v1.begin() v1.size(), 520);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.erase(v1.begin());for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.erase(v1.begin() v1.size()-1);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;}void test_vector7(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(4);v1.push_back(5);v1.push_back(6);vectorint::iterator it v1.begin();while (it ! v1.end()){if (*it % 2 0){it v1.erase(it);}else{it;}}for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;}
}结尾
如果有什么建议和疑问或是有什么错误大家可以在评论区中提出。 希望大家以后也能和我一起进步 如果这篇文章对你有用的话希望大家给一个三连支持一下
