【C++】容器篇（一）—— vector 的基本概述以及模拟实现网站首页 技术杂谈

【C++】容器篇（一）—— vector 的基本概述以及模拟实现

起飞的风筝 2024-06-17 11:19:22

简介【C++】容器篇（一）—— vector 的基本概述以及模拟实现

前言：

在之前，我们已经对 string类进行了基本的概述，并且手动的实现了string类中常用的接口函数。本期，我将带领大家学习的是STL库中的一个容器 -- vector 的学习。相比于之前的string类，本期的 vector 相对来说实现起来略微难一点，难点就在于要考虑关于 “迭代器失效”方面和“深浅拷贝”的问题。

文章目录

2、vector iterator 的使用

前言

在正式的学习之前，我们先来看看STL库中的容器有哪些，让大家先混个脸熟，在接下来，对于其他的容器我也会给大家进行相关的讲解。

STL库中的容器如下（勾画的接下来我都会给大家讲解）：

? 而对于 map、set等则是要等到之后在给大家讲解，因为要涉及关于红黑树的相关知识；

? 而对于像第一个【arry】这个我们十分的熟悉了，就没有必要在进行讲解了，而【deque】和【queue】二者之间也有很多的不同之处；

? 而对于【bitset】（位集），我们只需简单的了解即可，它主要的功能是提供一些成员函数，使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。

（一）基本介绍

1、相关定义

既然要学习vector，那么首先就需要知道到底什么是vector，定义如下：

vector是STL库中的一种序列式容器，事实上和数组差不多（但它比数组更优越），由于其大小(size)可变，常用于数组大小不可知的情况下来替代数组。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。

2、vector的引入

一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界；
而 vector 正好弥补了这个缺陷，它不像数组那样，它的大小是可以动态改变的，相当于可拓展的数组（动态数组），它的随机访问快，在中间插入和删除慢，但在末端插入和删除快，而且它的大小会被容器自动处理。

3、vector的优点

与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效；
对于其它不在末尾的删除和插入操作，效率更低；
比起list 和 forward_list 统一的迭代器和引用更好。

4、vector使用本质

本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。

其做法是：分配一个新的数组，然后将全部元素移到这个数组。

就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

（二）vector的使用

vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

1、vector的定义

2、vector iterator 的使用

3、vector的空间增长

4、vector的增删查改

大家通过文档不难发现，vector容器跟之前学习的string类的接口很相似。因此，通过之前对string的学习，并且掌握的话对于本次学习的vector学习到掌握是很容易的！！！

（三）接口函数的介绍

接下来，我就将为大家介绍常用的接口以及实现的过程！！！

1、Member functions

对于构造，我们通过阅读文档可以发现，文档给出的构造有四种，分别是：

默认构造
n个val构造
迭代区间构造
拷贝构造

接下来，我直接给大家展示相关方法是如何进行函数构造的。

1️⃣n个val构造

代码如下：

void test1()
{
	//n个val构造
	vector<int>arr(10,1); //ten ints with value 1

	for (int i = 0; i < arr.size(); ++i)
	{
		cout << arr[i] << " ";
	}
	cout << endl;

}

int main()
{
	test1();
	return 0;
}

解释说明：

上述代码我们构造包含 10个元素的容器。每个元素都是 1 的副本。

2️⃣迭代区间构造

代码如下：

void test()
{
    vector<int>arr(10,1);

	//迭代区间构造
	vector<int>tmp(arr.begin(), arr.end());
	for (int i = 0; i < tmp.size(); ++i)
	{
		cout << tmp[i] << " ";
	}
	cout << endl;

}

int main()
{
	test();
	return 0;
}

解释说明：

上述通过构造一个容器，其中包含与范围 [first、last）（特别注意迭代区间的范围是左闭右开）一样多的元素，每个元素都以相同的顺序从该区域中的相应元素构造。

拓展说明：

对于迭代器构造，不知道大家有没有发现文档中给出的描述：

迭代器不应该叫做【iterator】吗，这里怎么叫做【inputiterator】呢？

这就要说到一个问题了，那就是迭代器是分类型的（说起来很复杂，我简单讲一下）。
不同的迭代器除了之前说过的正向、反向这样的使用属性之外，还有相关的特性属性，比如双向、单向等；
因此在这里就表示你使用时即可传单向，也可以传双向，以及随机等（即可以传任意类型）

例如以下：

    string str("have a good day");
	vector<int>vv(str.begin(), str.end());
	for (int i = 0; i < vv.size(); ++i)
	{
		cout << vv[i] << " ";
	}
	cout << endl;

输出的即是对应的 ASCll 码值。除此之外，还可以进行【++】或【--】操作。

3️⃣拷贝构造

代码如下：

void test()
{
	vector<int>arr;  //默认构造
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);


	//拷贝构造
	vector<int> tmp(arr);
	for (auto e : tmp)
	{
		cout << e << " ";
	}
	cout << endl;
}

解释说明：

复制构造函数，以相同的顺序构造一个容器，其中包含 arr 中每个元素的副本。

2、Iterators

接下来就是关于正向迭代器和反向迭代器的介绍，这个我相信大家在之前的学习中都有了解，我就不过多阐述。

1️⃣begin()和end()

代码如下：

void test()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);


	vector<int>::iterator it = arr.begin();
	while (it != arr.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

2️⃣rbegin()和rend()

代码如下：

void test()
{
	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(4);
	arr.push_back(5);

	vector<int>::reverse_iterator rit = arr.rbegin();
	//auto rit = arr.rbegin();

	while (rit != arr.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

3、Capacity

对于容量的相关接口，跟之前学的string是类似的。

这里需要讲明的一点是关于【capacity】扩容的问题，capacity的代码在 vs 和 g++ 下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

用以下测试代码分别在两种环境下运行后：

// 测试vector的默认扩容机制
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:
";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '
';
		}
	}
}

在vs下的结果：

在g++下的结果：

接下来，对于reserve 和 resize，我们在后面的接口函数模拟实现上具体的讲解，以及带大家来理解迭代器失效的问题！！

（四）vector模拟实现

1、成员变量

我这里的实现风格整体来说是按照库里面的实现方式来进行操作的（如果大家有兴趣，可以去库里面看下源码）

首先，我们这里实现的vector是 typedef出来的，具体如下（分为普通版本和const版本）：

typedef T* iterator;
typedef const T* const_iterator;

而对于类的成员变量如下：

private:
		iterator _start;
		iterator _end;
		iterator _end_of_storage;

解释说明：

⚔️ _start：表示指向数据的开始位置；

⚔️ _end：表示指向数据的结尾位置的下一个位置；

⚔️ _end_of_storage：表示的是整个空间的大小。

2、成员函数

1️⃣构造函数

这些都跟之前是一样的，在这里就不多说了，具体如下：

        vector()
			: _start(nullptr)
			, _end(nullptr)
			, _end_of_storage(nullptr)
		{}

2️⃣析构函数


		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_end = _end_of_storage = _start = nullptr;
			}
		}

3️⃣拷贝构造

现代写法：

        //现代写法
		vector(const vector<T>& arr)
		{
			vector<int> tmp(arr.begin().arr.end());
			swap(tmp);
		}

传统写法：

        vector(const vector<T>& arr)
		{
			_start = new T[arr.capacity()];
			for (size_t i = 0; i < arr.size(); ++i)
			{
				_start[i] = arr._start[i];
			}

			_end = _start + arr.size();
			_end_of_storage = _start + arr.capacity();
		}

3、迭代器

1️⃣begin() 和 end()

这里我提供了两个版本的，分别是普通版本和const版本的实现。

具体如下：

        iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _end;
		}

		const_iterator begin()const
		{
			return _start;
		}

		const_iterator end()const
		{
			return _end;
		}

对于反向迭代器，我放在之后的学习中再去讲解，因为将会涉及一些其他的东西在里面。

4、容量

1️⃣size()

理解：这应该很容易理解，对于有效位数据位的大小，就为【_end】位置与【_start】位置的距离为多少。

具体如下：

        //长度大小
		size_t size()const
		{
			return _end - _start;
		}

2️⃣capacity()

理解：对于数据所占空间的大小，就为首元素位置与整体空间大小的差值。

具体如下：

        //空间大小
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}

3️⃣empty()

具体如下：

        bool empty()
		{
			return _start ==  _end;
		}

4️⃣reserve()

特点：reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

代码展示：

void reserve(size_t n)
		{
			//首先先判断是否需要开辟新空间
			if (n > capacity())
			{
				//开新空间
				T* tmp = new T[n];
				if (_start)
				{
					//元素拷贝到新空间
					memcpy(tmp, _start, sizeof(T)*size());
					//释放旧空间
					delete[] _start;
				}


				_start = tmp;
				_end = tmp + size();
				_end_of_storage = tmp + n;
			}
		}

上述模拟实现的vector中的reserve接口中，会使用 memcpy 进行的拷贝，但是大家通过代码有没有发现什么问题呢？

当我们用测试用例去打印结果的时候，会发生程序挂掉了：

我们通过调试去观察是什么原因导致的问题，具体如下：

现象解释：

首先，我们知道size() = _end - _start;
按理说释放之后应该为0，因为 tmp=_start，因此我们可以把上述带入公式带入代码中换掉，我们就不难得出一点，此时代码就为【tmp + _end - _start(tmp) 】，所以此时最终为0了；
相当于_start 是一个地址，而最终却是 0 减一个地址。即_end 还是之前的，而_start 却不是之前的_start 了；
因此，最好的解决办法就是在事先保留一份最初的 size() 即可。

代码如下：

        void reserve(size_t n)
		{
			//首先先判断是否需要开辟新空间
			if (n > capacity())
			{
				size_t num = size();
				//开新空间
				T* tmp = new T[n];
				if (_start)
				{
					//元素拷贝到新空间
					memcpy(tmp, _start, sizeof(T)*size());
					//释放旧空间
					delete[] _start;
				}

				_start = tmp;
				_end = _start + num;
				_end_of_storage = _start + n;

			}
		}

最终通过上诉我们得出一点：

如果拷贝的是自定义类型的元素，memcpy既高效又不会出错；
但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

5️⃣resize()

resize在开空间的同时还会进行初始化，影响size。

代码展示：

        void resize(size_t n, const T& val = T())
		{
			if (n < size())
			{
				_end = _start + n;
			}
			else
			{
				if(n > capacity())
					reserve(n);

				while (_end != _start + n)
				{
					_end = val;
					++_end;
				}
			}
		}

注意这里的val初始化时初始化为 T()；
当单独使用T()时，当前行结束就会自动调用销毁，而当时用 const T& val =T() 就可以延长生命周期。

5、元素访问

1️⃣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];
		}

6、修改

1️⃣push_back()


		//尾插
		void push_back(const T& X)
		{
			//先判断空间
			if (_end == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			//移动元素
			*_end = X;
			++_end;
		}

2️⃣pop_back()

        void pop_back()
		{
			assert(!empty()); //注意判空
			 --_end;
		}

3️⃣insert()

意思很简单，即在 pos 位置出插入 val 元素即可。但是这里却有一个很坑的点，那就是不小心写出来的代码就会引起迭代器失效的问题。

大家先看以下代码：

        void insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _end);

			if (_end == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			iterator finish = _end - 1;
			while (finish >= pos)
			{
				*(finish + 1) = *finish;
				--finish;
			}

			*pos = val;
			++_end;
		}

此时，数组中只有4个元素（即数组中有四个元素），当我们想在第三个位置处插入元素0时，我们打印对应的结果，就会发现结果报错:

但是，当我们提前先把 5 也放入数组（即数组中有5个元素），此时再去进行插入操作时，结果又是正确的：

那么上述是什么问题导致的呢？我们先调试看看：

解释说明：

通过上述我们不难看出一个问题，程序只走了一步扩容操作，pos 位置此时没有发生变化，而 _start 和 _end 已经发送改变了。
此时这种情况就是一种经典的迭代器失效现象

解决方法：

我们需要更新 pos位置，根据相对位置来判断扩容之后处于新空间的位置是多少。

纠正写法：

        void insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _end);

			if (_end == _end_of_storage)
			{
				size_t len = pos - _start;  //迭代器失效问题（野指针）
				reserve(capacity() == 0 ? 4 : capacity() * 2);

				pos = _start + len;

			}

			iterator finish = _end - 1;
			while (finish >= pos)
			{
				*(finish + 1) = *finish;
				--finish;
			}

			*pos = val;
			++_end;
		}

但是上述改了之后是不是就 ok l呢？其实并不是的，程序其实还有 bug。

此时，很多小伙伴就会说我都已经更新了pos呀，但是我们经过调试之后发现没有起作用在这里：

解释说明：

最主要的原因就是这里是值传递，形参的改变是不会改变实参的，所以说外面的pos依旧没有实现更新操作，依旧会失效。

? 正确写法是通过返回值去解决问题的，返回的是迭代器，即新插入元素的位置

正确代码：

        iterator  insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _end);

			if (_end == _end_of_storage)
			{
				size_t len = pos - _start;  //迭代器失效问题（野指针）
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
			}

			iterator finish = _end - 1;
			while (finish >= pos)
			{
				*(finish + 1) = *finish;
				--finish;
			}

			*pos = val;
			++_end;

			return pos;
		}

4️⃣erase()

这里主要的就是从后往前删除的，这点需要大家注意一下。

代码如下：

        void erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _end);

			iterator start = pos + 1;
			while (start != _end)
			{
				*(start - 1) = *start;
				++start;
			}
			--_end;
		}

此时问题又来了，上述这样写会不会也有迭代器失效的问题呢？

? 首先，我们简单的测试一下：

从上述结果我们不难发现，经过验证程序是没有问题的。

? 接下来，我们在去看看在库中表现如何：

解释说明：

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效;
但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了.因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

如果大家下去验证，发现不管是不是在结束的位置，编译器都会默认程序崩溃。

我们通过调试可以发现，库中默认的检查手段直接就是使得程序发送崩溃了：

注意：

说明一点的是代码的结果还跟环境有关，大家可以去linux下进行测试看看结果是怎么样的

? 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效：

void TestString()
{
     string s("hello");
     auto it = s.begin();
     // 放开之后代码会崩溃，因为resize到20会string会进行扩容
     // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
     // 后序打印时，再访问it指向的空间程序就会崩溃
     //s.resize(20, '!');
     while (it != s.end())
     {
         cout << *it;
         ++it;
     }
     cout << endl;
     it = s.begin();
     while (it != s.end())
     {
         it = s.erase(it);
         // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
         // it位置的迭代器就失效了
         // s.erase(it); 
         ++it;
     }
}

终上所述，我们认为在erase之后，pos是会发生失效的，因此建议不要访问，行为结果未定义（具体跟编译器有关系）

5️⃣swap()

        void swap(vector<T>&arr)
		{
			swap(_start, arr.start);
			swap(_end, arr.end);
			swap(_end_of_storage, arr._end_of_storage);
		}

总结

到此，关于vector的全部内容便讲解完毕了，接下来我们简单的总结一下本文都学了什么

首先，在开头我先给大家介绍了关于 STL库中的容器有哪些，让大家初步的认识了各个容器，对其有个基本的印象；
其次，先给出了关于vector的基本概念介绍，让大家知道vector的作用以及优势；
接下来，我们通过结合文档内容，带大家去认识了vector中最常用的接口并模拟实现了各个函数接口；
最后，关于vector最重要的便是关于迭代器失效的问题以及解决方法（重点）需要大家掌握。

以上全是全文的基本内容了。感谢大家的阅读与支持！！！

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

上一篇
Unity实战（6）：如何做相机动画...

下一篇
【Spring篇】AOP案例

站长推荐

SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权
stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程）
U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决
【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述

您现在的位置是：首页 >技术杂谈 >【C++】容器篇（一）—— vector 的基本概述以及模拟实现网站首页技术杂谈

【C++】容器篇（一）—— vector 的基本概述以及模拟实现

前言

（一）基本介绍

1、相关定义

2、vector的引入

3、vector的优点

4、vector使用本质

（二）vector的使用

1、vector的定义

2、vector iterator 的使用

3、vector的空间增长

4、vector的增删查改

（三）接口函数的介绍

1、Member functions

1️⃣n个val构造

2️⃣迭代区间构造

3️⃣拷贝构造

2、Iterators

1️⃣begin()和end()

2️⃣rbegin()和rend()

3、Capacity

（四）vector模拟实现

1、成员变量

2、成员函数

1️⃣构造函数

2️⃣析构函数

3️⃣拷贝构造

3、迭代器

1️⃣begin() 和 end()

4、容量

1️⃣size()

2️⃣capacity()

3️⃣empty()

4️⃣reserve()

5️⃣resize()

5、元素访问

1️⃣operator[]

6、修改

1️⃣push_back()

2️⃣pop_back()

3️⃣insert()

4️⃣erase()

5️⃣swap()

总结

上一篇 Unity实战（6）：如何做相机动画...

下一篇 【Spring篇】AOP案例

站长推荐

上一篇
Unity实战（6）：如何做相机动画...

下一篇
【Spring篇】AOP案例