C++ vector实现
2021/7/12 11:08:16
本文主要是介绍C++ vector实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 引入
- 一、成员变量
- 二、主要接口模拟
- 2.1 size && capacity && operator[ ]
- 2.2 begin && end
- 2.3 默认成员函数
- reserve && resize
- 插入删除操作
引入
vector英文翻译是向量,这个名字可以说是很形象了。vector在C++中是一个可以动态增容的数组,它像string一样拥有一个随机的迭代器,支持随机访问vector的位置。vector可以说就是C语言中的顺序表,但是又有顺序表不具有的优点,比如使用了模板,支持不同类型的vector同时存在。
一、成员变量
每写一个类,我认为应该优先考虑的就是成员变量。但是成员变量往往需要在成员函数的实现过程中确认。还好STL中有实现好的一份,我们参考一下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | namespace my_stl //因为我的vector名字和stl里相同,所以namespace封装一下 { template< class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; //指向vector的第一个位置 iterator _finish; //指向vector的最后一个位置的下一个位置 iterator _end_of_storage; //指向vector的容量的最后一个位置的下一个位置 }; } |
二、主要接口模拟
我们顺着stl的实现来一步一步走。较简单的只提供代码,不做讲解。
2.1 size && capacity && operator[ ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | size_t size() const{ return _finish - _start; } size_t capacity() const{ return _end_of_storage - _start; } T& operator[](size_t pos){ assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const{ assert(pos < size()); return _start[pos]; } |
2.2 begin && end
1 2 3 4 5 6 7 8 9 10 11 12 13 | iterator begin(){ return _start; } iterator end(){ return _finish; } // const迭代器 const_iterator begin() const{ return _start; } const_iterator end() const{ return _finish; } |
2.3 默认成员函数
构造函数有好几个版本,只实现几个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | // 无参构造,禁止隐式类型转换 explicit vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} //一个参数n的构造函数 explicit vector(size_t n, const T& val = T()) :_start(new T[n]), _finish(_start), _end_of_storage(_start + n) { for(size_t i = 0; i < n ; ++i){ *(_finish++) = val; } } //迭代器构造函数 template <class InputIterator> vector (InputIterator first, InputIterator last) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){ reserve(last - first); while(first != last){ push_back(*first); ++first; } } //initializer_list vector(initializer_list< T > il){ auto it = il.begin(); while(it != il.end()){ push_back(*it); ++it; } } |
几点注意:前两个构造函数不接受隐式类型转换。后两个代码有大量重复。可以重写。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public: template < class InputIterator> vector (InputIterator first, InputIterator last) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){ reserve(last - first); range_initialize(first, last); } vector(initializer_list< T > il){ range_initialize(il.begin(), il.end()); } // 复用的部分 private: template< class InputIterator> void range_initialize(InputIterator first, InputIterator last){ while(first != last){ push_back(*first); ++first; } } |
拷贝构造
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | // traditional 写法 vector(const vector< T >& v) :_start(new T[v.capacity()]) ,_finish(_start) ,_end_of_storage(_start + v.capacity()) { for (size_t i = 0; i < v.size (); ++i){ *(_finish++) = v[i]; } } // mordern写法 vector(const vector<T>& v) //拷贝构造现代写法 :_start(nullptr),_finish(nullptr),_end_of_storage(nullptr) { reserve(v.capacity()); //提前开好空间 for (const auto& e : v) push_back(e); } // 更mordern的写法 void swap(vector< T >& v){ ::swap(_start, v._start); ::swap(_finish, v._finish); ::swap(_end_of_storage, v._end_of_storage); } vector(const vector< T >& v) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { vector< T > tmp(v.begin(), v.end()); swap(tmp); } // C++ 11 移动构造 vector(vector< T >&& v) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { swap(v); } |
代码中出现的未知函数的实现在下面给出。
operator=
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | // traditional 写法 vector< T >& operator=(const vector< T >& v){ if(this != &v){ vector< T > tmp(v); swap(tmp); } return *this; } // modern写法 pass-by-value vector< T >& operator=(vector< T > v){ if(this != &v) swap(v); return *this; } // C++ 11 移动赋值 vector< T >& operator=(vector< T >&& v){ swap(v); return *this; } |
实际上移动赋值可以不用写,因为赋值的现代写法就包括了移动赋值。
析构
1 2 3 4 5 6 7 | void clear() noexcept{ delete[] _start; _start = _finish = _end_of_storage = nullptr; } ~vector(){ clear(); } |
reserve && resize
vector是可以动态增容的数组,所以自然提供增容函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | void reserve(size_t n){ assert(n > capacity()); size_t sz = size(); T* tmp = new T[n]; //开空间 delete[] _start; //释放旧空间 for(size_t i = 0; i < size (); ++i){ tmp[i] = _start[i]; } //拷贝数据,利用赋值 + 循环 _start = tmp ; _finish = _start + sz; //这里不能加上 size(),不然有问题 _end_of_storage = _start + n; } void resize(size_t n, const T& val = T ()){ if(n <= size()){ _finish = _start + n; return ; } if(n > capacity()){ reserve(n); } for(size_t i = size(); i < n; ++i){ *(_finish++) = val; } } |
插入删除操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | void push_back(const T& val){ /*if(size() == capacity()){ size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } *(_finish++) = val; */ insert(end(), val); } void pop_back(){ assert(size() > 0); --_finish; } iterator insert(iterator pos, const T& val = T()) //返回迭代器位置,防止迭代器失效 { size_t position = pos - _start; assert(pos >= _finish && pos <= _finish); if(size() == capacity()){ size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newCapacity); } iterator end = _finish; while(end >= _start + position){ *(end + 1) = *end; --end; } *(_start + position) = val; ++_finish; return _start + position; } iterator erase(iterator pos){ assert(pos >= _finish && pos <= _finish); iterator begin = pos; while(begin < _finish){ *begin = *(begin + 1); ++begin; } --finish; return pos; } |
迭代器失效问题:当我们调用某些使容量变动的函数时,例如reserve,push_back,可能会引起迭代器失效。因为增容可能导致重新开辟空间,导致pos指向释放过的空间。
实际上,vector的删除操作也会导致迭代器失效。但是删除操作不会重新开辟空间。究其原因是pos迭代器对应的值被删除了,导致pos的值锁定的值变了,删除效果变了。
我们可以在使用前对迭代器重新赋值即可。
(全文完)
这篇关于C++ vector实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-12深入理解 ECMAScript 2024 新特性:Map.groupBy() 分组操作
- 2025-01-11国产医疗级心电ECG采集处理模块
- 2025-01-10Rakuten 乐天积分系统从 Cassandra 到 TiDB 的选型与实战
- 2025-01-09CMS内容管理系统是什么?如何选择适合你的平台?
- 2025-01-08CCPM如何缩短项目周期并降低风险?
- 2025-01-08Omnivore 替代品 Readeck 安装与使用教程
- 2025-01-07Cursor 收费太贵?3分钟教你接入超低价 DeepSeek-V3,代码质量逼近 Claude 3.5
- 2025-01-06PingCAP 连续两年入选 Gartner 云数据库管理系统魔力象限“荣誉提及”
- 2025-01-05Easysearch 可搜索快照功能,看这篇就够了
- 2025-01-04BOT+EPC模式在基础设施项目中的应用与优势