微网站建设找哪家好,久免费域名注册网站,photoshop手机版免费,网站建设交易中心大家好我是沐曦希#x1f495; 文章目录一、前言二、无参构造析构三、基础接口1.empty和clear2.size和capacity3.[]和iterator四、reserve和resize五、尾插尾删六、其他构造1.迭代器区间构造2.拷贝构造七、memcpy问题八、完整代码一、前言
在模拟实现容器时候#xff0… 大家好我是沐曦希 文章目录一、前言二、无参构造析构三、基础接口1.empty和clear2.size和capacity3.[]和iterator四、reserve和resize五、尾插尾删六、其他构造1.迭代器区间构造2.拷贝构造七、memcpy问题八、完整代码一、前言
在模拟实现容器时候我们需要的不是造一个更好的轮子而是在了解原理更好理解和运用容器。
那么通过查看源码抽出vector容器主题框架:
template class T, class Alloc alloc
class vector {typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;
protected:iterator start;iterator finish;iterator end_of_storage;
}本质上与T*a,size_t size,size_t capacity是类似的 对于size _finish - _start 对于capacity _endofstorage-_start
二、无参构造析构
无参构造
初始化值为空。
vector():_start(nullptr),_finish(nullptr),_endofstarge(nullptr)
{}析构
~vector()
{delete[] _start;_start _finish _endofstarge nullptr;
}三、基础接口
1.empty和clear
empty
bool empty()
{return _finish _start;
}clear
void clear()
{_finish _start; //这里可不能置为nullptr
}2.size和capacity
size
int size() const
{return _finish - _start;
}-capacity
int capacity() const
{return _endofstarge - _start;
}加const是让const类对象和非const类对象都能调用
3.[]和iterator
这里提供const和非const两个版本加const是只可读不能更改不加const是可读可写。
[]
T operator[](const size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](const size_t pos)
{assert(pos size())return _start[pos];
}iterator 同理普通迭代器和const迭代器版本,同理范围for循环此时也是可以实现的
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator beign()
{return _start;
}
const_iterator end()
{return _finish;
}四、reserve和resize
reserve
reserve最大问题是深拷贝开辟新空间进行赋值的时候如果直接使用memcpy是浅拷贝。
void reserve(size_t n)
{if (n capacity()){int Oldsize size();//size需要保存方便更改_finsihT* tmp new T[n];//为空不需要拷贝if (_start){for (size_t i 0; i Oldsize; i){tmp[i] _start[i];}}_start tmp;_finish _start Oldsize;_endofstarge _start n;tmp nullptr;}
}size()要保存
因为size _finish - _start_start已经改变了。而_finish没有改变那么size就是一个任意数了不再是原来的size了就需要在开始时候用Oldsize进行存储size
使用memcpy问题
memcpy拷贝数据是按字节来拷贝的属于浅拷贝对于需要在堆开辟空间的自定义类型存在问题多次释放同一块空间将导致程序崩溃 vectorvectorint vv;
vectorint v(4, 1);
//复用push_back尾插
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
//需要扩容成2倍
vv.push_back(v);
for (size_t i 0; i vv.size(); i)
{for (size_t j 0; j vv[i].size(); j){cout vv[i][j] ;}cout endl;
}resize
用n个数据初始化vector那么就要用n和size进行比对分情况讨论: 1、当n大于当前的size时将size扩大到n扩大的数据为val若val未给出则默认为容器所存储类型的默认构造函数所构造出来的值。 2、当n小于当前的size时将size缩小到n。
根据resize函数的规则进入函数我们可以先判断所给n是否小于容器当前的size若小于则通过改变_finish的指向直接将容器的size缩小到n即可否则先判断该容器是否需要增容然后再将扩大的数据赋值为val即可。
void resize(size_t n, const T value T())
{if (n size()){_finish _start n;}reserve(n); // reserve对于ncapacity是不会做任何事情的for (size_t i 0; i n - size(); i){_finish[i] value;}_finish _start n;
}resize的参数初始化值为T类型的构造这里可不能直接初始化为0要是T是自定义类型呢是vector呢所以这里如果T是vector的化调用的就是vector的构造函数。另外这里还需要注意的一点是构造vector的时候是匿名对象匿名对象具有常性不可修改所以要加上const修饰。对于内置类型比如int都是有构造函数的
五、尾插尾删
void push_back(const T value)
{if (_finish _endofstarge){size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish value;_finish;
}
void pop_back()
{assert(_start _finish);if (_finish _start){--_finish;}
}六、其他构造
1.迭代器区间构造
vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endofstarge(nullptr)
{while (first ! last){push_back(*first);//int不能解引用first;}
}类模板的成员函数可以是函数模板使之可以是任意类型的迭代器区间包括了自身的迭代器区间构造 另外初始化列表全部初始化为nullptr没有初始化就是随机值出现野指针 2.拷贝构造
初始化列表全都要初始化为nullptr否则就是随机值
//写法一
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstarge(nullptr)
{reserve(v.capacity());for (const auto e : v){push_back(e);}
}
//写法二
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstarge, v._endofstarge);
}
vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstarge(nullptr)
{vectorT tmp(v.begin(), v._end());swap(tmp);
}赋值重载
可以复用拷贝构造
//缺陷是不能自己拷贝自己
vector operator(vectorT v)
{swap(v);return *this;
}这种写法就是有一个小问题如果是自己拷贝自己呢加个判断没用因为此时已经传值传参过来了加个判断没啥意义了。但是这个问题不大我们允许存在平时自己也很少自己赋值自己。
另外这里是传值调用有人会说了传引用也可以啊此时如果是引用的话v2赋值给v1,v1不是v2的拷贝直接把v2换成了v1,v1换给了v2,v2本身已经发生变化了这不是赋值了。
七、memcpy问题
如果拷贝的是内置类型的元素memcpy即高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝指向同一块空间假设我们仍然在reserve接口中使用memcpy进行拷贝
int main()
{bite::vectorbite::string v;v.push_back(1111);v.push_back(2222);v.push_back(3333);return 0;
}问题分析
memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是内置类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。 结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。
八、完整代码
vector.h
#pragma once
#includeiostream
#includeassert.h
using namespace std;
namespace lj
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}iterator rbegin(){return _finish;}iterator rend(){return _start;}const_iterator rbegin() const{return _finish;}const_iterator rend() const{return _start;}// construct and destroyvector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}vector(int n, const T value T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t i 0; i n; i){push_back(value);}}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}vector(const vectorT v){int* tmp new T[v.capacity()];for (size_t i 0; i v.size(); i){tmp[i] v[i];}_start tmp;_finish _start v.size();_endofstorage _start v.capacity;}vectorT operator(vectorT v){vector tmp(v);_start _finish _endofstorage nullptr;swap(_start, tmp._start);swap(_finish, tmp._finish);swap(_endofstorage, tmp._endofstorage);}~vector(){delete[] _start;_start _finish _endofstorage nullptr;}// capacitysize_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n capacity()){int Oldsize size();T* tmp new T[n];if (_start){for (size_t i 0; i size(); i){tmp[i] _start[i];}}_start tmp;_finish _start Oldsize;_endofstorage _start n;tmp nullptr;}}void resize(size_t n, const T value T()){if (n size()){_finish _start n;}reserve(n);for (size_t i 0; i n - size(); i){_finish[i] value;}_finish _start n;}///access///T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}///modify/void push_back(const T x){if (_finish _endofstorage){int newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish x;_finish;}void pop_back(){assert(_start _finish);if (_finish _start){--_finish;}}void swap(vectorT v){vector tmp;tmp._start _start;_start v._start;v._start tmp._start;tmp._finish _finish;_finish v._finish;v._finish tmp._finish;tmp._endofstorage _endofstorage;_endofstorage v._endofstorage;v._endofstorage tmp._endofstorage;tmp._start tmp._finish tmp._endofstorage nullptr;}iterator insert(iterator pos, const T x){assert(pos _start);assert(pos _finish);size_t Olddel pos - _start;if (_finish _endofstorage){size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}pos _start Olddel;auto it _finish;while (it pos){*it *(it - 1);it--;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos _start);assert(pos _finish);auto it pos;while (it _finish){(*it) *(it 1);it;}--_finish;return pos;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endofstorage; // 指向存储容量的尾};void test_vector1(){vectorint v1(10, 2);for (auto e : v1){cout e ;}cout endl;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;v1.reserve(20);cout v1.size() endl;cout v1.capacity() endl;vectorint v2;for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;}void test_vector2(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout e ;}cout endl;vectorint v2(v1.rend(), v1.rbegin());for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v2.resize(10, 1);for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v2.resize(5);for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v2.resize(15, 2);vectorint::iterator it v2.begin();while (it v2.end()){cout (*it) ;it;}cout endl;for (size_t i 0; i v2.size(); i){cout v2[i] ;}cout endl;v2.pop_back();for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v2.swap(v1);cout ------------------ v1 -------------------- endl;for (auto e : v1){cout e ;}cout endl;cout v1.size() endl;cout v1.capacity() endl;cout ------------------ v2 -------------------- endl;for (auto e : v2){cout e ;}cout endl;cout v2.size() endl;cout v2.capacity() endl;v1.resize(15);cout v1.size() endl;cout v1.capacity() endl;v1.insert(v1.begin(), 1);v1.insert(v1.end(), 1);for (auto e : v1){cout e ;}cout endl;cout v1.size() endl;cout v1.capacity() endl;}
}
