一、vector是什么?
vector是表示可变大小数组的序列容器,它也采用连续存储空间来存储元素,因此可以采用下标对vector的元素进行访问,它的大小是动态改变的,vector使用动态分配数组来存储它的元素;
二、容器特性
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;
2.动态数组
支持对序列中的任意元素进行快速直接访问,甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;
3.能够感知内存分配器的
容器使用一个内存分配器对象来动态地处理它的存储需求;
三、vector的模拟实现
定义一个类:
- template<class T>
- class Vector
- {
- T* _start; //首元素地址
- T* _finish; //最后一个元素地址的下一个地址
- T* _endOfStorage; //空间的尾地址
- public:
- //成员函数
- };
构造函数
- Vector()
- :_start(nullptr)
- , _finish(nullptr)
- , _endOfStorage(nullptr)
- {}
-
- Vector(size_t n, const T& value = T())
- :_start(nullptr)
- , _finish(nullptr)
- , _endOfStorage(nullptr)
- {
- reserve(n);
- while (n--)
- {
- push_back(value);
- }
- }
- Vector(InputInterator first, InputInterator last)
- :_start(nullptr)
- , _finish(nullptr)
- , _endOfStorage(nullptr)
- {
- while (first != last)
- {
- pushBack(*first);
- ++first;
- }
- }
-
数据大小、空间大小
- size_t size() const
- {
- return _finish - _start;
- }
-
- size_t capacity() const
- {
- return _endOfStorage - _start;
- }
-
尾插
- void pushBack(const T& value)
- {
- if (_finish == _endOfStorage)
- {
- size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
- reverse(value);
- }
- *_finish = value;
- ++_finish;
- }
扩容
有资源进行拷贝时,使用深拷贝;类型为自定义类型时,发生浅拷贝,调用自定义类型析构函数,释放资源,导致资源二次释放,所以自定义类型的拷贝有资源时进行深拷贝;
深拷贝与浅拷贝的区别及应用
- void reserve(size_t n)
- {
- if (n > capacity())
- {
- size_t sz = size();
- T* arr = new T[n];
- if (_start)
- {
- memcpy(arr, _start, sizeof(T) * sz);
- delete[] _start;
- }
- //update
- _start = arr;
- _finish = _start + sz;
- _endOfStorage = _start + n;
- }
- }
改变数据大小
- void resize(size_t n, const T& val = T())
- {
- if (n > capacity())
- {
- reserve(n);
- }
- else if (n > size())
- {
- while (_finish != _start + n)
- {
- *_finish = val;
- _finish++;
- }
- }
- _finish = _start + n;
- }
位置插入值
- void insert(iterator pos, const T& val)
- {
- size_t sz = pos - _start;
- //检查位置
- if (pos >= _start && pos <= _finish)
- {
- //检查容量
- if (_finish == _endOfStoage)
- {
- size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();
- reserve(n);
- //更新迭代器
- pos = _start + sz;
- }
- //移动元素
- iterator end_u = _finish;
- while (end_u != pos)
- {
- *end = *(end_u - 1);
- --end_u();
- }
- //插入元素
- *pos = val;
- //更新位置
- ++_finish;
- }
- }
删除数据
- iterator erase(iterator pos)
- {
- //检查位置
- if (pos < _finish && pos >= _start)
- {
- //移动元素
- iterator start = pos + 1;
- while (start!=_finish)
- {
- *(start - 1) = *start;
- start++;
- }
- //更新
- --_finish;
- }
- return pos;
- }
- //返回删除数据的下一个元素的位置
operator[] 重载
- T& operator[](size_t pos)
- {
- if (pos >= 0 && pos < size())
- return _start[pos];
- }
operator= 重载
- Vector<T>& operator=(const Vector<T>& v)
- {
- if (this != &v)
- {
- delete[]_start;
- size_t n = v.capacity();
- _start = new T[n];
- for (size_t i = 0; i < v.capacity(); ++i)
- {
- _start[i] = v._start[i];
- }
- _finish = _start + v.size();
- _finish = _start + n;
- }
- return *this;
- }
迭代器
- //vector迭代器:T*
- 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()
- {
- if (_start)
- {
- delete[] _start;
- _start = _finish = _endOfStorage = nullptr;
- }
- }
总结
到此这篇关于c++ vector模拟实现的文章就介绍到这了,更多相关c++ vector模拟实现内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!