✨个人主页： 北 海
🎉所属专栏： C++修行之路
🎊每篇一句： 图片来源

  • The power of imagination makes us infinite.
    • 想象力的力量使我们无限。

遇见彩虹，吃定彩虹

文章目录

🌇前言

vector 是 STL 中的容器之一，其使用方法类似于数据结构中的 顺序表，得益于范型编程和 C++ 特性的加持，vector 更强大、更全能；在模拟实现 vector 时，还需要注意许多细枝末节，否则就很容易造成重复析构及越界访问

vector
出自书籍《STL源码剖析》 侯捷著

本文重点： 深度拷贝、迭代器失效

🏙️正文

vector 的结构比较特殊，成员变量为三个指针

#pragma once
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <string>
using std::string;

namespace Yohifo
{
	template<class T>
	class vector
	{
	public:
		typedef T value_type;
		typedef value_type* pointer;	//指针
		typedef const value_type* const_pointer;
		typedef value_type* iterator;	//迭代器
		typedef const value_type* const_iterator;
		typedef value_type& reference;	//引用
		typedef const value_type& const_reference;
		
	private:
		iterator _start;	//指向起始位置
		iterator _finish;	//指向有效元素的下一个位置
		iterator _end_of_storage;	//指向可用空间的下一个位置
	};
}

图解

1、默认成员函数

默认成员函数需要自己设计，因为涉及深浅拷贝问题

默认构造函数、带参构造函数、迭代器区间构造

//默认构造
vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

//带参构造
vector(size_t n, const T& value = T())
	:vector()
{
	reserve(n);	//扩容
	while (n--) push_back(value);	//逐个尾插
}
//额外版本，避免匹配上迭代器区间构造
vector(int n, const T& value = T())
	:vector()
{
	reserve(n);	//扩容
	while (n--) push_back(value);	//逐个尾插
}

//迭代器区间构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
	:vector()
{
	//考虑提前计算容量
	InputIterator cur = first;
	int len = 0;
	while (cur != last) ++len, ++cur;
	reserve(len);
	while (first != last) push_back(*first), ++first;
}

注意： 在设计带参构造函数时，需要再额外提供一个 vector(int n, const T& value = T()) 版本，以防使用 vector<int> v(10, 6) （构造对象，内容为10个6）优先匹配上迭代器构造，此时会造成 非法间接寻址 错误

报错
此时多处用到了 匿名对象 作为缺省值

vector(size_t n, const T& value = T());
vector(int n, const T& value = T());

因为 T 类型不确定，在设置缺省值时，只能使用 匿名对象 的方式

  • 匿名对象 生命周期只有一行，但在被 const 修饰后，其生命周期会延长
  • 内置类型也能创建匿名对象，比如 int()、char() 是合法可用的

带参构造、拷贝构造、迭代器区间构造等函数创建新对象前，需要先初始化，有多种初始化方法：

  1. 在定义成员变量后设置缺省值
  2. 在创建新对象前手动进行初始化(初始化列表)
  3. 调用 默认构造函数 进行初始化

这里采用的是初始化列表调用 默认构造函数 初始化的方式

拷贝构造

//拷贝构造-传统写法
vector(const vector<T>& v)
	:vector()
{
	reserve(v.capacity());	//扩容
	size_t pos = 0;
	while (pos < v.size()) *(_start + pos) = *(v.begin() + pos), ++pos;
	_finish = begin() + v.size();
}
拷贝构造-现代写法
//vector(const vector<T>& v)
//	:vector()
//{
//	vector<T> tmp(v.begin(), v.end());	//构造临时对象
//	swap(tmp);	//直接交换
//}

拷贝构造对象前可以 先进行扩容，避免空间浪费； 采用逐个数据赋值拷贝的方式进行拷贝，因为 T 有可能是自定义类型，逐个赋值可以避免浅拷贝问题

  • 比如 T 为 string 类型，实际调用时是这样的 this[pos] = v[pos]（string 对象，调用对应的赋值重载函数）

注意： vector 的拷贝构造函数必须自己写，默认生成的是 浅拷贝

现代写法着重交换思想，利用迭代器区间构造出临时对象，再将临时对象 “交换” 给当前对象即可
这种方式有点窃取劳动成果的感觉~

赋值重载

//赋值重载-传统写法
vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)
	{
		reserve(v.capacity());	//扩容
		size_t pos = 0;
		while (pos < v.size()) *(_start + pos) = *(v.begin() + pos), ++pos;
		_finish = begin() + v.size();
	}

	return *this;
}
赋值重载-现代写法
//vector<T>& operator=(vector<T> tmp)
//{
//	swap(tmp);

//	return *this;
//}

赋值重载的传统写法与拷贝构造基本一致，赋值重载中不需要新建对象，因为是 “赋值”

注意： 赋值前，可以先判断两个对象是否为同一个，如果是，则不需要进行操作

析构函数

//析构函数
~vector()
{
	delete[] _start;
	_start = _finish = _end_of_storage = nullptr;
}

_start 指向已开辟空间的首位置，可以直接进行空间释放

注意： 空间申请时，使用的是 new []，因此释放时需要使用 delete []

1.1、经典问题：深度拷贝

众多构造函数都离不开空间调整函数 reserve，所以这里提前进行学习，并且 reserve 在实现时会出现一个经典问题：深浅拷贝

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();	//需要先保存 _start 与 _finish 间的距离
		pointer tmp = new value_type[n];	//开辟新空间
		if (begin())
		{
			//memcpy(tmp, begin(), size() * sizeof(T));	//不能直接移动
			size_t pos = 0;
			while (pos < sz)
			{
				//调用自定义类型的赋值重载函数，完成深拷贝
				*(tmp + pos) = *(begin() + pos);	//深拷贝
				pos++;
			}
			delete[] begin();	//释放原空间
		}

		_start = tmp;	//赋值新空间
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

函数执行步骤：

  • 判断 n 是否大于容量，大于才需要进行扩容
  • 保存有效元素数（大小），后面有用
  • 三步走：开辟新空间 -> 移动元素至新空间 -> 释放旧空间，更改指向

注意： 在将旧空间中的数据移动至新空间时，不能直接通过 memcpy/memmove 的方式进行数据移动，因为这些库函数都是 浅拷贝，使用后会造成重复析构问题

举例：使用 memcpy 进行数据迁移

对象中已存在字符串 This is a string，现在进行空间调整
浅拷贝
旧空间释放后，其 string 对象被释放，与此同时新空间中的 string 对象也将同步失效
结果
程序运行结束时，调用析构函数进行空间释放（此时会调用 string 的析构函数进行字符串释放），因为旧空间与新空间中的成员皆为同一个，所以会出现 空间重复释放问题
引发错误

改良：调具体对象的赋值重载函数进行深拷贝(赋值)，不再使用 memcpy 浅拷贝
正确结果
实际上，拷贝构造、赋值重载、reserve 都需考虑深度拷贝的问题
一句话总结：对于自定义类型来说，在进行拷贝/赋值等操作时，调用对应的赋值重载函数即可

reserve 扩容时，发生了这些事情：
扩容
出自 《STL源码剖析》

2、迭代器相关

vector 中的迭代器就是原生指针，如 begin() == _start、end() == _finish

typedef T value_type;
typedef value_type* iterator;	//迭代器
typedef const value_type* const_iterator;
		
//=====迭代器设计=====
iterator begin() { return _start; }
iterator end() { return _finish; }

const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

注意：

  • 需要提供两个迭代器版本，即 const 对象的 const 迭代器
  • 反向迭代器在后续文章中进行专门讲解

利用前面的函数构造对象，在通过迭代器遍历对象，结果如下
结果

3、容量相关

3.1、查看容量

直接通过迭代器获取值

//=====容量相关=====
size_t size() const { return end() - begin();  }
size_t capacity() const { return _end_of_storage - begin();  }
bool empty() const { return begin() == end();  }

3.2、容量调整

可以调整容量(reserve)，也可以调整大小(resize)
reserve 前面已经介绍过了，这里来看看 resize

void resize(size_t n, const_reference val = value_type())
{
	if (n < size())
		erase(begin() + n, end());
	else
		insert(end(), n - size(), val);
}

操作步骤：

  • 判断 n 是否大于大小
  • 如果小于，执行删除，区间为 [begin() + n, end()]
  • 如果小于或等于，就执行插入，区间为 [end(), n - size(), val]

value_type 就是 T，缺省值为默认对象值

4、数据访问相关

4.1、下标访问

下标访问有两种方式：operator[] 和 at

//=====数据访问=====
reference operator[](size_t pos)
{
	assert(pos >= 0 && pos < size());
	return *(begin() + pos);
}
const_reference operator[](size_t pos) const
{
	assert(pos >= 0 && pos < size());
	return *(begin() + pos);
}

reference at(size_t pos) { return (*this)[pos]; }
const_reference at(size_t pos) const { return (*this)[pos]; }

at 复用 operator[] 的代码，确保函数的稳定性~

4.2、首尾数据

获取首尾数据也可以直接复用 operator[]

reference front() { return (*this)[0]; }
const_reference front() const { return (*this)[0]; }
reference back() { return (*this)[size() - 1]; }
const_reference back() const { return (*this)[size() - 1]; }

测试结果如下：
示例

5、修改相关

5.1、首尾插删

void push_back(value_type val)
{
	if (size() == capacity())
		reserve(capacity() == 0 ? 4 : capacity() * 2);	//考虑容量为0的情况

	*_finish++ = val;	//在最后一个位置插入
}

void pop_back() 
{
	assert(!empty());
	--_finish;
}

注意： 尾插时，需要先判断容量是否足够，不够则需要扩容；同时因为容量默认从 0 开始，假若是第一次插入，需将容量扩容为 4

关于尾插，还有一个类似的拼接函数 assign，将某段区间或 n 个 val 值，拼接至对象后面

//=====数据修改=====
template <class InputIterator>
void assign(InputIterator first, InputIterator last)
{
	//迭代器区间拼接
	InputIterator cur = first;
	int len = 0;
	while (cur != last) ++len, ++cur;
	reserve(len);
	while (first != last) push_back(*first), ++first;
}
void assign(int n, const value_type& val)
{
	reserve(n);	//提前扩容
	while (n--) push_back(val);
}

执行结果如下：
结果

5.2、任意位置插删

任意位置插删更为自由，同时也更加 “危险”

iterator insert(iterator pos, const_reference val)
{
	//先记录当前迭代器的位置
	size_t sz = pos - begin();
	if (size() == capacity())
		reserve(capacity() == 0 ? 4 : capacity() * 2);	//考虑容量为0的情况

	pos = begin() + sz;	//更新迭代器
	iterator cur = end();
	while (cur != pos) *cur = *(cur - 1), --cur;
	*cur = val;	//插入数据
	++_finish;	//尾向后移动

	return pos;	//返回新迭代器位置
}
iterator insert(iterator pos, size_t n, const_reference val)
{
	while (n--) pos = insert(pos, val), pos++;	//正确写法

	return pos;
}

iterator erase(iterator pos)
{
	assert(pos >= begin() && pos < end());
	iterator cur = pos;
	while (pos != end()) *pos = *(pos + 1), ++pos;
	--_finish;
	return cur;
}
iterator erase(iterator first, iterator last)
{
	//迭代器区间删除
	//两个结束条件：last == _finish
	//while (last != _finish) *first = *(last + 1), ++first, ++last;	//错误写法
	while (last != _finish) *first = *last, ++first, ++last;	//正确写法
	_finish = first;
	return _finish;
}

2023.5.16 更新

迭代器区间删除时，区间为 左闭右开，在进行数据覆盖时，需要写成 *first = *last 而非 *first = *(last + 1)，这样会导致删除出现问题

图解

感谢大佬：LinAlpaca 指出错误

注意： insert 后迭代器 pos，需要及时更新

若产生扩容行为，迭代器 pos 将指向失效空间，这就是迭代器失效情况之一

错误方法

正确方法
迭代器失效时的具体表现：
具体结果
这只是迭代器失效的其中一种情况：没有更新迭代器位置

5.3、经典问题：迭代器失效

下面再来看一个迭代器失效场景
比如下标这段代码会运行失败

void TestVector3()
{
	vector<int> v;
	
	auto it = v.begin();
	int val = 0;

	while (val < 100)
		v.insert(it++, val++);

	for (auto e : v)
		cout << e << " ";
}

结果：
结果
原因：
迭代器失效
我们通常认为，在 insert 后，迭代器失效，不能再使用，当然将此迭代器更新，也能正常使用

while (val < 100)
{
	it = v.insert(it, val++);
	it++:	//接收 insert 返回值，更新迭代器
}

修改后结果
注意： erase 后，也会出现迭代器失效情况，在 PJ 版本中，对 erase 迭代器失效情况零容忍，只要是删除后没有即使更新迭代器，就会直接报错；而在 SGI 版中，检查相对比较薄弱，即使是删除最后一个元素，它也不报错，这会导致异常行为

对于 erase 迭代器实现情况：

  • PJ 版：零容忍，检查很严格
  • SGI 版：结果未定义，缺乏检查

从实用角度来看，PJ 版的处理方法明显更合理

5.4、交换、清理、排序

再补充一些常用函数

void swap(vector<T>& v)
{
	//交换三个内置类型，效率要高得多
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end_of_storage, v._end_of_storage);
}

void clear() { erase(begin(), end()); }

即使库中提供了全局性的 std::swap 函数，vector 还是提供了额外的 swap 交换函数，因为 std::swap 中会发生多次拷贝构造，效率较低，而 swap 效率是极高的，只需交换三个成员变量

vector 中使用的是随机迭代器，可以使用库中的排序函数 std::sort

void TestVector8()
{
	int arr[] = { 1,9,5,4,3,2,6,7,10,8 };
	vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));

	//使用库中的排序函数
	std::sort(v.begin(), v.end());	//默认为升序（仿函数）
	//std::sort(v.begin(), v.end(), std::less<int>());	//其实默认是这样的，为缺省值

	for (auto e : v)
		cout << e << " ";
	cout << endl;


	//利用仿函数，进行降序排序
	std::sort(v.begin(), v.end(), std::greater<int>());

	for (auto e : v)
		cout << e << " ";
	cout << endl;
}

结果
这里是第一次用到仿函数，后续在进行适配器讲解时，会详细介绍，现在只需知道怎么用就行了

对于 std::sort 来说

  • 如果想升序的话，使用 std::less<T>()
  • 降序使用 std::greater<T>()

注意： 使用仿函数需要头文件 functional，使用 std::sort 需要头文件 algorithm；std::sort 函数只能用于 随机迭代器

6、源码

本文中涉及的所有代码都在这个仓库中：Gitee

gitee

🌆总结

以上就是本篇关于 vector 模拟实现的全部内容了，感兴趣的同学可以自己试着写一下，不过需要特别注意 深度拷贝 和 迭代器失效 问题

如果你觉得本文写的还不错的话，可以留下一个小小的赞👍，你的支持是我分享的最大动力！

如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正

星辰大海

相关文章推荐

C++ STL学习之【vector的使用】

===============

STL 之 string 类

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】

===============

内存、模板

C++【模板初阶】

C/C++【内存管理】

感谢支持

# c++ # 学习 # 开发语言 # 后端
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生