C++语法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
命名空间	缺省参数与函数重载	C++相关特性	类和对象-上篇	类和对象-中篇
类和对象-下篇	日期类	C/C++内存管理	模板初阶	String使用
String模拟实现

在string类文章中提及了STL容器间的接口是大差不差的，本篇将直接通过模拟实现Vector来讲解底层实现与使用。

🌈个人主页：是店小二呀

🌈C语言笔记专栏：C语言笔记

🌈C++笔记专栏： C++笔记

🌈初阶数据结构笔记专栏： 初阶数据结构笔记

🌈Linux笔记专栏： Linux笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

文章目录

前文:vector介绍一、模拟实现Vector准备工作1.1 vector的成员对象1.2 原生指针模拟迭代器

二、正式模拟实现Vector2.1 构造函数2.1.1 无参构造2.1.2 vector迭代区间构造2.1.3 初始化构造

2.2 拷贝构造2.3 初始化列表2.4 析构函数2.5 operator[] 下标访问2.6 swap 交换函数2.7 operator= 赋值运算符重载2.8 得到当前元素空间信息2.8.1 size(有效元素个数)2.8.2 capacity(当前空间容量)

2.9 reserve2.9.1 第一版本:野指针问题2.9.2 第二版本：浅拷贝问题

2.10 resize(重点常用)2.10.1 const T& val = T()解释

2.11 单或多参数构造支持隐式类型转化2.12 insert 2.12.1 insert使用

2.13 扩容前迭代器失效2.14 erase2.14.1 erase使用2.14.2 验证迭代器失效2.14.3缩容导致迭代器失效

2.15 push_back2.16 pop_back2.17 pop_back2.18 empty 判断空2.19 print_vector 打印数据

三、vector.h

前文:vector介绍

vector的文档介绍

vector是表示可变大小数组的序列容器，底层是动态开辟顺序表vector插入新数据发生扩容，其做法是，分配一个新的数组，然后将全部元素移动到这个数组(单论时间，需要付出相对代价很高).每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小(不清楚这块空间剩余多少内存)vector分配空间策略:vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大，不同的库采用不同的策略权衡空间的使用和重新分配。重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更

一、模拟实现Vector准备工作

在模拟实现vector过程中，为了避免跟库中vector发生冲突，需要创建个命名空间，在命名空间中实现vector。需要选择现实vector类模板去用于不同的类型(内置类型、自定义类型)

<code>namespace vec

{ -- -->

template<class T>

class vector

{

};

}

1.1 vector的成员对象

适用于不同类型的操作，可以通过模板参数列表的类型指针，去对不同类型进行访问和修改。

template<class T>

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

成员说明:

typedef T* iteratror:采用原生指针去模拟迭代器(不是真正的迭代器)_start：指向空间的第一个位置_finish：指向最后有效数据的位置_end_of _storage：指向空间的最后一个位置

1.2 原生指针模拟迭代器

<code>template<class T>

class 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;

}

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

二、正式模拟实现Vector

2.1 构造函数

具体说明：allocator_type是内存配置器（内存池）和explicit这个阶段都不用去理会它。最经常使用是接口(1)和(4)，其中(1)就当作是无参的构造，不用传什么值，就使用它的缺省值()

value_type()是模板参数列表实例化转化的T类型

2.1.1 无参构造

<code> vector()

{ -- -->}

这里就算不显式写无参构造，编译器也会自动生成。从某种意义上无参构造不用写，但是我们需要实现拷贝构造，编译器就不会默认生成无参构造函数了。总之要显式写无参构造函数。

2.1.2 vector迭代区间构造

类模板的成员函数可以是函数模板

template<class InputIterator>

vector(InputIterator fist, InputIterator last)

{

while (fist != last)

{

push_back(*fist);

++fist;

}

}

使用场景：

vector<int> v2(v1.begin()+1, v1.end()-1);

print_vector(v2);

string str("abcd");

vector<int> v3(str.begin(), str.end());

print_vector(v3);

具体说明：在使用该接口时，需要注意不可以(--v1.begin(), --v1.end()使用。这里begin()和end()函数是传值返回，返回临时对象具有常性，不能通过++或–修改临时对象

2.1.3 初始化构造

vector(size_t n, const T* val = T())

{

reserve(n);

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

这段初始化构造逻辑是没有问题的，但是在调用过程可能会出现问题

首先给出三组数据，去使用初始化构造函数

vector<int> v1(10, 1);

print_vector(v1);

vector<int> v2(10u, 1);

print_vector(v2);

vector<int> v3(10, 'a');

print_vector(v3);

具体说明：在调用过程中会报出<code>非法的间接寻址错误，原因在于第一个实例化(就这个比较特别)，调用的是函数模板，这里*first就会报错，想走捷径，发现掉坑里面。

vector<int> v1(10, 1)参数部分都是整型类型，如果使用下面的初始化构造，需要int转化为size_t（发生隐式类型转化）。对于模板初始化函数而言，自动推导类型，对此上面更加匹配(那就报错哦)vector<int> v2(10u, 1)参数部分都是无符号整数，有现成吃现成，就是调用第二个vector<int> v3(10, 'a')参数部分是不同类型，自然调不动第一个函数，调用第二个函数，进行类型转化

解决措施：实现函数重载，特殊情况特殊处理

vector(size_t n, const T* val = T())

{ -- -->

reserve(n);

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

vector(int n, const T& val = T())

{

reserve(n);

for (int i = 0; i < n; i++)

{

push_back(val);

}

}

2.2 拷贝构造

vector(const vector<T>& v)

{

//需要开一样大的空间

reserve(v.capacity());

for (auto& e : v)

{

push_back(e);

}

}

具体说明:这里可以采用string类拷贝构造方式，但是这个更加简洁。auto自动识别类型建议加&，如果T是自定义类型，就需要调用多次拷贝构造(深拷贝)

2.3 初始化列表

auto x = { 1,2,3,4,5,6 };

cout << typeid(x).name() << endl;

cout << sizeof(x) << endl;

输出结果:

class std::initializer_list<int>

当我们想实现像数组nums[5] = {12,3,4,5}这样初始化，库提供初始化列表initializer_list的方式满足了我们的需求。

其中vector类也包含了这种方式

initializer_list y = {1,2,3,4,5};vector x = {1,2,3,4,5};

通过类模板在vector类中实现该功能

vector(initializer_list<T> il)

{

reserve(il.size());

for (auto& e : il)

{

push_back(e);

}

}

2.4 析构函数

~vector()

{

delete[]_start;

_start = nullptr;

_finish = _end_of_storage = nullptr;

}

2.5 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];

}

具体说明：

下标加方括号仅限于物理逻辑连续的容器，比如:string、vector、list之类。针对对象是否被const修饰，需要重载两个函数(可读可写，可读不可写)。使用引用返回，可以修改到实参和提高效率

2.6 swap 交换函数

void swap(vector<T>& v)

{

std::swap(_start, v._start);

std::swap(_start, v._start);

std::swap(_start, v._start);

}

2.7 operator= 赋值运算符重载

//v2 = v1;

vector<T>& operator=(vector<T> v)

{

swap(v);

return *this;

}

说明：跟string是同一套流程，这里就直接选用优化现代写法版本

2.8 得到当前元素空间信息

2.8.1 size(有效元素个数)

size_t size() const

{

//指针 - 指针

return _finish - _start;

}

2.8.2 capacity(当前空间容量)

size_t capacity()const

{

return _end_of_storage - _start;

}

说明:

size是有效元素的个数，capacity是当前空间的容量都是通过指针-指针得到的大小

2.9 reserve

2.9.1 第一版本:野指针问题

void reserve(size_t n)

{

if (n > capacity())

{

T* tmp = new T[n];

memcpy(tmp, _start, size(T) * n);

delete[] _start;

_start = tmp;

_finish = tmp + size();

_end_of_storage = tmp + n;

}

}

不足之处:迭代器失效的问题，出现野指针_finish指向错误。在delete[] _start的时候，finish还在指向旧空间，导致调用size()得到数据错误。

解决办法:在销毁旧空间之前，提前保留size()的大小

<code>void reserve(size_t n)

{ -- -->

if (n > capacity)

{

T& tmp = new T[n];

size_t size = size();

memcpy(tmp, _statr, sizeof(T) * n);

delete[] _start;

_start = tmp;

_finish = tmp + size;

_end_of_storage = tmp + n;

}

}

2.9.2 第二版本：浅拷贝问题

问题说明:这里memcpy是逐字节拷贝，属于浅拷贝。当T为自定义类型，使用memcpy进行浅拷贝操作，会指向同一块空间。

_str指向的空间没有拷贝，导致指向同一块空间，调用析构函数会造成野指针问题。

解决办法:

<code>void reserve(size_t n)

{ -- -->

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

//memcpy(tmp, _start, size(T) * n);

for (size_t i = 0; i < old_size; i++)

{

//自定义类型会赋值运算符重载

tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = tmp +n ;

}

}

这属于一种更加暴力的解法，直接将_start里面的数据拷贝过来

2.10 resize(重点常用)

//重点实现resize

void resize(size_t n, const T& val = T())

{

//缩容

if (n <= size())

{

//类似截断

_finish = _start + n;

}

else

{

//提前扩容

//大于capacity才起作用

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

_finish++;

}

}

}

具体说明:虽然没有reserve这么多坑，但是有几个知识点值得我们注意。

2.10.1 const T& val = T()解释

对于T可能是内置类型或自定义类型，对于自定义类型不能通过简单常量作为缺省值，所以选择了T()调用构造函数作为缺省值最合适。对于内置类型不是说没有构造函数这一说法吗？好的，内置类型被迫升级下。内置类型也有了自己的构造函数和析构函数(平常一般不使用)，int就是0（char也是整型 ASCII码）、double就是0.0、指针就是空指针。因为缺省值怎么给都不合理，只能用自身的构造(匿名对象实例化)

2.11 单或多参数构造支持隐式类型转化

string str="1111";//构造+拷贝构造-->优化 直接构造code>

const string& str1="1111";//构造临时对象，引用的是临时对象code>

vector<string>v;

v.push_back(str);

v.push_back(string("2222"));

v.push_back("33333");

隐式类型+优化的情况:

<code>vector<int> v1={ -- -->1,2,3,4,5};

vector<int> v2({ 1,2,3,4,5}) //直接构造

2.12 insert

2.12.1 insert使用

<code> void insert(iterator pos, const T& val)

{ -- -->

assert(_start <= pos);

assert(pos <= _finish);

//考虑是否需要扩容

//说明空间已经满了

if (_finish == _end_of_storage)

{

reserve(capacity() == 0 ? 4 : capacity() * 2);

}

//开始移动数据

iterator it = _finish - 1;

while (it >= pos)

{

*(it + 1) = *it;

it--;

}

*pos = val;

_finish++;

}

具体说明：使用迭代器去模拟实现insert比起string模拟实现，在 while (it >= pos)没有pos为0的坑。涉及到开辟或销毁空间时，都有可能涉及到迭代器失效，对此都需要考虑到位。

2.13 扩容前迭代器失效

void test_vector()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

v1.push_back(6);

v1.push_back(7);

v1.push_back(8);

print_vector(v1);

vector<int>::iterator it = v1.begin() + 3;

v1.insert(it, 40);

print_vector(v1);

cout << *it << endl;

}

问题:在进行insert操作后，迭代器it就会失效。

思考:在扩容接口中，不是解决迭代器失效的问题了吗？

具体说明：

在调用insert接口是it传参pos位置，而形参是实参的一份临时拷贝，那么需要传引用解决。一波未平一波又起，如果传引用<code>v2.insert(v2.begin(),11.11)，这里v2.begin()返回的是临时变量，不能通过引用来接收。

没有给出解决办法，调用insert接口出现扩容操作，迭代器会失效，不要去使用

2.14 erase

2.14.1 erase使用

//迭代器实现erase

iterator erase(iterator pos)

{ -- -->

assert(_start <= pos);

//删除不到_finish这个位置

assert(pos < _finish);

iterator it = pos+1;

//it=pos+1=_finish就是最后一个位置

while (it <= _finish)

{

*(it - 1) = *(it);

it++;

}

_finish--;

return pos;

}

2.14.2 验证迭代器失效

接下来我将给出三个场景:都是关于删除偶数

第一个场景:没啥问题

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

vector<int>::iterator it = v1.begin();

while (it != v1.end())

{

if (*it % 2 == 0)

{

v1.erase(it);

}

++it;

}

第二个场景:少删除

<code>vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(4);

v1.push_back(5);

vector<int>::iterator it = v1.begin();

while (it != v1.end())

{ -- -->

if (*it % 2 == 0)

{

v1.erase(it);

}

++it;

}

第三个场景:迭代器失效

<code>vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

v1.push_back(4);

关于上面出现的问题分析:

在erase的逻辑是通移动数据覆盖不需要的数据，达到删除的效果。逻辑上会跳过一个值，移动++可能会导致错过了一些值。如果it++操作跳过end()，it就会一路向北，错过了判断条件

解决措施:

<code>vector<int>::iterator it = v1.begin();

while (it != v1.end())

{ -- -->

if (*it % 2 == 0)

{

v1.erase(it);

}

else

{

it++;

}

}

print_vector(v1);

2.14.3缩容导致迭代器失效

上面解决措施在Linux下还可以，但是在Vs下就不行了。由于因为Vs下的iterator没有使用原生指针实现，是自定义类型的迭代器，内部会进行强制类型检查。

对于erase不同编译器迭代器是不同的，erase也可能会缩容。erase迭代器的解决方案有两个：迭代器失效以后不要直接使用，如果要使用按照规则重新更新后使用。

<code>vector<int>::iterator it = v1.begin();

while (it != v1.end())

{ -- -->

if (*it % 2 == 0)

{

it=v1.erase(it);

}

else

{

it++;

}

}

这样子就可以适应不同的版本，缩容以后。迭代器还是但会删除原生的下一个迭代器。

2.15 push_back

void push_back(const T& val )

{

insert(end(), val);

}

2.16 pop_back

void pop_back()

{

/*assert(!empty());

--_finish;*/

erase(end()-1);

}

2.17 pop_back

void pop_back()

{

/*assert(!empty());

--_finish;*/

erase(end()-1);

}

2.18 empty 判断空

bool empty()

{

return _start == _finish;

}

2.19 print_vector 打印数据

为了实现适用于不同类型的打印，这里需要涉及一个函数模板

void print_vector(const vector<T>& v)

{

//下标加[]

for (size_t i = 0; i < v.size(); i++)

{

cout << v[i] << " ";

}

cout << endl;

//迭代器

vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

//范围for

for (auto e : v)

{

cout << e << " ";

}

cout << endl;、

}

不足之处：在三种遍历方式，使用迭代器遍历会出现报错。

问题在于: vector<T>,这里类模板没有实例化，对于内嵌类型，那么不敢进去取，里面的东西也有没有实例化。编译器无法识别const_iterator是静态变量还是内中类,选择报错。

vector类模板没有完成实例化，对于内嵌类型const_iterator不敢进去取，对于内部是否实例。编译器无法编译器无法识别const_iterator是静态变量还是内中类。编译器选择报错。

解决措施:编译器规定typename告诉后面后面是一个类型，不是静态成员变量(先通过编译，之后再给你实例化)。在编译阶段才知道类型，如果需要一个类型接收，可以使用auto自动识别类型。

typename vector<T>::const_iterator it = v.begin();

auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

三、vector.h

#pragma once

#include <assert.h>

#include <iostream>

#include <algorithm>

using namespace std;

namespace bit

{

template<class T>

class 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()

{ }

//有参构造

//.....

//析构

~vector()

{

delete[]_start;

_start = nullptr;

_finish = _end_of_storage = nullptr;

}

//vector<int> v1={1,2,3,4,5,6};

vector(initializer_list<T> il)

{

reserve(il.size());

for (auto& e : il)

{

push_back(e);

}

}

//拷贝构造

//v2(v1)

vector(const vector<T>& v)

{

//需要开一样大的空间

reserve(v.capacity());

for (auto& e : v)

{

push_back(e);

}

}

//v2 = v1;

vector<T>& operator=(vector<T> v)

{

swap(v);

return *this;

}

//通过下标访问

//并且不知道会返回什么具体的类型

T& operator[](size_t pos)

{

//不能等于size()，指向\0

assert(pos < size());

return _start[pos];

}

const T& operator[](size_t pos) const

{

assert(pos < size());

return _start[pos];

}

//交换

void swap(vector<T>& v)

{

std::swap(_start, v._start);

std::swap(_start, v._start);

std::swap(_start, v._start);

}

//得到当前元素空间信息

//指针-指针

size_t size()const

{

return _finish - _start;

}

size_t capacity()const

{

return _end_of_storage - _start;

}

//扩容

//第一个问题，迭代器失效

//void reserve(size_t n)

//{

//if (n > capacity())

//{

//T* tmp = new T[n];

//memcpy(tmp, _start, size(T) * n);

//delete[] _start;

//_start = tmp;

//_finish = tmpt + size();

//_end_of_storage = tmp + n;

//}

//}

改良

第二个问题，当T为自定义类型，就是浅拷贝，但是还是指向同一块空间

//void reserve(size_t n)

//{

//if (n > capacity())

//{

//size_t old_size = size();

//T* tmp = new T[n];

//memcpy(tmp, _start, size(T) * n);

//delete[] _start;

//_start = tmp;

//_finish = tmp + old_size;

//_end_of_storage = tmp + n;

//}

//}

正确写法

void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

//memcpy(tmp, _start, size(T) * n);

for (size_t i = 0; i < old_size; i++)

{

tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = tmp +n ;

}

}

//vector的迭代区间

//函数模板

template<class InputIterator>

vector(InputIterator fist, InputIterator last)

{

while (fist != last)

{

push_back(*fist);

++fist;

}

}

//初始化 构造

vector(size_t n, const T& val = T())

{

reserve(n);

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

vector(int n, const T& val = T())

{

reserve(n);

for (int i = 0; i < n; i++)

{

push_back(val);

}

}

//重点实现resize

void resize(size_t n, const T& val = T())

{

//缩容

if (n <= size())

{

_finish = _start + n;

}

else

{

//提前扩容

//大于capacity才起作用

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

_finish++;

}

}

}

//核心操作

void push_back(const T& val )

{

insert(end(), val);

}

void pop_back()

{

/*assert(!empty());

_finish--;*/

//不能--

erase(end() - 1);

}

//判断空

bool empty()

{

return _start == _finish;

}

//实现插入操作时，可能会涉及到扩容操作，就有可能出现迭代器失效的可能

void insert(iterator pos, const T& val )

{

assert(_start <= pos);

assert(pos <= _finish);

//考虑是否需要扩容

//说明空间已经满了

if (_finish == _end_of_storage)

{

size_t len = pos - _start;

//这里迭代器失效的问题

//不是解决了吗！当时pos没有解决呀！

reserve(capacity() == 0 ? 4 : capacity() * 2);

pos = _start + len;

}

//开始移动数据

iterator it = _finish - 1;

while (it >= pos)

{

*(it + 1) = *it;

it--;

}

*pos = val;

_finish++;

}

//迭代器实现erase

iterator erase(iterator pos)

{

assert(_start <= pos);

//删除不到_finish这个位置

assert(pos < _finish);

iterator it = pos+1;

//it=pos+1=_finish就是最后一个位置

while (it <= _finish)

{

*(it - 1) = *(it);

it++;

}

_finish--;

return pos;

}

private:

iterator _start=nullptr;

iterator _finish=nullptr;

iterator _end_of_storage=nullptr;

};

// 函数模板

template<class T>

void print_vector(const vector<T>& v)

{

//for (size_t i = 0; i < v.size(); i++)

//{

//cout << v[i] << " ";

//}

//cout << endl;

//typename vector<T>::const_iterator it = v.begin();

auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

/*for (auto e : v)

{

cout << e << " ";

}

cout << endl;*/

}

void test1()

{

vector<int> v;

v.push_back(12);

v.pop_back();

v.push_back(1);

print_vector(v);

}

void test_vector2()

{

vector<int> v1(10, 1);

print_vector(v1);

vector<int> v2(10u, 1);

print_vector(v2);

vector<int> v3(10, 'a');

print_vector(v3);

}

void test_vector3()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

v1.push_back(6);

v1.push_back(7);

v1.push_back(8);

print_vector(v1);

vector<int>::iterator it = v1.begin() + 3;

v1.insert(it, 40);

print_vector(v1);

cout << *it << endl;

}

void test_vector4()

{

auto x = { 1,2,3,4,5,6 };

cout << typeid(x).name() << endl;

cout << sizeof(x) << endl;

}

void test_vector5()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

v1.push_back(4);

//std::vector<int>::iterator it = v1.begin();

vector<int>::iterator it = v1.begin();

while (it != v1.end())

{

if (*it % 2 == 0)

{

it=v1.erase(it);

}

else

{

it++;

}

}

print_vector(v1);

}

}

---

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！