【C++】STL——vector

用户11290673

发布于 2024-09-25 13:14:12

330

发布于 2024-09-25 13:14:12

文章被收录于专栏：学习

前言本篇博客继续介绍STL库里一个结构——vector,它是个顺序储存的容器，不仅可以包含字符串，还可以有其他类型，让我们一起来详细看一下它 💓 个人主页：小张同学zkf ⏩ 文章专栏：C++ 若有问题评论区见📝 🎉欢迎大家点赞👍收藏⭐文章

1.vector的介绍

vector介绍：vector

vector的定义

2.vector的使用

2.1vector iterator 的使用

2.2vector空间增长问题

capacity 的代码在 vs 和 g++ 下分别运行会发现， vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的 。这个问题经常会考察，不要固化的认为， vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的。 vs 是 PJ 版本 STL ， g++ 是 SGI 版本 STL 。 reserve 只负责开辟空间，如果确定知道需要用多少空间， reserve 可以缓解 vector 增容的代价缺陷问题。 resize 在开空间的同时还会进行初始化，影响 size。

2.3vector增删查改

2.4vector迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对

指针进行了封装 ，比如： vector 的迭代器就是原生态指针 T* 。因此 迭代器失效，实际就是迭代器

底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间 ，造成的后果是程序崩溃 ( 即

如果继续使用已经失效的迭代器，程序可能会崩溃 ) 。

对于 vector 可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、

assign 、 push_back 等。

#include <iostream> using namespace std ; #include <vector> int main () { vector < int > v { 1 , 2 , 3 , 4 , 5 , 6 }; auto it = v . begin (); // 将有效元素个数增加到 100 个，多出的位置使用 8 填充，操作期间底层会扩容 // v.resize(100, 8); // reserve 的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变 // v.reserve(100); // 插入元素期间，可能会引起扩容，而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 给 vector 重新赋值，可能会引起底层容量改变 v . assign ( 100 , 8 ); /* 出错原因：以上操作，都有可能会导致 vector 扩容，也就是说 vector 底层原理旧空间被释放掉，而在打印时， it 还使用的是释放之间的旧空间，在对 it 迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作 vector 中的元素，只需给 it 重新赋值即可。 */ while ( it != v . end ()) { cout << * it << " " ; ++ it ; } cout << endl ; return 0 ; }

2. 指定位置元素的删除操作--erase

#include <iostream> using namespace std ; #include <vector> int main () { int a [] = { 1 , 2 , 3 , 4 }; vector < int > v ( a , a + sizeof ( a ) / sizeof ( int )); // 使用 find 查找 3 所在位置的 iterator vector < int > :: iterator pos = find ( v . begin (), v . end (), 3 ); // 删除 pos 位置的数据，导致 pos 迭代器失效。 v . erase ( pos ); cout << * pos << endl ; // 此处会导致非法访问 return 0 ; }

erase 删除 pos 位置元素后， pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理

论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end

的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素

时， vs 就认为该位置迭代器失效了。

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

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

3.1vector核心接口模拟实现代码

#include <assert.h>
#include <iostream>
using namespace std;
namespace zkf
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()
		{
		}
		size_t size()const
		{
			return _finish - _start;
		}
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator begin()const
		{
			return _start;
		}
		const_iterator end()const
		{
			return _finish;
		}
		bool empty()
		{
			return _start == _finish;
		}

		void reserve(const size_t n)
		{
			if (n > capacity())
			{
				size_t old_size = size();
				T* tmp = new T[n];
				for (size_t i = 0; i < size(); i++)
				{
					tmp[i] = _start[i];
				}
				delete[]_start;
				_start = tmp;
				_finish = tmp + old_size;
				_end_of_storage = tmp + n;
			}
		}
		void push_back(const T& x)
		{
			// 扩容
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;
			++_finish;
		}
		void pop_back()
		{
			assert(!empty());
			--_finish;
		}
		T& operator[](size_t i)
		{
			assert(i < size());

			return _start[i];
		}

		const T& operator[](size_t i) const
		{
			assert(i < size());

			return _start[i];
		}
		vector(const vector<T>& s)
		{
			reserve(s.size());
			for (auto& e : s)
			{
				push_back(e);
			}
		}
		vector(size_t n, const T& m = T())
		{
			for (size_t i = 0; i < n; i++)
			{
				push_back(m);
			}
		}
		vector(int n, const T& m = T())
		{
			for (int i = 0; i < n; i++)
			{
				push_back(m);
			}
		}
		template <class inputinerator>
		vector(inputinerator s1, inputinerator s2)
		{
			while (s1 != s2)
			{
				push_back(*s1);
				s1++;
			}
		}
		void swap(vector<T>& s)
		{
			std::swap(_start, s._start);
			std::swap(_finish, s._finish);
			std::swap(_end_of_storage, s._end_of_storage);
		}
		vector<T>& operator=(vector<T> s)
		{
			swap(s);
			return *this;
		}
		void clear()
		{
			_finish = _start;
		}
		iterator insert(iterator pos,const T& s)
		{
			assert(_start <= pos);
			assert(_finish>pos);
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			iterator it = _finish -1;
			while (it >= pos)
			{
				*(it+1) = *it;
				it--;
			}
			*pos = s;
			++_finish;
			return pos;
		}
		void erase(iterator pos)
		{
			assert(_start <= pos);
			assert(_finish > pos);
			iterator it = pos+1;
			while (it != end())
			{
				*(it-1) = *it;
				it++;
			}
			_finish--;
		}
		void resize(size_t n,  T s = T())
		{
			reserve(n);
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				while (_finish != _start + n)
				{
					*_finish = s;
					_finish++;
				}
			}
		}
		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
	template<class T>
	void print_vector(const vector<T>& s)
	{
		auto as = s.begin();
		while (as != s.end())
		{
			cout << *as <<" ";
			as++;
		}
		cout << endl;
	}
	
}