做全国性的app网站推广多少,快速建设企业门户网站,十大计算机培训学校,怎么做二维码进网站vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问#xff0c;和数组一样高效。但是又不像数组#xff0c;它的大小是可以动态改变的#xff0c;而…vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3. 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4. vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5. 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6. 与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。
参考侯捷老师《STL源码刨析》这本书画的 Vector的一些接口
namespace MyVector
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin();iterator end();const_iterator cbegin() const;const_iterator cend() const; // 初始化vector();// 析构~vector();vector(int n, const T value T());vector(size_t n, const T val T());//类模板的成员函数可以是函数模板templateclass InputIteratorvector(InputIterator first, InputIterator last);vector(const vectorT v);vectorT operator (vectorT v);size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T value T());T operator[](size_t pos);const T operator[](size_t pos)const;bool empty();void push_back(const T x);void pop_back();void swap(vectorT v);iterator insert(iterator pos, const T x);iterator erase(iterator pos);private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr;// 指向存储容量的尾};
}
iterator begin() iterator begin(){return _start;}iterator end() iterator end(){return _finish;}const_iterator cbegin() const_iterator cbegin(){return _start;}const_iterator cend() const const_iterator cend() const{return _finish;} 四个比较简单的迭代器 vector() vector():_start(nullptr),_finish(nullptr), _endOfStorage(nullptr){}
~vector() ~vector(){delete[] _start;_start _finish _endOfStorage;} 初始化与析构 //类模板的成员函数可以是函数模板templateclass InputIterator // InputIterator定义的一个迭代器类型vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first ! last){push_back(*first);first;}}
vectorT operator (vectorT v) vectorT operator (vectorT v){swap(v);return *this;} // v1 v3 size_t size() const size_t size() const{return _finish - _start;} // 有效数据的尾减去数据块的开始就是元素个数 size_t capacity() const size_t capacity() const{return _endOfStorage - _start;} // 开辟空间的容量 void reserve(size_t n) void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t old_size size();for (size_t i 0; i old_size; i){tmp[i] _start[i]; // 深拷贝}delete[] _start;_start tmp; // 老的_start已经失效更新一下_finish tmp old_size;_endOfStorage tmp n;}}
void resize(size_t n, const T value T()) void resize(size_t n, const T value T()){if (n size()) // 超过就扩容{reserve(n);while (_finish _start n){*_finish value;_finish;}}else{_finish _start n;}}
vector(const vectorT v) vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}} // v2(v1) 用已经存在的 v1 去初始化 v2 T operator[](size_t pos)
const T operator[](size_t pos)const T operator[](size_t pos){assert(pos size()); // 保证下标为有效数据return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}
iterator insert(iterator pos, const T x) iterator insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);if (_finish _endOfStorage){size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos _start len;}iterator it _finish - 1;while (it pos){*(it 1) *it;--it;}*pos x;_finish;}
iterator erase(iterator pos) iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator it pos 1;while (it _finish){*(it - 1) *it;--it;}--_finish;return pos;}
vector(int n, const T value T()) vector(int n, const T value T()){reserve(n);for (size_t i 0; i n; i){push_back(value);}}
vector(size_t n, const T val T()) vector(size_t n, const T val T()){reserve(n);for (size_t i 0; i n; i){push_back(val);}}
bool empty() bool empty(){return _start _finish;}
void push_back(const T x) void push_back(const T x){insert(end(), x);}
void pop_back() void pop_back(){erase(end() - 1);}void swap(vectorT v) void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}
完整代码
#pragma once#include assert.hnamespace bit
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin(){return _start;}const_iterator cend() const{return _finish;}// construct and destroyvector():_start(nullptr),_finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T value T()){reserve(n);for (size_t i 0; i n; i){push_back(value);}}vector(size_t n, const T val T()){reserve(n);for (size_t i 0; i n; i){push_back(val);}}//类模板的成员函数可以是函数模板templateclass InputIteratorvector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first ! last){push_back(*first);first;}}vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}}vectorT operator (vectorT v){swap(v);return *this;}~vector(){delete[] _start;_start _finish _endOfStorage;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t old_size size();for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish tmp old_size;_endOfStorage tmp n;}}void resize(size_t n, const T value T()){if (n size()){reserve(n);while (_finish _start n){*_finish value;_finish;}}else{_finish _start n;}}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}bool empty(){return _start _finish;}void push_back(const T x){insert(end(), x);}void pop_back(){erase(end() - 1);}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){size_t len pos - _start;reserve(capacity() 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos _start len;}iterator it _finish - 1;while (it pos){*(it 1) *it;--it;}*pos x;_finish;}iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator it pos 1;while (it _finish){*(it - 1) *it;--it;}--_finish;return pos;}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr;// 指向存储容量的尾};}
测试代码
#include iostream
#includealgorithm
#includevector#include Vector.husing namespace std;int main()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);cout v.size() endl;cout v.capacity() endl;for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;for (auto e : v){cout e ;}cout endl;v.reserve(30);cout v.capacity() endl;vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;vectorint v1(v);v1.push_back(100);v1.push_back(200);v1.pop_back();for (auto e : v1){cout e ;}
}
