目录
- 前言
- 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;
}
