网站需要怎么做,做普通网站公司吗,助君网络科技,网商网#x1f4d8;北尘_#xff1a;个人主页 #x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上#xff0c;不忘来时的初心 文章目录 一、vector的介绍二、vector的模拟实现1、模拟实现2、测试结果 一、vector的介绍
vector的文… 北尘_个人主页 个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上不忘来时的初心 文章目录 一、vector的介绍二、vector的模拟实现1、模拟实现2、测试结果 一、vector的介绍
vector的文档介绍
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。
使用STL的三个境界能用明理能扩展 那么下面学习vector我们也是按照这个方法去学习 二、vector的模拟实现
1、模拟实现
#includeiostream
#includestring
#includeassert.h
using namespace std;
namespace zsc
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finsh;}const_iterator begin() const{return _start;}const_iterator end() const {return _finsh;}templateclass InputIteratorvector(InputIterator frist, InputIterator last){while (frist ! last){push_back(frist);frist;}}vector(size_t n, const T val T()){reserve(n);for (size_t i 0; i n; i){push_back(val);}}vector(int n, const T val T()){reserve(n);for (size_t i 0; i n; i){push_back(val);}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finsh, v._finsh);std::swap(_endofstorage, v._endofstorage);}vectorT operator(vectorT tmp){swap(tmp);return *this;}size_t size(){return _finsh - _start;}size_t capacity(){return _endofstorage - _start;}vector(){}~vector(){delete[] _start;_start _finsh _endofstorage nullptr;}T operator[](size_t pos){assert(pos size());return _start[pos];}void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t sz size();if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finsh _start sz;_endofstorage _start n;}}void resize(size_t n, const T val T()){if (n size()){_finsh _start n;}else{reserve(n);while (_finsh _start n){*_finsh val;_finsh;}}}void insert(iterator pos, const T x){assert(pos _start);assert(pos _finsh);if (_finsh _endofstorage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator end _finsh - 1;while (end pos){*(end 1) *(end);--end;}*pos x;_finsh;}iterator erase(iterator pos){assert(pos _start);assert(pos _finsh);iterator it pos 1;while (it _finsh){*(it - 1) *it;it;}--_finsh;return pos;}void push_back(const T x){if (_finsh _endofstorage){size_t sz size();size_t cp capacity() 0 ? 4 : capacity() * 2;T* tmp new T[cp];if (_start){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start tmp;_finsh _start sz;_endofstorage _start cp;}*_finsh x;_finsh;}private:iterator _start nullptr;iterator _finsh nullptr;iterator _endofstorage nullptr;};void test1(){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);cout push_back and pop_back :;for (auto i : v)cout i ;cout endl;v.insert(v.begin() 2, 30);cout insert:;for (auto x : v)cout x ;cout endl;v.erase(v.end() - 1);cout erase:;for (auto x : v)cout x ;cout endl;v.reserve(20);cout reserve(20): size: v.size() capacity: v.capacity() endl;v.resize(100);cout resize(100): size: v.size() capacity: v.capacity() endl;}
}int main()
{zsc::test1();return 0;
}2、测试结果
