![](http://zhangshiyu.com/zb_users/upload/2024/03/20240321182803171101688332142.png)
目录
前言vector容器代码实现内部成员简介构造函数拷贝函数析构函数迭代器相关容量相关元素访问vector的修改操作 源代码
前言
我们前面介绍了vector容器的概念以及对其基本使用进行了介绍,如果你在这里不知道vector是什么以及不知道如何使用的话,可以进入本人主页,在C++专栏里有介绍
为了对小白友好,在这我简单介绍一下
C++中的vector是一个动态数组容器,可以存储不同类型的元素。它提供了一系列的成员函数来方便地操作和管理数组。
以下是C++ vector容器的一些特点和功能:
动态大小:vector的大小可以根据需要动态调整,可以在运行时添加或删除元素。随机访问:可以通过索引直接访问vector中的元素,支持常数时间的随机访问。自动内存管理:vector会自动处理内存分配和释放,无需手动管理内存。插入和删除:可以在任意位置插入或删除元素,vector会自动调整其他元素的位置。迭代器支持:可以使用迭代器遍历vector中的元素。动态增长:当vector的容量不足时,会自动重新分配更大的内存空间,以容纳更多的元素。元素访问:可以使用下标运算符[]或at()函数来访问元素,也可以使用front()和back()函数分别获取第一个和最后一个元素。本章节主要对vector容器的手撕实现其简单功能
vector容器代码实现
内部成员简介
命名空间实现与库里vector的隔绝,实现自定义vector
namespace A{template<class T> //模版实现vector<类型>class vector //vector功能实现{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;....... //函数接口实现.......private:iterator _start;// 指向数据块的开始iterator _finish;// 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};}
构造函数
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(size_t n, const T& value = T())之后
vector(int n, const T& value = T())就不需要提供了,但是对于:
vector v(10, 5);
编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型
就不会走vector(size_t n, const T& value = T())这个构造方法,
最终选择的是:vector(InputIterator first, InputIterator last)
因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int
但是10和5根本不是一个区间,编译时就报错了
故需要增加如下构造方法
vector(int n, const T& value = T()): _start(new T[n]), _finish(_start + n), _endOfStorage(_finish){for (int i = 0; i < n; ++i){_start[i] = value;}}
拷贝函数
若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)只能是vector的迭代器
重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器
template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}_finish = it;}vector<T>& operator=(vector<T> v){swap(v);return *this;}
析构函数
~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}
迭代器相关
迭代器是vector中用于遍历元素的一种工具。通过迭代器,我们可以访问vector中的每个元素,并对其进行操作。
vector的迭代器有以下几种类型:
begin():返回指向vector第一个元素的迭代器。
end():返回指向vector最后一个元素之后位置的迭代器。
rbegin():返回指向vector最后一个元素的逆向迭代器。rend()
:返回指向vector第一个元素之前位置的逆向迭代器。
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}
容量相关
下面是vector的容量相关接口:
size()
:返回vector中元素的个数。capacity()
:返回当前vector可以容纳的元素个数,即当前分配的内存空间大小。max_size()
:返回vector能够容纳的最大元素个数,这个值取决于系统的限制。resize()
:改变vector的大小,可以增加或减少元素的个数。reserve()
:预留内存空间,用于存放指定数量的元素,避免频繁的内存重新分配。empty()
:判断vector是否为空,如果为空则返回true,否则返回false。
size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty() const{return _start == _finish;}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();// 1. 开辟新空间T* tmp = new T[n];// 2. 拷贝元素// 这里直接使用memcpy会有问题吗?同学们思考下//if (_start)//memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];// 3. 释放旧空间delete[] _start;}_start = tmp;_finish = _start + oldSize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){// 1.如果n小于当前的size,则数据个数缩小到nif (n <= size()){_finish = _start + n;return;}// 2.空间不够则增容if (n > capacity())reserve(n);// 3.将size扩大到niterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}
元素访问
下面是vector的元素访问相关接口:
operator[]
:通过索引访问vector中的元素。例如,vector_name[index]可以获取vector中索引为index的元素。at()
:通过索引访问vector中的元素,与operator[]类似,但会进行边界检查。如果索引超出范围,会抛出std::out_of_range异常。front()
:获取vector中第一个元素。back()
:获取vector中最后一个元素。data()
:返回指向vector内部存储数据的指针。可以使用该指针直接访问vector中的元素。size()
:返回vector中元素的个数。empty()
:检查vector是否为空,如果为空则返回true,否则返回false。clear()
:清空vector中的所有元素。push_back()
:在vector的末尾添加一个元素。pop_back()
:删除vector末尾的元素。
T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}T& front(){return *_start;}const T& front()const{return *_start;}T& back(){return *(_finish - 1);}const T& back()const{return *(_finish - 1);}
vector的修改操作
下面是vector的一些常用的修改操作相关接口:
push_back
:在vector的末尾插入一个元素。pop_back
:删除vector的最后一个元素。insert
:在指定位置插入一个或多个元素。erase
:删除指定位置的一个或多个元素。clear
:清空vector中的所有元素。resize
:改变vector的大小。swap
:交换两个vector的内容。assign
:用新元素替换vector中的内容。
void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vector<T>& 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 <= _finish);// 空间不够先进行增容if (_finish == _endOfStorage){//size_t size = size();size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容,需要重置pospos = _start + size();}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 返回删除数据的下一个数据// 方便解决:一边遍历一边删除的迭代器失效问题iterator erase(iterator pos){// 挪动数据进行删除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;}
源代码
#pragma once#include <iostream>using namespace std;#include <assert.h>namespace A{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;///// 构造和销毁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(size_t n, const T& value = T())之后* vector(int n, const T& value = T())就不需要提供了,但是对于:* vector<int> v(10, 5);* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型* 就不会走vector(size_t n, const T& value = T())这个构造方法,* 最终选择的是:vector(InputIterator first, InputIterator last)* 因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int* 但是10和5根本不是一个区间,编译时就报错了* 故需要增加该构造方法*/vector(int n, const T& value = T()): _start(new T[n]), _finish(_start + n), _endOfStorage(_finish){for (int i = 0; i < n; ++i){_start[i] = value;}}// 若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)只能是vector的迭代器// 重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.capacity());iterator it = begin();const_iterator vit = v.cbegin();while (vit != v.cend()){*it++ = *vit++;}_finish = it;}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}/// 迭代器相关iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin() const{return _start;}const_iterator cend() const{return _finish;}//// 容量相关size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty() const{return _start == _finish;}void reserve(size_t n){if (n > capacity()){size_t oldSize = size();// 1. 开辟新空间T* tmp = new T[n];// 2. 拷贝元素// 这里直接使用memcpy会有问题吗?同学们思考下//if (_start)//memcpy(tmp, _start, sizeof(T)*size);if (_start){for (size_t i = 0; i < oldSize; ++i)tmp[i] = _start[i];// 3. 释放旧空间delete[] _start;}_start = tmp;_finish = _start + oldSize;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){// 1.如果n小于当前的size,则数据个数缩小到nif (n <= size()){_finish = _start + n;return;}// 2.空间不够则增容if (n > capacity())reserve(n);// 3.将size扩大到niterator it = _finish;_finish = _start + n;while (it != _finish){*it = value;++it;}}///// 元素访问T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}T& front(){return *_start;}const T& front()const{return *_start;}T& back(){return *(_finish - 1);}const T& back()const{return *(_finish - 1);}/// vector的修改操作void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vector<T>& 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 <= _finish);// 空间不够先进行增容if (_finish == _endOfStorage){//size_t size = size();size_t newCapacity = (0 == capacity()) ? 1 : capacity() * 2;reserve(newCapacity);// 如果发生了增容,需要重置pospos = _start + size();}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}// 返回删除数据的下一个数据// 方便解决:一边遍历一边删除的迭代器失效问题iterator erase(iterator pos){// 挪动数据进行删除iterator begin = pos + 1;while (begin != _finish) {*(begin - 1) = *begin;++begin;}--_finish;return pos;}private:iterator _start;// 指向数据块的开始iterator _finish;// 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};}/// //// 对模拟实现的vector进行严格测试void TestBitVector1(){A::vector<int> v1;A::vector<int> v2(10, 5);int array[] = { 1,2,3,4,5 };A::vector<int> v3(array, array + sizeof(array) / sizeof(array[0]));A::vector<int> v4(v3);for (size_t i = 0; i < v2.size(); ++i){cout << v2[i] << " ";}cout << endl;auto it = v3.begin();while (it != v3.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v4){cout << e << " ";}cout << endl;}void TestBitVector2(){A::vector<int> 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;cout << v.front() << endl;cout << v.back() << endl;cout << v[0] << endl;for (auto e : v){cout << e << " ";}cout << endl;v.pop_back();v.pop_back();for (auto e : v){cout << e << " ";}cout << endl;v.insert(v.begin(), 0);for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin() + 1);for (auto e : v){cout << e << " ";}cout << endl;}