当前位置:首页 » 《休闲阅读》 » 正文

C++ : STL容器之vector剖析

26 人参与  2024年10月15日 09:21  分类 : 《休闲阅读》  评论

点击全文阅读


在这里插入图片描述

STL容器之vector剖析

一、构造函数与赋值(一)默认构造(二)拷贝构造(三)几个相同值构造(四)迭代器构造(五)initializer_list 构造(六)赋值重载 二、几个重要接口(一)reserve(二)resize(三)erase(四)insert 三、vector 的实现(完整源码)四、结束语

一、构造函数与赋值

(一)默认构造

采用初始化列表初始化,将三个迭代器都初始化为 nullptr,用三个指针的关系间接地控制size,capacity以及``data`.

vector(): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){}

(二)拷贝构造

拷贝构造可以用两种方式来实现,下面第一种是直接深拷贝的思路,另外还可以采用复用的方式。

这种方式可以使得拷贝后,size(), capacity()和拷贝的值相等

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){size_t n = v.size(), cap = v.capacity();reserve(cap);for (size_t i = 0; i < n; i++) {_start[i] = v[i];}_finish = _start + n;_endofstorage = _start + cap;}

这种方式采用复用,简洁了代码,可以多采用这种方式书写代码。

vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

(三)几个相同值构造

拷贝几个相同的值进入一个新的 vector,我们用了两个方式来实现,用 size_t来做参数,扩大n的取值范围,这样的化还需要重载一个函数 int,这是因为下面还有一个迭代器构造函数用函数模板实现,如果不这样的化,我们如果需要3个5的vector,就会自动调用函数模板,达不到预期,还会报错。

vector(size_t n, const T& value = T()){_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = value;}_finish = _start + n;_endofstorage = _start + n;}vector(int n, const T& value = T()){_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = value;}_finish = _start + n;_endofstorage = _start + n;}

(四)迭代器构造

成员函数也可以用函数模板来实现,可以用其它容器的迭代器来构造 vector,只要能够进行自动类型转换即可。

template<class InputIterator>vector(InputIterator first, InputIterator second){size_t n = second - first;_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = *(first + i);}_finish = _start + n;_endofstorage = _start + n;}
void test09(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);vector<int> v2(v1.begin(), v1.end());for (auto e : v2){cout << e << " ";}cout << endl;string s1("hello");vector<int> v3(s1.begin(), s1.end());for (auto e : v3){cout << e << " ";}cout << endl;vector<int> v4(10, 1);vector<double> v5(10, 1.1);for (auto e : v4){cout << e << " ";}cout << endl;}

在这里插入图片描述

(五)initializer_list 构造

initailzer_list是一个 std 库里面的一个对象,原理大概就是开一个数组用两个首尾指针来维护它

vector(initializer_list<T> il): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){int n = il.size();_start = new T[n];auto x = il.begin();for (int i = 0; i < n; i++) {_start[i] = *(x + i);}_finish = _start + n;_endofstorage = _finish;}

下面的实例中,v1先构造了一个initializer_list 对象,接着隐式类型转换,但是编译器优化为直接构造。而v2就是直接构造,接着下面演示了如何初始化这种对象。

void test11(){vector<int> v1 = { 1,2,3,4,5,6 };vector<int> v2({ 1,2,3,4,5,6 });auto il1 = { 1, 2, 3, 4, 5, 6 };initializer_list<int> il2 = { 1, 2, 3, 4, 5, 6 };for (auto x : il2) {cout << x  << " ";}}

(六)赋值重载

现代写法,这种写法简直拉满了,妙哉。
我们知道函数值传参会调用拷贝构造,我们只需要将需要赋值的对象和形参交换,就能达到赋值的效果,而函数结束后会调用析构函数自动释放形参的空间,妙不可言。

void swap(vector<T>& v1){std::swap(_start, v1._start);std::swap(_finish, v1._finish);std::swap(_endofstorage, v1._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}

二、几个重要接口

(一)reserve

在完成这个函数时,一定要采取for循环来依次赋值,如果使用 memcpy ,会发生一个深层次深浅拷贝的问题,如果_start指向的这片空间设计到动态内存开辟,那么会造成析构时释放两次的现象。

void reserve(size_t n){if (n > capacity()) {T* temp = new T[n];size_t cnt = size();if (_start) {for (size_t i = 0; i < cnt; i++) {temp[i] = _start[i];}delete[]_start;}_start = temp;_finish = _start + cnt;_endofstorage = _start + n;}}

(二)resize

设置有效元素个数,分情况讨论即可,如果 reserve 里面采用了memcpy 涉及到复用,这里也可能会报错。

void resize(size_t n, T value = T()){if (n <= size()) {int num = size() - n;_finish -= num;}else {reserve(n);    while (size() < capacity()) {push_back(value);}}}

(三)erase

删除指定元素,并且返回当前删除元素的下一个元素的迭代器,返回值需要注意,否则可能发生迭代器失效的问题。

iterator erase(iterator pos){assert(pos < _finish);assert(pos >= _start);for (auto x = pos + 1; x != _finish; x++) {*(x - 1) = *(x);}_finish--;return pos;}

(四)insert

插入一个元素,这里用到了 reserve,因此pos指向的元素可能已经是另外开辟的空间,造成迭代器失效,这种情况我们要记住pos_start的相对位置,这样我们才能在新的数组空间还原pos的位置。`

iterator insert(iterator pos, const T& value){assert(pos <= _finish);assert(pos >= _start);if (_finish == _endofstorage) {int n = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + n;}for (auto x = _finish; x > pos; x--) {*(x) = *(x - 1);}*(pos) = value;_finish++;return pos;}

三、vector 的实现(完整源码)

实现vector的时候,我们没有用 capacity size data 来定义,而是用了三个指针来间接地维护这几个值。

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<vector>#include<assert.h>using namespace std;namespace wgm {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;vector(): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){cout << "vector() 调用" << endl;}vector(initializer_list<T> il): _start(nullptr), _finish(nullptr), _endofstorage(nullptr){cout << "vector(initializer_list<T> il)调用" << endl;int n = il.size();_start = new T[n];auto x = il.begin();for (int i = 0; i < n; i++) {_start[i] = *(x + i);}_finish = _start + n;_endofstorage = _finish;}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){size_t n = v.size(), cap = v.capacity();reserve(cap);for (size_t i = 0; i < n; i++) {_start[i] = v[i];}_finish = _start + n;_endofstorage = _start + cap;}template<class InputIterator>vector(InputIterator first, InputIterator second){size_t n = second - first;_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = *(first + i);}_finish = _start + n;_endofstorage = _start + n;}vector(size_t n, const T& value = T()){_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = value;}_finish = _start + n;_endofstorage = _start + n;}vector(int n, const T& value = T()){_start = new T[n];for (int i = 0; i < n; i++) {_start[i] = value;}_finish = _start + n;_endofstorage = _start + n;}~vector() {if (_start) {delete[] _start;_start = _finish = _endofstorage = nullptr;}}T& operator[](size_t n) {assert(n < size());assert(n >= 0);return _start[n];}const T& operator[](size_t n) const{assert(n < size());assert(n >= 0);return _start[n];}void swap(vector<T>& v1){std::swap(_start, v1._start);std::swap(_finish, v1._finish);std::swap(_endofstorage, v1._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void reserve(size_t n){if (n > capacity()) {T* temp = new T[n];size_t cnt = size();if (_start) {for (size_t i = 0; i < cnt; i++) {temp[i] = _start[i];}delete[]_start;}_start = temp;_finish = _start + cnt;_endofstorage = _start + n;}}void resize(size_t n, T value = T()){if (n <= size()) {int num = size() - n;_finish -= num;}else {reserve(n);    while (size() < capacity()) {push_back(value);}}}void push_back(const T& x){if (_finish == _endofstorage) {/*int n = capacity();n = n == 0 ? 4 : n * 2;reserve(n);*/reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}bool empty() {return _start == _finish;}void pop_back(){assert(!empty());_finish--;}iterator insert(iterator pos, const T& value){assert(pos <= _finish);assert(pos >= _start);if (_finish == _endofstorage) {int n = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + n;}for (auto x = _finish; x > pos; x--) {*(x) = *(x - 1);}*(pos) = value;_finish++;return pos;}iterator erase(iterator pos){assert(pos < _finish);assert(pos >= _start);for (auto x = pos + 1; x != _finish; x++) {*(x - 1) = *(x);}_finish--;return pos;}private:iterator _start;iterator _finish;iterator _endofstorage;};}

四、结束语

相比于stringvector新加入的一些新的元素,但是大同小异,后面的学习中研究不同点即可,vector中的迭代器失效,以及深浅拷贝的问题在学习时需要注意。


点击全文阅读


本文链接:http://zhangshiyu.com/post/171952.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1