开发语言 c语言 数据结构 STL 探索C++中的动态数组：实现自己的Vector容器

个人名片：

作者简介：一名乐于分享在学习道路上收获的大二在校生 个人主页：GOTXX 个人WeChat：ILXOXVJE 本文由GOTXX原创，首发CSDN 系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路 每日一句：如果没有特别幸运，那就请特别努力！ ————————————————

文章简介：

本篇文章将 介绍如何使用C++编写代码来实现一个类似于STL中的Vector容器 等学习的相关知识进行分享！

如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加 油，一起奔跑，让我们顶峰相见！！！ ——————————————————————————

一.前言

这篇文章将介绍如何使用C++编写代码来实现一个类似于STL中的Vector容器。Vector是一种动态数组，它可以根据需要自动调整大小，并提供了许多方便的方法来操作数据。在这篇文章中，你将学习如何使用指针和动态内存分配来创建一个可变大小的数组，并实现Vector的常见功能，如添加元素、删除元素、访问元素等。通过实现自己的Vector容器，你将更好地理解动态数组的原理和实现方式，并提升对C++语言的理解和掌握。

二.Vs下Vector的底层结构

vs下底层是一个类，类里面的成员变量包括三个指针，指针类型为所存储数据类型（T）的指针； T* _start 指向的是存储数据所开空间的起始位置； T* _finish 指向的是最后一个数据的下一个位置； T* _endofstorage 指向的是所开空间的最后的下一个位置；

如图：

public:

typedef T* iterator;

typedef const T* const_iterator;

private:

iterator _start;

iterator _finish;

iterator _endofstorage;

三.vector的模拟实现

1.构造函数

1.直接初始化为空指针，使用时再开空间

vector()

:_start(nullptr)

,_finish(nullptr) //也可以在定义的时候直接给缺省值

,_endofstorage(nullptr)

{}

2.用一个迭代器区间构造（需要复用下面实现的push_back函数）

template //模板

vector(intputiterator first, intputiterator last)

{

while (first != last) //不能是用<判断，因为底层不一定连续

{

push_back(*first); //依次取里面的数据尾插

++first;

}

}

3.用n个T类型构造对象（这里需要后面实现的resize函数）

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

{

resize(n,x);

}

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

{

resize(n,x);

}

注意：这里为什么要实现两个？

2.reserve函数

结合下面代码和图解看看思路解析： 1.reserve函数可以单独使用，也可以在其他接口种会使用，我们实现的该函数不会缩容，所以最开始会加一个判断是否缩容； 2.reserve函数的实现是开一个新空间，将原空间的数据拷贝到新空间，再对_start,_finish,_endofstorage 进行处理； 3.这里需要记录一个原空间存储的有效数据的个数，为了确定_finish的位置（如果不存储，则当开辟好了新空间后，_finish的位置不能确定） 图解：

void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size(); //旧空间有效数据个数

size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //需要判断，因为可能为0

iterator tmp = new T[newcapacity]; //开空间

//memcpy(tmp, _start,old_size * sizeof(T)); //下面会将为什么不用memmove函数

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

{

tmp[i] = _start[i]; //拷贝数据

}

delete[] _start; //释放旧空间

_start = tmp;

_finish = _start + old_size; //确定_finish的位置

_endofstorage = _start + newcapacity;

}

}

为什么不用memmove？ 当我们存储的数据类型为string时【如图一】每个string对象里面都有一个_str，指向一个字符串，当我们用memmove拷贝后，拷贝后的_str与拷贝前的_str指向同一块空间【如图二】，当我们释放_start的时候，会调用string的析构函数，将该空间释放掉，就会导致野指针问题；

3.push_back函数

思路：检查是否空间满了，扩容，直接尾插

void push_back(const T& x)

{

if (_finish == _endofstorage) //检查是否需要扩容

{

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

}

*_finish = x; //尾插

++_finish; //更新下标

}

4.push_back函数

思路：与顺序表实现一样，直接–_finish;

void pop_back()

{

assert(size()); //检查是否还有有效数据可删

--_finish;

}

5.resize函数

思路： 分为三种可能: 1.n>capacity 扩容+尾插 2.size

值得注意的是传参给了缺省值，因为存储数据可能是string这种数据，给了缺省值会去掉对应的默认构造函数，虽然内置类型没有默认构造，但是为了解决这类问题，有了类似于默认构造类处理内置类型；

void resize(size_t n,T x=T() )

{

if (n

{

_finish = _start + n;;

}

else

{

if (n > capacity()) //扩容

{

reserve(n);

}

for (size_t i = size(); i <= n; i++) //尾插

{

_start[i] = x; //可以复用push_back函数

}

_finish = _start + n; //更新

}

}

6.insert函数

思路： 1.检查是否需要扩容 2.挪动数据 3.插入，更新下标

iterator insert(iterator pos, const T& x)

{

assert(pos);

assert(pos >= _start); //断言

assert(pos <= _finish);

if (_finish == _endofstorage)

{

size_t len = pos - _start; //记录之前的值

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

pos = _start + len; //更新pos下标

}

//memmove(pos+1, pos, sizeof(T) * (_finish - pos));

iterator end = _finish-1;

while (end>=pos)

{

*(end+1) = *end; //拷贝

end--;

}

*pos = x; //插入

++_finish;

return pos; //返回pos位置的迭代器，防止迭代器失效问题

}

7.erase函数

直接挪动数据覆盖

iterator erase(iterator pos)

{

assert(pos < _finish && pos >= _start); //断言

iterator end = pos;

while (end < _finish)

{

*end = *(end + 1); //挪动数据覆盖

end++;

}

--_finish; //更新下标

return pos; //返回pos位置的迭代器，防止迭代器失效问题

}

8.swap函数

void swap(vector& v)

{

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

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

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

}

9.赋值运算符重载

与上章《魔法之线：探索string类的神秘世界》链接: link赋值运算符重载方法一样；

现代写法：

vector& operator=(vector v)

{

swap(v);

return *this;

}

10.拷贝构造函数

传统写法：

vector(const vector& v)

{

iterator tmp = new T[v.capacity()];

memcpy(tmp, v._start, sizeof(T) * v.size());

_start = tmp;

_finish = _start + v.size();

_endofstorage = _start + v.capacity();

}

稍便捷的方式 直接复用尾插函数，将对象v的数据一个一个尾插；

vector(vector& v)

:_start(nullptr)

,_finish(nullptr)

,_endofstorage(nullptr)

{

reserve(v.capacity()); //提前空间，减少尾插扩容

for (const auto& e : v)

{

push_back(e);

}

}

11.其他简单函数的实现：

//判空

bool empty()

{

return size();

}

//返回第一个数据

T& front()const

{

return *_start;

}

//返回最后一个数据

T& back()const

{

return *(_finish-1);

}

//返回有效数据个数

size_t size()const

{

return _finish - _start;

}

//返回容量

size_t capacity()const

{

return _endofstorage - _start;

}

//[]运算符重载

T& operator[](size_t pos)

{

assert(pos>=0 && pos

return _start[pos];

}

T& operator[](size_t pos)const

{

assert(pos >= 0 && pos < size());

return _start[pos];

}

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;

}

四.迭代器失效例题：

例题1：

假设cont是一个Container 的示例，里面包含数个元素，那么当CONTAINER为：1.vector 2.list 3.deque 会导致下面的代码片段崩溃的Container 类型是（ ）

int main()

{

Container cont = { 1, 2, 3, 4, 5};

Container::iterator iter, tempIt;

for (iter = cont.begin(); iter != cont.end();)

{

tempIt = iter;

++iter;

cont.erase(tempIt);

}

}

解析： 分析：此题主要考察cont.erase(tmpit)删除数据之后，迭代器失效相关问题

本题重点要关注的是底层实现

vector、deque底层都是用了连续空间，所以虽然++iter迭代器了，但是erase(tempit)以后

底层是连续空间，删除会挪动数据，最终导致iter意义变了，已失效了。

而list，不是连续空间，删除以后tempIt虽然失效了，但是不影响iter。

例题2：

对于list有迭代器it, 当erase(it)后，说法错误的是( )

A.当前迭代器it失效 B.it前面的迭代器仍然有效 C.it后面的迭代器失效 D.it后面的迭代器仍然有效

解析：

分析：删除节点后，只有指向当前节点的迭代器失效了，其前后的迭代器仍然有效，因为底层为不连续空间，只有被删除的 节点才会失效， 所以答案为 C

例题3：

下面程序的输出结果正确的是( )

int main()

{

int ar[] ={1,2,3,4,0,5,6,7,8,9};

int n = sizeof(ar) / sizeof(int);

vector v(ar, ar+n);

vector::iterator it = v.begin();

while(it != v.end())

{

if(*it != 0)

cout<<*it;

else

v.erase(it);

it++;

}

return 0;

}

解析： 分析:当迭代器的值为0时，此时会进行删除，删除后如果迭代器不重新赋值，会导致原来的迭代器失效，此时针对一个已经失效的迭代器在进行++,会导致程序崩溃

例题4：

下面关于迭代器失效的描述哪个是错误的（ ）

A.vector的插入操作一定会导致迭代器失效 B.vector的插入操作有可能不会导致迭代器失效 C.vector的删除操作只会导致指向被删除元素及后面的迭代器失效 D.vector的删除操作只会导致指向被删除元素的迭代器失效

解析： A.vector的插入操作如果导致底层空间重新开辟，则迭代器就会失效。如果空间足够，不扩容时，迭代器不一定失效，比如push_back尾插，元素插入到空间末尾，在不扩容时不会对迭代器产生影响 B.参考A的解释。 C.vector删除，当前元素肯定失效，后面元素会牵扯到移动数据，因此删除元素后面的迭代器也会失效 D. vector的删除操作不光会导致指向被删除元素的迭代器失效，删除元素后面的迭代器也会失效

例题5：

T是一个数据类型，在vs系列编译器中，debug模式下，关于std::vector::at 和 std::vector::operator[ ] 描述正确的是( ) A.at总是做边界检查， operator[] 不做边界检查. B.at 不做边界检查， operator[] 做边界检查. C.at和operator[] 都是会做边界检查的 D.以上都不对

解析：

注意题目专门强调了vs系列编译器，debug模式下at() 和 operator[] 都是根据下标获取任意位置元素的，在debug模式下两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 内部的assert会触发，故选择C。

最后希望内容对大家有所帮助

好文推荐

 您阅读本篇文章共花了：