宁波网站建设开发公司,中国建设监理企业协会网站,深圳建设集团股份有限公司,职场社交网站怎么做目录 一、vector的数据结构
二、vector的构造
三、vector的增删查改及空间管理
四、全部代码 一、vector的数据结构
vector以线性连续空间为基础来定义数据结构以及扩展功能。vector的两个迭代器#xff0c;分别是start和finish#xff0c;分别指向配置得来的已被使用的空…目录 一、vector的数据结构
二、vector的构造
三、vector的增删查改及空间管理
四、全部代码 一、vector的数据结构
vector以线性连续空间为基础来定义数据结构以及扩展功能。vector的两个迭代器分别是start和finish分别指向配置得来的已被使用的空间。还有一个迭代器end_of_storage指向整块连续空间的尾端。
iterator _start nullptr;
iterator _finish nullptr;
iterator _endofstorage nullptr;
此处迭代器变量名前加‘_表示我们不是真正的vector而是模拟出来的
这些迭代器应该被private所修饰那么可以设计如下构造函数来提取vector的首尾这样既保护了迭代器又便于提取首位
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}
vector的实际配置大小要比需求量大一些以便将来可以扩充。也就是说vector的容量大小永远大于或者等于其大小。一旦其容量等于其大小即是满载当有新的元素加入时vector就要进行扩容。
示意图如下 二、vector的构造
vector的构造如下
(constructor)构造函数声明接口说明vector();无参构造vectorsize_type n, const value_type val value_type());构造并初始化n个valvector (const vector x);拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
我们来一一实现。
无参构造
vector()
{}
初始化n个构造
vector(size_t n, const T val T())
{resize(n, val);
}vector(int n, const T val T())
{resize(n, val);
}
拷贝构造
vector(const vectorT v)
{_start new T[v.capacity()];//memcpy(_start, v._start, sizeof(T)*v.size());for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_endofstorage _start v.capacity();
}
使用迭代器初始化构造
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}
除此之外也可以重载来实现构造原理同拷贝构造
vectorT operator(vectorT v)
{swap(v);return *this;
}
最后既然有构造函数那必然有析构函数呀
~vector()
{if (_start){delete[] _start;_start _finish _endofstorage nullptr;}
}
三、vector的增删查改及空间管理
vector的增删查改功能函数如下
vector增删查改接口说明push_back尾插pop_back尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[]像数组一样访问
要实现push_back我们先实现insert
iterator insert(iterator pos, const T x)
{assert(pos _start pos _finish);if (_finish _endofstorage){size_t len pos - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;
}
这样在设计push_back时直接调用insert函数就好
void push_back(const T x)
{insert(end(), x);
}
要实现pop_back不妨参考push_back的实现过程先实现erase
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator it pos 1;while (it ! _finish){*(it - 1) *it;it;}--_finish;return pos;
}
再直接调用erase即可实现pop_back
void pop_back()
{erase(--end());
}
要交换两个vector的数据空间的话把关键迭代器交换即可
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
operator[]的实现如下
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}
vector的空间管理功能如下
容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize改变vector的sizereserve改变vector的capacity
前三个都很简单返回相应的值即可
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endofstorage - _start;
}bool empyt() const
{return ((_endofstorage - _start) 0 ? true : false);
}
重点实现的是resize和reserve
resize如下
void resize(size_t n, const T val T())
{if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}
}
reserve如下
void reserve(size_t n)
{if (n capacity()){size_t sz size();T* tmp new T[n];if (_start){for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}
}
四、全部代码
全部代码如下
#includeassert.hnamespace bit
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T()){resize(n, val);}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}vector(){}vector(const vectorT v){_start new T[v.capacity()];for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_endofstorage _start v.capacity();}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vectorT operator(vectorT v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start _finish _endofstorage nullptr;}}void reserve(size_t n){if (n capacity()){size_t sz size();T* tmp new T[n];if (_start){for (size_t 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 val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}}void push_back(const T x){insert(end(), x);}void pop_back(){erase(--end());}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _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];}iterator insert(iterator pos, const T x){assert(pos _start pos _finish);if (_finish _endofstorage){size_t len pos - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);// 解决pos迭代器失效问题pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start 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;};
}
