当前位置： 首页 > article >正文

vector的使用，以及部分功能的模拟实现（C++）

article 2025/1/23 16:22:50

1.vector的介绍及使用

1.1 vector的介绍

vector是STL容器中的一种常用的容器，和数组类似，由于其大小(size)可变，常用于数组大小不可知的情况下来替代数组。

vector也是一种顺序容器，在内存中连续排列，因此可以通过下标快速访问，时间复杂度为O(1)。但是，连续排列也意味着大小固定，数据超过vector的预定值时vector将自动扩容。

1.2 vector的使用

在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

1.2.1 vector的定义

(constructor)构造函数声明接口说明
vector()（重点）无参构造
vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
vector (const vector& x); （重点）拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

举例：

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int>v1;
	vector<int>v2(5,5);
	vector<int>v3(v2);
	vector<int>v4(v2.begin(), v2.end());
	return 0;
}

结果：

 1.2.2 vector iterator 的使用

iterator的使用接口说明
begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下 一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置 的reverse_iterator

举例：

void test2()
{
	vector<int>v2(5, 5);
	vector<int>::iterator it = v2.begin();
	while (it != v2.end())
	{
		cout << *it << " ";
		it++;
	}
}

结果：

 1.2.3 vector 空间增长问题

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize改变vector的size
reserve改变vector的capacity

a）capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2 倍增长的。不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。

通过下面一段代码来演示：

void test3()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

vs下的结果：

making foo grow:

capacity changed: 1

capacity changed: 2

capacity changed: 3

capacity changed: 4

capacity changed: 6

capacity changed: 9

capacity changed: 13

capacity changed: 19

capacity changed: 28

capacity changed: 42

capacity changed: 63

capacity changed: 94

capacity changed: 141

g++运行结果：

making foo grow:

capacity changed: 1

capacity changed: 2

capacity changed: 4

capacity changed: 8

capacity changed: 16

capacity changed: 32

capacity changed: 64

capacity changed: 128

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

举例：

void test4()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

结果：

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

 1.2.3 vector 增删查改

vector增删查改接口说明
push_back（重点）尾插
pop_back （重点）尾删
find查找。（注意这个是算法模块实现，不是vector的成员接口）
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] （重点）像数组一样访问

push_back和pop_back演示：

void test5()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.pop_back();
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.pop_back();
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：

 find（这个是算法里面的函数，需要配合迭代器使用）演示：

void test6()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	vector<int>::iterator pos=find(v.begin(), v.end(), 3);
	cout << pos-v.begin() <<endl;
}

结果：

find函数第一个参数是迭代器的起始位置，第二参数是结束位置，第三个是寻找的对象，找到则返回第一次找到该对象位置的迭代器，否则返回结束位置。

insert和erase演示：

void test7()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.insert(v.begin() + 2, 10);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.erase(v.end()-1);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：

这个第一个参数都是需要传迭代器来确定需要插入，或删除的位置。

swap演示：

void test8()
{
	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> v2;
	v2.push_back(5);
	v2.push_back(4);
	v2.push_back(3);
	v2.push_back(2);
	v2.push_back(1);
	cout << "v1:";
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "v2:";
	for (auto& e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
	v1.swap(v2);
	cout << "v1:";
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "v2:";
	for (auto& e : v2)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：

 operator[]演示：

void test9()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}

结果：

 2.vector深度剖析及模拟实现

vector在底层实现中，其实类里面并不是像小编之前数据结构中，那样有三个成员：T* arr，size_t size，size_t capacity，而是T* _start,T* _finish,T* end_of_storage。

_start表示有效元素开始的迭代器位置，_finish表示有效元素结束下一个迭代器位置，_end_of_storage表示空间大小结束下一个迭代器位置。

 2.1实现默认构造函数

这里为了和STL库里面的vector区分用命名空间进行隔离，这里利用缺省参数，初始化列表进行初始化：

namespace iu
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
        typedef const T* const_iterator;
		vector()
		{}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage= nullptr;
	};
}

2.2析构函数

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

2.3元素个数size(),空间大小capacity()

size_t size() const
{
	return _finish - _start;
}
size_t capacity() const
{
	return _end_of_storage - _start;
}

2.4迭代器实现begin(),end()

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

这里需要重载const修饰的类型，如果是元素类型是const例如：const T，以及范围for使用时对象是const修饰时，就需要重载这种const的end(),begin(),才能使用。

2.5重载[]

const T& operator[](size_t pos) const
{
	assert(pos < size());
	return _start[pos];
}
T& operator[](size_t pos)
{
	assert(pos < size());
	return _start[pos];
}

 这里也需要重载const修饰的类型，和上面begin(),end()实现的原因是一样的。

2.6 开辟空间大小void reserve(size_t n)

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldsize = size();
		T* tmp = new T[n];
        //注意这里不能使用memcpy(tmp,_start,sizeof(T)*oldsize)来赋值
		for (size_t i = 0; i < oldsize; i++)
		{
			tmp[i] = _start[i];
		}
		delete[] _start;

		_start = tmp;
		_finish = _start + oldsize;
		_end_of_storage = _start + n;
	}
}

这里首先判断n是否大于capacity()，如果小于就不做处理，大于就需要扩容，这里需要保存size()大小，如果将tmp赋给_start时，这是_start已经更新，再利用size()去确定_finish就会有问题。

 其次就是不能用memcpy来赋值

用下面的例子来解释：

int main()
{
	iu::vector<string> v1;
	v1.push_back("1111111111111111111111111");
	v1.push_back("1111111111111111111111111");
	v1.push_back("1111111111111111111111111");
	v1.push_back("1111111111111111111111111");
	v1.push_back("1111111111111111111111111");

	for (const auto& e : v1)
	{
		cout << e << endl;
	}
	cout << endl;
	return 0;
}

结果：

这里是为什么？这里空间大小不够，所以要扩容，其实是memcpy浅拷贝导致的，这里delete[]释放空间之后，但是浅拷贝，还是指向原来的释放的空间，再去访问就是野指针，就出错了。

2.7 控制元素个数void resize(size_t n,const T& val=T())

void resize(size_t n,const T& val=T())
{
	
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

首先判断是否小于size()，小于就直接将_finish位置向前调整即可，大于就需要先扩容，因为在前面实现的reserve中有判断是否需要扩容，所以这里直接将n传给reverse，自然会判断，然后再将增加的元素个数，初始化为val，调整_finish位置。

2.8 插入元素iterator insert(iterator pos, const T& x)

iterator insert(iterator pos, const T& x)
{
	assert(pos <= _finish && pos >= _start);
	if (_finish == _end_of_storage)//更新迭代器
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		pos = _start + len;
	}
	iterator it = _finish - 1;
	while (it >= pos)
	{
		*(it + 1) = *it;
		--it;
	}
	*pos = x;
	++_finish;
	return pos;
}

这里首先判断空间是否已满，满了需要扩容，再插入，这里和前面reserve有相同的问题，扩容之后，_start指向一块新的空间，但pos还是指向原来释放掉的空间，所以需要更新迭代器，确定原来len，再更新pos，在将pos及之后的数据依次向后移动一位，再插入x,返回pos位置。

 2.9 删除元素iterator erase(iterator pos)

iterator erase(iterator pos)
{
	assert(pos <= _finish && pos >= _start);
	auto it = pos + 1;
	while (it < _finish)
	{
		*(it - 1) = *it;
		it++;
	}
	--_finish;
	return pos;
}

直接将pos+1位置的数据都向前移动一位，实现数据覆盖，然后_finish--就相当于删除pos位置元素，返回pos位置。

2.10 尾插void push_back(const T& val = T())，尾删void pop_back()

void push_back(const T& val = T())
{
    insert(end(), val);
}
void pop_back()
{
	assert(size() > 0);
	--_finish;
}

这里尾插直接复用insert函数，第一个参数直接传end()位置的迭代器，第二传插入的元素，尾删直接_finish--就行了。

2.11 拷贝构造函数

vector(const vector<T>& v)
{
	reserve(v.size()); 
	for (auto e : v)
	{
		push_back(e);
	}
}

 this开辟和v一样大的元素个数相等的空间大小，再将v中的元素，依次尾插到this中。

2.12 赋值运算符重载

void swap(vector<int>& v)
{
	std::swap(_start,v._start);
	std::swap(_finish,v._finish);
	std::swap(_end_of_storage,v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

 这里利用前面（string）中讲的现代写法，利用swap函数,注意这里形参，不能传引用，如果传引用，交换后会影响实参，这里传参走拷贝构造给v，出了作用域会销毁，不会影响实参。

2.13 其他几种构造函数

2.13.1vector(int n, const T& value = T())

vector(int n, const T& value = T())
{
	resize(n, value);
}

这里直接调用resize，就可以了，resize里面有扩容，并赋值操作，直接复用就行了。

2.13.2 vector(InputIterator first, InputIterator last)

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	size_t i= 0;
	while(first!=last)
	{
		push_back(*first);
		first++;
	}
}

这是利用迭代器初始化，将frist到last位置，依次尾插到this即可。

 举例：

void test6()
{
	iu::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	iu::vector<int>v2(v1.begin()+2,v1.end());
	for (auto& e : v2)
	{ 
		cout << e << " ";
	}
}

结果：

2.13.3  vector(std::initializer_list<T> it)

vector(std::initializer_list<T> it)
{
	reserve(it.size());
	for (auto e : it)
	{
		push_back(e);
	}
}

首先this开辟和it一样大的元素个数相等的空间大小，再将it中的元素，依次尾插到this中。这个initializer_list类型，可以类似于数组。

 举例：

void test6()
{
	iu::vector<int>v1 = {1,2,3,4,5,6};
	for (auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：

3.迭代器失效问题讨论

3.1插入

看下面这段代码：

int main()
{
	
	std::vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	auto it = v1.begin() + 2;
	// insert以后，默认迭代器都失效了，不要使用
	v1.insert(it, 10);
	cout << *it << endl;
}

结果：

注意这里问题是，空间大小为4，再插入就需要扩容，扩容之后，it还指向原来的位置，但扩容之后，_start位置已经改变，相当于it为野指针，就失效了，但如果不扩容的话，有些编译器可以通过，可能正确，但不能去以编译器为准，就默认insert之后迭代器就失效了，要再用就重新初始化。

3.2 删除

看下面这段代码：（删除所有的偶数）

void test9()
{
	std::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);
	for (const auto& e : v1)
	{
		cout << e <<" ";
	}
	cout << endl;
	auto it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			v1.erase(it);
		}
		else
		{
			++it;
		}
	}
	for (const auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：

这里编译器vs会直接报错，因为在vs下检查非常严格，只要是erase，insert之后编译器直接就失效了，虽然vs下并不会缩容，但也会报错，如果在要缩容的编译器下，那肯定也是失效了，这里需要更新迭代器。

改进后：

void test9()
{
	iu::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);
	for (const auto& e : v1)
	{
		cout << e <<" ";
	}
	cout << endl;
	auto it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			it=v1.erase(it);//每删除一次就更新一次迭代器
		}
		else
		{
			++it;
		}
	}
	for (const auto& e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
}

结果：


http://www.kler.cn/a/515118.html

相关文章：

  • 线性表-线性存储结构
  • 《安富莱嵌入式周报》第349期：VSCode正式支持Matlab调试，DIY录音室级麦克风，开源流体吊坠，物联网在军工领域的应用，Unicode字符压缩解压
  • 澎峰科技计算软件栈与沐曦GPU完成适配和互认证
  • AI 编程工具—Cursor进阶使用 Rules for AI
  • 【深度学习】2.视觉问题与得分函数
  • YOLOv9改进，YOLOv9检测头融合RFAConv卷积，适合目标检测、分割任务
  • Unity入门1
  • iptables和ipvs差异
  • 攻防世界GFSJ1012 pwnstack
  • GaussDB数据库故障定位手段
  • 詳細講一下mobx的在ReactNative中的用法，包含下載，配置。
  • java开发常用指令整理
  • 【jmeter】下载及使用教程【mac】
  • .NET Framework
  • 【Elasticsearch】RestClient操作文档
  • 数据库-多表查询
  • git远程仓库如何修改
  • 简单排序算法
  • MATLAB绘图时线段颜色、数据点形状与颜色等设置，介绍
  • 手机版扫描王导出 PDF、快速文本识别工具扫描纸张
  • 9. 神经网络（一.神经元模型）
  • 5.SQLAlchemy对两张有关联关系表查询
  • IM系统设计
  • 4.JoranConfigurator解析logbak.xml
  • IDEA中将String类型转json格式
  • 学python的第四天：输入（重制版）