C++学习之STL学习：vector的模拟实现

        上节课我们已经接触并学习了vector的使用。接下来我们将通过模拟实现的方式深入学习vector的底层，更好的了解学习vector

vector模拟实现前置准备

vector.h：将类、函数的声明与定义放在一起   

test.cpp：函数的测试

为什么vectror.h要将类和函数的声明与定义放在一起而不是再创建一个.cpp文件呢？

        因为本篇中vector的模拟实现要用到模板，而模板的声明与定义不能放在两个文件里，否则就会编译链接错误（原因后面深入模板学习进行讲解）

        首先抓类的成员变量，然后看构造的初始化，再看核心的成员函数（项目中有很多细节的成员函数）

命名空间的设置

        为了解决与库中vector 使用冲突的问题，我们需要一个命名空间将其封装起来 

namespace Boogiepop
{
    
}

vector的构造

vector 的模拟实现中，我们需要用到模板

template<class T>

     而用到模板的情况下，声明与定义是不能分离的

        成员变量

private:
	iterator _start;//第一个元素的指针
	iterator _finish;//最后一个元素的指针
	iterator _end_of_storage;//分配的内存的最后一个元素的指针

        构造

namespace Boogiepop
{
	//声明与定义不能分别定义在两个文件
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		vector()
			:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{

		}
	private:
		iterator _start;//第一个元素的指针
		iterator _finish;//最后一个元素的指针
		iterator _end_of_storage;//分配的内存的最后一个元素的指针
	};
}

        拷贝构造

//拷贝构造函数
vector(const vector<T>&v)
	:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
	reserve(v.capacity());
	for (auto e : v)
	{
		push_back(e);
	}
}

        析构

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

        强制编辑器构造 

//强制编辑器生成构造
vector()=defalut;

        多个值初始化

花括号对多个数值初始化

//列表初始化构造
vector(initializer_list<T> il)
{
	reserve(il.size());
	for (auto& e : il)
	{
		push_back(e);
	}
}

        函数模板初始化 

//函数模板初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	reserve(last - first);
	for (InputIterator it = first; it!= last; ++it)
	{
		push_back(*it);
	}
}

vector的成员函数

        尾插数据

        尾插数据的时候需要考虑内存分配的空间已经满了。因此我们需要判断是否已经满了并进行扩容

        在此之前我们需要一个更方便的表达方式，类似于string

//返回一个向量有效元素的个数
size_t size() const
{
	return _finish - _start;
}
//返回一个向量分配内存中元素的个数
size_t capacity() const
{
	return _end_of_storage - _start;
}

扩容函数

//扩容
void reserve(size_t n)
{
	size_t old_size = size();
	if (n>capacity())
	{
		T*tmp=new T[n];
		//拷贝旧空间数据
		if (_start!= nullptr)
		{
			memcpy(tmp,_start,sizeof(T)*size());
			delete[]_start;
		}
		_start = tmp;
		_finish = _start + old_size;
		_end_of_storage = _start + n;
	}
}

因此最后尾插数据是这样的

//尾插数据
void push_back(const T& val)
{
	if (_finish == _end_of_storage)
		//空间满了，需要扩容
	{
		resverse(capacity() == 0? 4 : 2 * capacity());
	}
	*_finish = val;
	++_finish;
}

[]遍历

//[]运算符重载
T&operator[](size_t i)
{
	assert(i<size());
	return _start[i];
}

迭代器

typedef T* iterator;
typedef const T* const_iterator;
//迭代器
iterator begin()
{
	return _start;
}
iterator end()
{
	return _finish;
}
//const迭代器
//const不是自身不能修改，而是指向的内容不能修改
const_iterator begin() const
{
	return _start;
}
const_iterator end() const
{
	return _finish;
}

测试：

​void test1()
{
	Boogiepop::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
    //范围for本质上就是迭代器
    for (auto e : v)
    {
	    std::cout<<e<<" ";
    }
    std::cout<<std::endl;
}

​

尾部删除

判定为空函数

//判断为空
bool empty() const
{
	return _finish == _start;
}

完整版

//判断为空
bool empty() const
{
	return _finish == _start;
}
//尾部删除
void pop_back()
{
	/*assert(_finish > _start);*/
	assert(!empty());
	--finish;
}

insert插入

//插入
void insert(iterator pos, const T& val)
{
	assert(pos>=_start && pos<=_finish);
	if (_finish == _end_of_storage)
	{
		size_t len =pos-start();
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	//移动后面的元素
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1)=*end;
		--end;
	}
	*pos = val;
	++_finish;
}

        以上代码有问题，会出现迭代器失效的问题

        插入就会导致扩容，而扩容会导致迭代器失效问题

        如下图所示 ，异地扩容的时候，旧有的空间被销毁，导致指向旧空间的指针指向的内容消失，变成了野指针，因此导致了迭代器失效

        因此要更新pos的位置

//插入
void insert(iterator pos, const T& val)
{
	assert(pos>=_start && pos<=_finish);
	if (_finish == _end_of_storage)
	{
		size_t len =pos-start();
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		//更新pos，pos失效了
		pos = _start + len;
	}
	//移动后面的元素
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1)=*end;
		--end;
	}
	*pos = val;
	++_finish;
}

 再举一个例子

void test4()
{
	Boogiepop::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	print(v);
	int x;
	std::cin >> x;
	auto it = std::find(v.begin(), v.end(), x);
	if(it!= v.end())
	{
		//迭代器失效
		v.insert(it,x*10);
		//C++扩容没有具体固定vector的扩容规则
		//我们认为扩容后it就失效了，所以不能使用it
		//it不能继续使用，已经失效了
		*it = 10;//要更新迭代器位置
	}
	print(v);
}

结果为：

删除

//删除
void erase(iterator pos)
{
	assert(pos>=_start && pos<=_finish);
	iterator it = pos + 1;
	while (it !=_finish)
	{
		*(it - 1) = *(it);
		++it;
	}
	--_finish;
}

test.c

void test6()
{
	std::vector<int> v;
	//Boogiepop::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);
	v.push_back(7);
	v.push_back(8);
	print(v);
	//删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			//erase迭代器也会失效
			//要重新赋新值才可以
			it=v.erase(it);
		}
		else
		{
			++it;
		}
	}
	print(v);
}

 resize

//修改大小
void resize(size_t n,T val=T ())
{//匿名对象的使用场景
	if (n>size())
	{
		reserve(n);
		while (_finish!=_start+n)
		{
			*_finish = val;
			++_finish;
		}
	}
	else
	{
		_finish = _start + n;
	}
}

迭代器失效 

底层就是野指针

C++迭代器失效详解

一、底层原理

迭代器是容器元素的抽象指针，其底层实现与容器内存结构紧密相关：

1. 连续内存容器（vector/string/deque）

   • 迭代器本质是原始指针（或封装指针的类）

   • 内存重新分配时，原内存块被释放，迭代器成为悬垂指针

vector<int> v{1,2,3};
int* p = &v[0];  // 原始指针实现
v.push_back(4);  // 可能导致内存重分配
// p 可能指向已释放内存

        2.节点式容器（list/set/map）

        迭代器是节点指针的封装

        删除节点时，该节点内存被释放，迭代器指向无效内存

list<int> l{1,2,3};
auto it = l.begin();
l.erase(it);  // 节点内存被释放
// it 指向已删除节点

二、失效原因分类

三、典型失效场景分析

1. vector插入导致扩容

   vector<int> v = {1,2,3};
   auto it = v.begin();
   v.push_back(4);  // 容量不足，触发重新分配内存
   *it = 10;       // 未定义行为！it已失效

   2.删除时的迭代器递增错误

   vector<int> v{1,2,3,4};
   for(auto it=v.begin(); it!=v.end(); ++it) {
     if(*it % 2 == 0)
       v.erase(it);  // 错误！erase后it失效，再++导致崩溃
   }

   3.unordered_map的rehash

   unordered_map<int, string> m;
   auto it = m.begin();
   for(int i=0; i<1000; ++i) 
     m[i] = to_string(i);  // 可能触发rehash
   it->second = "test";    // 可能访问失效内存

   四、避免失效的解决方案

更新迭代器法（推荐）

// vector删除示例
for(auto it=v.begin(); it!=v.end(); /* 空 */) {
  if(condition) 
      it = v.erase(it);  // erase返回下一个有效迭代器
  else 
      ++it;
}

// 插入操作
it = v.insert(it, new_value);  // insert返回新元素位置
it += 2;  // 安全移动

索引法（仅随机访问容器） 

vector<int> v{1,2,3,4};
for(size_t i=0; i<v.size(); ) {
  if(v[i] % 2 == 0) {
      v.erase(v.begin() + i);
      // 索引自动更新，无需调整
  } else {
      ++i;
  }
}

 算法组合法（高效安全）

vector<int> v{1,2,3,4};
// 移除-擦除惯用法
v.erase(remove_if(v.begin(), v.end(), 
       [](int x){ return x%2==0; }), 
       v.end());

临时存储法（复杂删除场景）

list<int> l{1,2,3,4};
vector<list<int>::iterator> toErase;

// 先标记要删除的元素
for(auto it=l.begin(); it!=l.end(); ++it)
  if(*it % 2 == 0) 
      toErase.push_back(it);

// 批量删除
for(auto& e : toErase) 
  l.erase(e);

五、特殊容器注意事项

1. deque：

   • 首尾插入通常不使迭代器失效（除非分块变化）

   • 中间插入使所有迭代器失效

     deque<int> d{1,2,3};
     auto it = d.begin() + 1;
     d.push_front(0);  // it可能失效！

     关联容器：

   • 插入永不使迭代器失效

   • 删除仅使被删元素的迭代器失效

     set<int> s{1,2,3};
     auto it = s.find(2);
     s.erase(1);    // 不影响it
     s.insert(4);   // 不影响it
     cout << *it;   // 安全输出2

     unordered容器：

   • rehash 使所有迭代器失效

   • 可通过reserve()预分配桶避免

     unordered_map<int, string> m;
     m.reserve(1000);  // 预分配空间
     auto it = m.begin();
     for(int i=0; i<500; ++i)
       m[i] = "test";  // 不会触发rehash
     it->second = "safe";  // 安全

     六、最佳实践总结

   • 遍历时修改：优先使用it = container.op(it)模式

   • 大规模修改：使用STL算法（remove/copy_if等）

   • 性能敏感场景：

     • vector预分配空间（reserve()）

     • unordered容器预分配桶（reserve()）

   • 长期保存迭代器：

     • 避免在可能修改容器的代码段保存

vector.h

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
namespace Boogiepop
{
	//声明与定义不能分别定义在两个文件
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		//迭代器
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		//const迭代器
		//const不是自身不能修改，而是指向的内容不能修改
		const_iterator begin() const
		{
			return _start;
		}
		const_iterator end() const
		{
			return _finish;
		}
		//构造函数
		vector()
			:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{

		}
		//拷贝构造函数
		vector(const vector<T>&v)
			:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{
			reserve(v.capacity());
			for (auto e : v)
			{
				push_back(e);
			}
		}
		//强制编辑器生成构造
		vector()=defalut;
		//列表初始化构造
		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto& e : il)
			{
				push_back(e);
			}
		}
		//函数模板初始化
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			reserve(last - first);
			for (InputIterator it = first; it!= last; ++it)
			{
				push_back(*it);
			}
		}
		vector(size_t n, const T& val)
		{
			resize(n, val);
		}
		//析构函数
		~vector()
		{
			if (_start!= nullptr)
			{
				delete[]_start;
				_start = nullptr;
				_finish = nullptr;
				_end_of_storage = nullptr;
			}
		}
		//返回一个向量有效元素的个数
		size_t size() const
		{
			return _finish - _start;
		}
		//返回一个向量分配内存中元素的个数
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}
		//扩容
		void reserve(size_t n)
		{
			size_t old_size = size();
			if (n>capacity())
			{
				T*tmp=new T[n];
				//拷贝旧空间数据
				if (_start!= nullptr)
				{
					memcpy(tmp,_start,sizeof(T)*size());
					delete[]_start;
				}
				_start = tmp;
				_finish = _start + old_size;
				_end_of_storage = _start + n;
			}
		}
		//尾插数据
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)
				//空间满了，需要扩容
			{
				reserve(capacity() == 0? 4 : 2 * capacity());
			}
			*_finish = val;
			++_finish;
		}
		//[]运算符重载
		T&operator[](size_t i)
		{
			assert(i<size());
			return _start[i];
		}		
		//判断为空
		bool empty() const
		{
			return _finish == _start;
		}
		//尾部删除
		void pop_back()
		{
			/*assert(_finish > _start);*/
			assert(!empty());
			--_finish;
		}
		//插入
		void insert(iterator pos, const T& val)
		{
			assert(pos>=_start && pos<=_finish);
			if (_finish == _end_of_storage)
			{
				size_t len =pos-_start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				//更新pos，pos失效了
				pos = _start + len;
			}
			//移动后面的元素
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1)=*end;
				--end;
			}
			*pos = val;
			++_finish;
		}
		//删除
		void erase(iterator pos)
		{
			assert(pos>=_start && pos<=_finish);
			iterator it = pos + 1;
			while (it !=_finish)
			{
				*(it - 1) = *(it);
				++it;
			}
			--_finish;
		}
		//修改大小
		void resize(size_t n,T val=T ())
		{//匿名对象的使用场景
			if (n>size())
			{
				reserve(n);
				while (_finish!=_start+n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}
	private:
		iterator _start;//第一个元素的指针
		iterator _finish;//最后一个元素的指针
		iterator _end_of_storage;//分配的内存的最后一个元素的指针
	};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include"vector.h"
//泛型函数模板
template<typename container>
//打印vector
void print(const container& v)
{
	//范围for本质上就是迭代器
	for (auto e : v)
	{
		std::cout << e << " ";
	}
	std::cout << std::endl;
}
void test1()
{
	Boogiepop::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++)
	{
		std::cout<<v[i]<<" ";
	}
	std::cout<<std::endl;
	//范围for本质上就是迭代器
	for (auto e : v)
	{
		std::cout<<e<<" ";
	}
	std::cout<<std::endl;
	print(v);
}
void test2()
{
	Boogiepop::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	print(v);
	v.pop_back();
	v.pop_back();
	print(v);
}
void test3()
{
	Boogiepop::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	print(v);
	v.insert(v.begin()+3, - 2);
	print(v);
}
void test4()
{
	Boogiepop::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	print(v);
	int x;
	std::cin >> x;
	auto it = std::find(v.begin(), v.end(), x);
	if(it!= v.end())
	{
		//迭代器失效
		v.insert(it,x*10);
		//C++扩容没有具体固定vector的扩容规则
		//我们认为扩容后it就失效了，所以不能使用it
		//it不能继续使用，已经失效了
		*it = 10;//要更新迭代器位置
	}
	print(v);
}
void test5()
{
	Boogiepop::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);
	v.push_back(7);
	v.push_back(8);
	print(v);
	v.erase(v.begin()+2);
	v.erase(v.begin()+3);
	print(v);
	int x;
	std::cin >> x;
	auto it = std::find(v.begin(), v.end(), x);
	if (it != v.end())
	{
		//这里的it迭代器不会失效
		v.erase(it);
		*it = 10;
	}
	print(v);
}
void test6()
{
	std::vector<int> v;
	//Boogiepop::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);
	v.push_back(7);
	v.push_back(8);
	print(v);
	//删除所有的偶数
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			//erase迭代器也会失效
			//要重新赋新值才可以
			it=v.erase(it);
		}
		else
		{
			++it;
		}
	}
	print(v);
}
void test7()
{
	Boogiepop::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);
	v.push_back(7);
	v.push_back(8);
	print(v);
	v.resize(10);
	print(v);
	v.resize(13,10);
	print(v);
	//v.resize(20, 19);
}
void test8()
{
	Boogiepop::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	//test6();
	//test7();
	//test8();
	return 0;
}

        今天的内容就到这里了求一个点赞谢谢。

封面图自取：