• C++ vector使用介绍以及模拟实现

    文章目录

    何为vector？

    vector是一个动态顺序表，可以理解为是一个数组不过该数组的大小是可变的，当数组的容量满了时，再插入数据vector会自动扩容。和string不同，string是一个类模板的实例，但vector是一个类模板，在初始化时需要我们传入模板参数。

    vector的初始化

    void test1()
{
	// 创建一个存储int对象的vector
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	for (auto e : v1)
	{
		cout << e << ' ';
	}
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述
    除了上面的创建vector的方式，还有两种方式创建vector

    void test2()
{
	string str = "hello";
	// 使用迭代器创建vector，注意迭代器指向的数据类型要和vecotr存储的数据类型相同
	vector<char> v1(str.begin(), str.end());
	for (auto e : v1)
	{
		cout << e << ' ';
	}
	cout << endl;

	// 初始化5个10的空间
	vector<int> v2(5, 10);
	for (auto e : v2)
	{
		cout << e << ' ';
	}
	cout << endl;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    vector的遍历

    vector有三种遍历方式（和string一样这里不再赘述）

    void test1()
{
	// 创建一个存储int对象的vector
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	// vector的遍历：范围for
	for (auto e : v1)
	{
		cout << e << ' ';
	}
	cout << endl;

	// 下标遍历
	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << ' ';
	}
	cout << endl;

	// 迭代器
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << ' ';
		it++;

	}
	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    vector的查找与增删

    vector的查找和删除，vector并没有实现find函数，但在algorithm中实现了一个find函数在这里插入图片描述

    传入要查找数据的迭代器区间，以及要查找的数据，该函数会返回一个指向查找到的数据的迭代器，如何我们可以通过vector的erase函数删除数据

    void test3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	for (auto e : v)
	{
		cout << e << ' ';
	}
	cout << endl;
	// 通过find查找数据，再进行删除
	auto it = find(v.begin(), v.end(), 3);
	v.erase(it);

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述
    vector的插入需要传入一个迭代器，将数据插入到迭代器的位置，其他数据往后移动
    在这里插入图片描述

    void test4()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

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

	// 头插数据到vector中
	v.insert(v.begin(), -1);
	v.insert(v.begin(), -2);
	v.insert(v.begin(), -3);

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    在这里插入图片描述

    vector的模拟实现

    在这里插入图片描述

    这次的模拟实现不再使用size，capacity来表示数组的大小和容量，而使用_start指针指向数组的第一个元素，_end指向数组最后一个存储数据的元素的下一个位置，_endofstrore指向数组最后元素的下一个位置。之所以用指针实现vector是因为STL库中也是这样实现，使用指针的方式更贴合“模拟”二字。

    先给出vector的结构声明，接着一个个的实现声明中的函数

    namespace myVector
{
	template <class T>
	class vector
	{
		typedef T* iterator;
		typedef const T* const_iterator;
	public:
		void swap(const vector<T> v);
		// 构造和析构
		vector();
		template <class InputIterator>
		vector(InputIterator first, InputIterator last);
		vector(int n, T val);  // 用n个T构造vector
		vector(const vector<T>& v);
		~vector();
		vector<T>& operator=(vector<T> v);

		// 迭代器
		iterator begin() { return _start; }
		iterator end() { return _finish; }
		const_iterator begin() const { return _start; }
		const_iterator end() const { return _finish; }

		// 容量
		size_t size() const;
		size_t capacity() const;
		void reserve(size_t n);
		void resize(size_t n, T val = T());

		// 修改
		void push_back(const T& val);
		void pop_back();
		void insert(iterator pos, const T& val);
		void erase(iterator pos);

		// 下标访问
		T& operator[](size_t n);
		const T& operator[](size_t n) const;


	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    迭代器

    在这里插入图片描述
    vector的迭代器就是指针，这些函数的作用就是返回指向vector开始或结束处的指针，逻辑简单，代码就写在类里了。

    构造和析构

    文档中声明vector的构造有三种：1.无参，2.用迭代器区间的数据构造，3.用n个val值初始化。最后一个是拷贝构造。
    在这里插入图片描述
    无参的构造函数就是将vector的三个原生指针置空

    template <class T>
myVector::vector<T>::vector()
{
	_start = nullptr;
	_finish = nullptr;
	_endofstore = nullptr;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    用迭代器first到迭代器last之间的数据构造并初始化一个vector，这里要用first迭代器遍历区间，然后调用push_back将遍历得到的数据尾插到vector中，push_back后面会实现。而迭代器类型肯定是不一样的，有指向内置类型的迭代器，指向自定义类型的迭代器，这就需要使用模板函数，再使用一个模板参数，编译器会根据实参的类型生成对应的函数

    template <class T>
template <class InputIterator>
myVector::vector<T>::vector(InputIterator first, InputIterator last)
{
	while (first != last)
	{
		push_back(*first);
		begin++;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    用n个val构造并初始化vector时，这个val值可以不给，也就是val是默认参数，当使用者不给形参时，初始化vector的val值就是默认的。但这样就有一个问题，val的默认值应该是什么？当val是自定义类型对象时，使用默认构造函数构造的对象就是val的默认值（形参中写：T val = T() )，但val是内置类型对象如int，char时，应该怎样操作？其实C++对于内置类型也支持默认构造函数，比如int i = 0，这是创建int对象并初始化成0，也能写成int i = int()，这里的意思就是创建int对象并调用int的默认构造函数初始化对象。
    在这里插入图片描述
    可以看到vs下int的默认构造是将int赋值为0。综上，得出结论：C++中的内置类型如int，char可以看成一个类，所以int类有默认构造函数，而C++这样做的原因是为了更好的支持模板

    而实现就很简单了，for循环将n个val尾插到vector中

    template <class T>
myVector::vector<T>::vector(int n, T val = T())
{
	for (int i = 0; i < n; i++)
	{
		push_back(val);	
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这里还要注意一个问题，int n最好不要写成size_t n，如果这样，当想用5个5初始化vector时程序会报错
    在这里插入图片描述
    大概就是非法访问内存，原因：vector< int> v(5, 5)中的两个5都是int类型，编译器在编译时不会将第一个5隐式类型转换成size_t，因为vector还有一个构造函数在这里插入图片描述
    由于该构造的两个参数类型相同，两个5又都是int类型，编译器会生成该模板对应的函数，再调用它，而该函数需要对指针解引用，传个5进去，对5解引用当然是非法访问了。所以最好将n的类型写为int

    vector的拷贝构造，用传入的vector对象v，构造函数出tmp对象，再将tmp与this指向的vector交换。

    // 两个vector的交换，只要交换它们的三个原生指针，这里的交换调用std的交换
template <class T>
myVector::vector<T>::swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstore, v.endofstore);
}

// 用v拷贝构造
template <class T>
myVector::vector<T>::vector(const vector<T>& v)
{
	_start = nullptr;
	_finish = nullptr;
	_endofstore = nullptr;
	vector tmp(v.begin(), v.end()); // 用v构造tmp对象
	swap(tmp); // 此时的tmp是v的复制，将它交换
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    至于拷贝构造前为什么要将当前的vector的原生指针置空，因为如果不置空三个指针就是随机值，tmp是一个局部变量，出作用域销毁，因为交换此时tmp的三个原生指针指向随机空间，销毁tmp前要是否tmp的动态空间，而释放随机空间非法，所以要先将当前的原生指针置空。

    析构函数就是将vector的动态空间释放

    template <class T>
myVector::vector<T>::~vector()
{
	delete[] _start; // 因为_start指向的空间是连续的，所以用delete[]
}

    • 1
    • 2
    • 3
    • 4
    • 5

    最后一个是vector的赋值重载，如果不写=的重载，编译器默认生成的重载只是一个浅拷贝，而vector涉及动态内存的申请，所以需要自己实现该重载，完成深拷贝。不把函数参数写成引用，在函数实例化形参时会去调用vector的拷贝构造函数，这时的形参就是一份拷贝，之后只要将当前的vector与形参交换。

    template <class T>
myVector::vector<T>& myVector::vector<T>::operator=(vector<T> v)
{
	swap(v);
	return *this; // 返回当前的vector为了支持连续赋值
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    (vector的构造，如果无参：将三个指针置空，如果参数是两个迭代器：用迭代器初始化空间，当first迭代器不等于last迭代器，将first迭代器指向的数据push_back。push_back将数据尾插到vector，当容量满时调用reserve函数扩容，reserve：new n个T（存储的数据类型）空间，使tmp指向该空间，再将原来的数据拷贝到tmp指向的空间，注意这里的拷贝不是简单的浅拷贝，如果存储的数据是string，vector需要管理内存的类型，浅拷贝会使程序崩溃，所以不能直接用memcpy简单的拷贝数据，而是要用=，将数据一个一个的拷贝进去。而=如果不重载，也是一个浅拷贝，所以需要对=进行重载，重载=时使用现代写法，参数是vector但不是引用，这里会复用参数是vector的拷贝构造函数，参数是vector的拷贝构造函数会复用参数是两个迭代器的构造函数，又复用push_back，如果push_back的数据不是内置类型，又会调用=，直到push_back的数据类型是内置类型)

    关于容量

    在这里插入图片描述
    容量有四个接口，size()返回当前vector存储数据的个数，capacity()返回当前vector最大能存储数据的个数，这两个接口简单直接贴代码

    template <class T>
size_t myVector::vector<T>::size() const
{
	return _finish - _start; // 指针相减得到两指针之间的数据个数
}

template <class T>
size_t myVector::vector<T>::capacity() const
{
	return _endofstore - _start;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    reserve()设置vector的容量，如果参数n大于当前的capacity，进行扩容，小于或等于，什么都不做。扩容时，先申请n个T的空间，再将原来空间上的数据深拷贝进新开辟的空间中（凡是有申请资源的类，都要注意深拷贝的问题），释放原来空间。

    reserve还涉及迭代器失效问题，什么是迭代器失效？两个方面：1.迭代器指向空间被释放，形成野指针但你没发现。2.迭代器指向的位置意义变了。扩容时，在拷贝完原来数据后需要释放原来的空间，这时的迭代器仍然是指向原来的空间（包括原生指针），所以需要对迭代器进行更新，_start指向新开辟的空间，_finish和_endofstore却指向原来的空间，_endofstore只要指向_start后的n个位置就行，但_finish要指向_start后size个位置，而size函数要用_finish - _start，这时的_finish已经是个失效的迭代器，所以不能调用size函数，需要先记录原来的size。

    template <class T>
void myVector::vector<T>::reserve(size_t n)
{
	if (n > capacity())
	{
		int sz = size();
		T* tmp = new T[n];
		if(_start) // 为空不进行拷贝
		{
			for (int i = 0; i < size(); i++)
			{
				tmp[i] = _start[i]; // 复用=的重载，如果vector存储的数据需要深拷贝，将深拷贝工作交给=的重载，前提是该类型=的重载实现了深拷贝，当然如果没有实现这里会出问题，但这不是我们的事
			}
			delete[] _start; // 拷贝完别忘记释放
		}			
		_start = tmp;
		_finish = _start + sz;
		_endofstore = _start + n;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    （记录一个在模拟实现中想到的问题，在实现reserve时，最开始没有进行vector为空并不进行拷贝的if条件判断，之后便思考是否有必要进行该判断，_start为空，说明其他两个指针也为空，在for循环的条件判断时调用size函数，以此引出一个疑问，**两个空指针是否能相减？**便敲了代码验证在这里插入图片描述
    可以看到，两个指针相减的前提是指针类型要统一，而nullptr作为一个空指针是没有类型的。但对于一个空的vector调用size却不会报错，并且还打印出了0，思索了一会才明白这只是C语言的语法基础。两个指针相减得到的是它们之间数据个数，这是怎么做到的？大概就是地址相减后再除以对应类型的字节数得到最后的数据个数，但nullptr没有数据类型，想要跑通这行代码只要用强制类型转换，所以不用判断vector是否为空也行，之后的delete对于空指针不释放）在这里插入图片描述
    题外话结束，resize，对于n大于size并且大于capacity的情况，resize就是reserve+初始化空间，开辟空间后，尾插数据，改变size。对于n只大于size小于capacity的情况，尾插数据使size到n。对于n小于size的情况，修改_finish指针达到删除数据的效果

    template <class T>
void myVector::vector<T>::resize(size_t n, T val = T())
{
	if (n > capacity())
	{
		reserve(n); 
	}
	
	if (n > size())
	{
		while (_finish != _start + n)
		{
			push_back(val);
			_finish++;
		}
	}
	else
	{
		_finish = _start + n;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    关于修改

    在这里插入图片描述
    clear就是清空vector中的数据，只要将_finish指向_start的位置就行，代码简单直接写在类里。

    push_back尾插数据到vector中，插入数据前要检查是否需要扩容，之后解引用_finish，将数据写入，最后++_finish。pop_back就是直接–_finish

    template <class T>
void myVector::vector<T>::push_back(const T& val)
{
	// 如果容量为0，直接乘2还是0，所以要判断一下
	if (_finish == _endofstore)
		reserve(capacity() == 0 ? 4 : capacity() * 2);		
	*_finish = val;
	_finish++;
}

template <class T>
void myVector::vector<T>::pop_back()
{
	if (size()) // 不为空了再删除
		--finish;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    insert和erase都涉及到迭代器失效问题，在pos位置插入一个数据，如果容器满了，扩容后虽然容器的三个迭代器不会失效，但用户传的迭代器pos会失效：指向原来的空间，所以在扩容要前先计算pos位置与_start的相对位置。之后就是移动数据，插入val值。但还有一个问题，有这样一个场景：在所有偶数前插入一个2，然后我们用it迭代器去遍历整个vector，随着2的插入vector进行了扩容，而it指向的还是原来的空间（虽然vector的三个迭代器没有失效，但用来遍历vector的it失效了），标准库是怎么解决这个问题的？通过返回迭代器，一个指向新插入数据的迭代器，这样我们在每次的插入后更新it，it = insert(… , …)，就能保证迭代器不失效
    在这里插入图片描述

    template <class T>
typename myVector::vector<T>::iterator myVector::vector<T>::insert(iterator pos, const T& val)
{
	if (_finish == _endofstore)
	{
		int n = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + n; // 更新pos迭代器
	}
	// 数据的挪动
	auto end = _finish;
	while (end > pos) // 挪动数据
	{
		*end = *(end - 1);
		end--;
	}
	*pos = val; // 插入数据
	_finish++;

	return pos;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    （insert的返回值是一个迭代器，在类外写这个函数时，需要在迭代器前加上类名::，表示该迭代器是定义在这个类下的，但这样与类名::静态变量名，这种访问静态变量的方式冲突，所以编译器不知道这里的返回类型是一个类型还是一个静态变量，编译器会报错，需要加上typenmae显式地告诉编译器这是一个类型）

    在这里插入图片描述
    再来看删除，本质上就是移动数据将被删除的数据覆盖，要注意的是erase返回值是指向被删除位置的下一个位置的迭代器，其实就是还是指向被删除的位置，因为后面的数据向前移动了。

    template <class T>
typename myVector::vector<T>::iterator myVecotr::vector<T>::erase(iterator pos)
{
	if (pos >= begin() && pos < end()) // 判断pos的合法性
	{
		auto end = pos + 1;
		while (end < _finish)
		{
			*(end - 1) = *end;
			end++;
		}
		_finish--;
	}
	return pos;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    下标访问

    在这里插入图片描述
    通过下标不仅要支持读，还要支持写，所以下标访问函数的返回值是数据的引用

    template <class T>
T& myVector::vector<T>::operator[](size_t n)
{
	assert(n < size()); // 断言n的合法性
	return _start[n];
}

template <class T>
const T& myVector::vector<T>::operator[](size_t n) const
{
	assert(n < size()); 
	return _start[n];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 相关阅读:
    制氢厂氢气泄漏安全监测：氢气传感器守护“氢”安全
    BIT-7文件操作和程序环境（16000字详解）
    蚁群算法ACO求解连续函数问题
    机器学习从0到1
    61、SpringBoot -----跨域资源的设置----局部设置和全局设置
    【juc】ReentrantReadWriteLock之缓存（仅当学习）
    【C++ 结构体的构造函数使用】
    ASEMI整流桥DB307S参数，DB307S规格，DB307S封装
    git常用命令
    极客日报：张一鸣以594亿美元成中国互联网首富；苹果称华为商标抄袭AIRPODS被驳回；​Chrome 95发布
  • 原文地址：https://blog.csdn.net/weixin_61432764/article/details/125874027