• C++——vector容器的基本使用和模拟实现

    1、vector的介绍

    1. vector是表示可变大小数组的序列容器。
    2.  就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。
    3.  本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
    4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
    5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增 长。
    6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward_lists统一的迭代器和引用更好。

    注意：string与vector类似，但也有不同之处。string是存放字符的动态数组，vector是存放一个T类型的动态数组，本质都是一个顺序表。并且我们使用vector时需要加头文件#include

     2、vector的常用接口

    构造函数

    1. void test_vector1()
    2. {
    3. 	vector<int> v1;
    4. 	vector<int> v2(10, 8);//开十个空间都赋值8
    5. 	vector<int> v3(++v2.begin(), --v2.end());//用自身的迭代器区间构造
    6. 	vector<int> v4(v3);//拷贝构造
    7.  
    8. 	string s("hello world");
    9. 	vector<char> v5(s.begin(), s.end());//用string的迭代器区间构造
    10. }

    尾插和尾删

    1. vector<int> v;
    2. 	v.push_back(1);
    3. 	v.push_back(2);
    4. 	v.push_back(3);
    5. 	v.push_back(4);
    6.  
    7. 	v.pop_back();
    8. 	v.pop_back();
    9. 	v.pop_back();
    10. 	v.pop_back();

    由于头删和头插效率太低了，vector并没有提供相应的接口。

    遍历和[]访问

    vector可支持[]下标访问，并且可以改变vector中的值，至于遍历，我们可以用下标遍历，也可以使用范围for来遍历。

    1. //遍历
    2. 	for (size_t i = 0; i < v.size(); i++)
    3. 	{
    4. 		v[i] += 1;//可修改
    5. 		cout << v[i] << " ";
    6. 	}
    7. 	cout << endl;
    8.  
    9. 	//
    10. 	vector<int>::iterator it = v.begin();
    11. 	//迭代器 it指向vector的第一个数据
    12. 	while (it != v.end())
    13. 	{
    14. 		*it -= 1;
    15. 		cout << *it << " ";
    16. 		it++;
    17. 	}
    18. 	cout << endl;
    19. 	//范围for 本质也是迭代器
    20. 	for (auto e : v)
    21. 		//把v中的每个数据遍历的时候给给e
    22. 	{
    23. 		cout << e << " ";
    24. 	}
    25. 	cout << endl;
    26.  
    27. 	//int a[] = { 1,2,3 };
    28. 	原生指针就是天然的迭代器，数组支持范围for，会被替换指针
    29. 	//for (int* p = a; p < a + sizeof(a) / sizeof(int); p++)
    30. 	//{}

    reserve和resize的使用

    1.     v.reserve(100);   //扩容并只改变capacity空间
    2. 	v.resize(100);    //扩容不仅改变capacity空间并且改变size
    3. 	v.resize(100, 5); //扩容+初始化 或 删除数据（类比string）
    4. 	v.resize(2);      //截取数据但不改变capacity

    find和assign的使用

    1. vector<int>::iterator ret = find(v.begin(), v.end(), 3);
    2. 	//auto ret = find(v.begin(), v.end(), 3);
    3. 	//如果没找到find返回第二个参数
    4.     //如果找到了返回该数下标
    5.     vector<int> v;
    6. 	v.push_back(1);
    7. 	v.push_back(2);
    8. 	v.push_back(3);
    9. 	v.push_back(4);
    10.  
    11. 	v.assign(10, 5);//给v的前十个值上全部赋值为5，并且会覆盖原来的值

    clear、capacity、size、max_size的使用

    1.  
    2. 	cout <<"max_size:"<< v.max_size() << endl;//数据所能存放的最大容量
    3. 	cout <<"capacity:"<< v.capacity() << endl;//当前容量
    4. 	cout <<"size:"<< v.size() << endl;//当前数据个数
    5.  
    6. 	v.clear();//只清理size的值不改变capacity
    7. 	cout << "-------------------";
    8. 	cout << "max_size:" << v.max_size() << endl;
    9. 	cout << "capacity:" << v.capacity() << endl;
    10. 	cout << "size:" << v.size() << endl;

    insert、erase的使用

    1.     vector<int> v;
    2. 	v.push_back(1);
    3. 	v.push_back(2);
    4. 	v.push_back(3);
    5. 	v.push_back(4);
    6.  
    7. 	//v.assign(10, 5);
    8. 	//覆盖之前已有的值
    9.  
    10. 	vector<int>::iterator ret = find(v.begin(), v.end(), 3);
    11. 	//auto ret = find(v.begin(), v.end(), 3);
    12. 	//如果没找到find返回第二个参数
    13. 	if (ret != v.end())
    14. 	{
    15. 		cout << "找到了" << endl;
    16. 		v.insert(ret, 30);
    17. 		//v.erase(ret);
    18. 		//不能在这删，因为ret失效了
    19. 		//这个迭代器失效问题，我们后面会细讲
    20. 	}
    21. 	v.insert(v.begin(), 30);//在v.begin()的前面插入30也就是头插
    22. 	vector<int>::iterator pos = find(v.begin(), v.end(), 300);
    23. 	if (pos != v.end())
    24. 		//找不到的时候就会返回v.end
    25. 		//因此找不到的时候不会进入
    26. 	{
    27. 		v.erase(pos);//删除pos下标的值
    28. 		
    29. 	}

    增容方式

    1. int main()
    2. {
    3. 	size_t sz;
    4. 	std::vector<int> foo;
    5. 	sz = foo.capacity();
    6. 	std::cout << "making foo trow;\n";
    7. 	for (int i = 0; i < 100; i++)
    8. 	{
    9. 		foo.push_back(i);
    10. 		if (sz != foo.capacity())
    11. 		{
    12. 			sz = foo.capacity();
    13. 			std::cout << "capacity changed:" << sz << '\n';
    14. 		}
    15. 	}
    16. }

     由上图可知vs下vector是以大约1.5增容的。而Linux下g++是以2倍增容的。

    vector相关OJ题

    1、只出现一次的数

    力扣

    1. class Solution {
    2. public:
    3.     int singleNumber(vector<int>& nums) 
    4.     {
    5.         int value=0;
    6.         for(auto e : nums)
    7.         {
    8.             value^=e;//将nums中的值全部互相异或，这样的话相同的数据刚好抵消
    9.         }
    10.         return value;//返回剩下的那个与其他值不相等的数据
    11.  
    12.     }
    13. };

    2、杨辉三角形

    力扣

    1. 杨辉三角形
    2. class Solution {
    3. public:
    4. 	vectorint>> generate(int numRows)
    5. 	{
    6. 		vectorint>> vv;
    7. 		vv.resize(numRows);//先给外层vector开内存
    8. 		for (size_t i = 0; i < numRows; i++)
    9. 		{
    10. 			vv[i].resize(i + 1);//给每一个小vector开内存
    11. 			vv[i][0] = vv[i][vv[i].size() - 1] = 1;//小vector中的头尾设为1
    12. 		}
    13. 		for (size_t i = 0; i < vv.size(); i++)
    14. 		{
    15. 			for (size_t j = 0; j < vv[i].size(); j++)
    16. 			{
    17. 				if (vv[i][j] == 0)
    18. 				{
    19. 					vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
    20. 				}
    21. 			}
    22. 		}
    23. 		return vv;
    24. 	}
    25. };

    3、电话号码的字母组合（重点题，代码中有详细注释）

    1. //回溯力扣题：《电话号码的字母组合》
    2. class Solution {
    3. 	string arr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    4. 	//将0-9(其中0和1不给值)中的每个数字映射一个字符串
    5. public:
    6. 	//最关键的一个函数体，会反复使用
    7. 	void _letterCombinations(const string& digits, size_t i,
    8. 		string combinStr, vector& strV)
    9. 		//传入digits的引用并且加const为了防止改变digits并且减少拷贝，digits就是我们传入的字符串
    10. 		//传入i为了遍历digits中的每个字符串，因为digits字符串的每个字符还代表这一个字符串：例如2->"abc"
    11. 		//combinStr是为了去存放每次递归后的字符串组合
    12. 		//strV为了存放所有情况遍历完全之后的字符串总和
    13. 	{
    14. 		if (i == digits.size())
    15. 			//由于i是从0开始的，倘若此时i已经与digits的长度相等那么说明i已经越界了也代表digits的字符串已经遍历完全了
    16. 		{
    17. 			strV.push_back(combinStr);
    18. 			//将我们组合好的combinStr尾插到strV中，strV也就是最终我们需要返回的那个字符串
    19. 			return;//立即返回，只要执行该语句，该函数将不再执行接下来的语句，因为此时就需要返回
    20. 		}
    21. 		string str = arr[digits[i] - '0'];
    22. 		//定义一个新的字符串str并且让str中存入我们需要遍历的字符串
    23. 		//digits[i]是访问到我们输入字符串中的某个字符
    24. 		//digits-'0'为了得到arr的下标   使其得到digits字符串中每个字符中的字符串
    25. 		//最后让它赋值给str我们就可以遍历str将其进行组合
    26. 		for (size_t j = 0; j < str.size(); j++)//遍历str进行组合，并且继续递归调用_letterCombination函数
    27. 		{
    28. 			_letterCombinations(digits, i + 1, combinStr + str[j], strV);
    29. 			//传入digits   为了继续访问它的字符中的字符串
    30. 			//传入i+1  为了访问digits中的下一个字符中的字符串 并且这样的话i不会发生改变 以便下次可以直接继续使用i+1
    31. 			//传入 combinStr+str[j]  为了将我们得到的str中的字符尾插到combinStr中存放起来，等遍历结束可以尾插到strV中
    32. 			//传入 strV   如果遍历结束可直接把combinStr中的值直接传入strV中
    33. 		}
    34. 	}
    35. 	vector letterCombinations(string digits)
    36. 		//digits是我们所选择的字符串
    37. 	{
    38. 		string combinStr;//定义一个combinStr字符串
    39. 		vector strV;//定义一个vector容器里面的值是string值
    40. 		if (digits.empty())//为了考虑我们的digits为空的情况下
    41. 			return strV;//若为空 直接返回
    42.  
    43. 		//开始递归调用此函数
    44. 		_letterCombinations(digits, 0, combinStr, strV);
    45.  
    46. 		return strV;//递归调用完成后返回
    47. 	}
    48. };

    图解：

    3、vector的模拟实现

    vector的成员变量

    1. private:
    2. 	iterator _start; // 指向数据块的开始
    3. 	iterator _finish; // 指向有效数据的尾
    4. 	iterator _endofStorage; // 指向存储容量的尾

    构造函数

    默认构造

    1. vector()
    2. 			:_start(nullptr)
    3. 			, _finish(nullptr)
    4. 			, _endofstorage(nullptr)
    5. 		{}

    迭代器构造

    1. //一个类模板的成员函数，又可以是一个函数模板
    2. 		template<class InputIterator>
    3. 		vector(InputIterator first, InputIterator last)
    4. 			:_start(nullptr)
    5. 			,_finish(nullptr)
    6. 			,_endofstorage(nullptr)
    7. 		{
    8. 			while (first != last)
    9. 			{
    10. 				push_back(*first);
    11. 				first++;
    12. 			}
    13. 		}

    拷贝构造

    1. //v2(v1)
    2. 		//现代写法
    3. 		vector(const vector& v)
    4. 		{
    5. 			vector tmp(v.begin(),v.end());
    6.             
    7.             //没有模拟swap之前可用下列写法
    8. 			/*swap(_start, tmp._start);
    9. 			swap(_finish, tmp._finish);
    10. 			swap(_endofstorage, tmp._endofstorage);*/
    11.  
    12. 			//this->swap(tmp);
    13. 			swap(tmp);
    14. 		}
    15. v2(v1)传统写法
    16. 		//vector(const vector& v)
    17. 		//	//拷贝构造（深拷贝）
    18. 		//{
    19. 		//	_start = new T[v.capacity()];
    20. 		//	_finish = _start + v.size();
    21. 		//	_endofstorage = _start + v.capacity();
    22.  
    23. 		//  memcpy是浅拷贝
    24. 		//	memcpy(_start, v._start, v.size() * sizeof(T));
    25. 		//}

    这里传统写法不是很推荐，因为会用到memcpy，因为memcpy会用到浅拷贝。

    析构函数

    1. ~vector()
    2. 		{
    3. 			if (_start)
    4. 			{
    5. 				delete[] _start;
    6. 				_start = _finish = _endofstorage = nullptr;
    7. 			}
    8. 		}

    赋值运算符重载函数

    1. //v1=v2
    2. 		//现代写法
    3. 		vector& operator=(vector v)
    4. 		{
    5.  
    6.             //未模拟swap时用下列方法
    7. 			/*swap(_start, v._start);
    8. 			swap(_finish, v._finish);
    9. 			swap(_endofstorage, v._endofstorage);*/
    10.  
    11.  
    12. 			swap(v);
    13.  
    14. 			return *this;
    15. 		}

    迭代器

    1. public:
    2. 		typedef T* iterator;
    3. 		typedef const T* const_iterator;

    begin()和end()

    1.  
    2. 		const_iterator begin() const
    3. 		{
    4. 			return _start;
    5. 		}
    6. 		const_iterator end() const
    7. 		{
    8. 			return _finish;
    9. 		}
    10. 		iterator begin()
    11. 		{
    12. 			return _start;
    13. 		}
    14. 		iterator end()
    15. 		{
    16. 			return _finish;
    17. 		}

    容量函数

    size()和capacity()

    1.  
    2. 		size_t size() const
    3. 		{
    4. 			return _finish - _start;
    5. 		}
    6. 		size_t capacity() const
    7. 		{
    8. 			return _endofstorage - _start;
    9. 		}

    reserve

    1. void reserve(size_t n)
    2. 		{
    3. 			if (n > capacity())
    4. 			{
    5. 				//扩容
    6. 				size_t sz = size();
    7. 				T* tmp = new T[n];
    8. 				if (_start)
    9. 				{
    10. 					//memcpy是浅拷贝
    11. 					//memcpy(tmp, _start, sizeof(T) * size());
    12. 					for (size_t i = 0; i < sz; i++)
    13. 					{
    14. 						//T 是int，一个一个拷贝没问题
    15. 						//T 是string，一个一个拷贝调用是T的深拷贝复制，也没问题
    16. 						tmp[i] = _start[i];
    17. 					}
    18. 					delete[] _start;
    19. 				}
    20. 				_start = tmp;
    21. 				_finish = _start + sz;
    22. 				/*_finish = tmp + size();
    23. 				_start = tmp;*/
    24. 				_endofstorage = _start + n;
    25.  
    26. 			}
    27. 		}

    resize

    1.  
    2. 		void resize(size_t n, const T& val = T())
    3. 		{
    4. 			if (n < size())
    5. 			{
    6. 				_finish = _start + n;
    7. 			}
    8. 			else
    9. 			{
    10. 				if (n > capacity())
    11. 				{
    12. 					reserve(n);
    13. 				}
    14. 				while (_finish != _start + n)
    15. 				{
    16. 					*_finish = val;
    17. 					_finish++;
    18. 				}
    19. 			}
    20. 		}

    empty

    1. bool empty()const
    2. {
    3. 	return _start == _finish;
    4. }

    增删查改

    push_back

    1. void push_back(const T& x)
    2. 		{
    3. 			if (_finish == _endofstorage)
    4. 			{
    5. 				扩容
    6. 				//size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    7. 				size_t sz = size();
    8. 				//T* tmp = new T[newCapacity];
    9. 				//if (_start)
    10. 				//{
    11. 				//	memcpy(tmp, _start, sizeof(T) * size());
    12. 				//	delete[] _start;
    13. 				//}
    14. 				_start = tmp;
    15. 				_finish = _start + sz;
    16. 				//_finish = tmp + size();
    17. 				//_start = tmp;
    18. 				//_endofstorage = _start + newCapacity;
    19.  
    20. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    21. 			} 
    22. 			*_finish = x;
    23. 			_finish++;
    24. 		}

    pop_back

    1. void pop_back()
    2. 		{
    3. 			assert(_finish > _start);//检查是否为空
    4.  
    5. 			_finish--;
    6. 		}

    insert

    1. iterator insert(iterator pos, const T& x)
    2. 		{
    3. 			assert(pos >= _start);
    4. 			assert(pos <= _finish);
    5. 			//满了就扩容
    6. 			if (_finish == _endofstorage)
    7. 			{
    8. 				//扩容
    9. 				//扩容会导致pos失效，扩容需要更新一下pos
    10. 				size_t len = pos - _start;//计算一下扩容前pos与_start直接的距离以便以计算新pos
    11. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    12. 				pos = _start + len;//得到新pos的位置
    13. 			}
    14.  
    15. 			//移动数据
    16. 			iterator end = _finish - 1;
    17. 			while (end >= pos)
    18. 			{
    19. 				*(end + 1) = *end;
    20. 				end--;
    21. 			}
    22. 			*pos = x;
    23. 			_finish++;
    24.  
    25. 			return pos;
    26. 		}

    earse

    1.  
    2. 		iterator erase(iterator pos)
    3. 		{
    4. 			assert(pos >= _start);
    5. 			assert(pos <= _finish);
    6.  
    7. 			iterator begin = pos + 1;
    8. 			while (begin < _finish)
    9. 			{
    10. 				*(begin - 1) = *begin;
    11. 				begin++;
    12. 			}
    13. 			_finish--;
    14. 			return pos;
    15. 		}

    swap

    1. void swap(vector& v)
    2. 		{
    3. 			std::swap(_start, v._start);
    4. 			std::swap(_finish, v._finish);
    5. 			std::swap(_endofstorage, v._endofstorage);
    6. 		}

    下标访问

    1. T& operator[](size_t i)
    2. 		{
    3. 			assert(i < size());
    4. 			return _start[i];
    5. 		}

    完整代码

    1. #pragma once
    2.  
    3. namespace mwb
    4. {
    5. 	template<class T>
    6. 	class vector
    7. 	{
    8. 	public:
    9. 		typedef T* iterator;
    10. 		typedef const T* const_iterator;
    11. 		
    12. 		vector()
    13. 			:_start(nullptr)
    14. 			, _finish(nullptr)
    15. 			, _endofstorage(nullptr)
    16. 		{}
    17.  
    18. 		// v2(v1)传统写法
    19. 		//vector(const vector& v)
    20. 		//	//拷贝构造（深拷贝）
    21. 		//{
    22. 		//	_start = new T[v.capacity()];
    23. 		//	_finish = _start + v.size();
    24. 		//	_endofstorage = _start + v.capacity();
    25.  
    26. 		//  memcpy是浅拷贝
    27. 		//	memcpy(_start, v._start, v.size() * sizeof(T));
    28. 		//}
    29. 		
    30. 		//一个类模板的成员函数，又可以是一个函数模板
    31. 		template<class InputIterator>
    32. 		vector(InputIterator first, InputIterator last)
    33. 			:_start(nullptr)
    34. 			,_finish(nullptr)
    35. 			,_endofstorage(nullptr)
    36. 		{
    37. 			while (first != last)
    38. 			{
    39. 				push_back(*first);
    40. 				first++;
    41. 			}
    42. 		}
    43. 		void swap(vector& v)
    44. 		{
    45. 			std::swap(_start, v._start);
    46. 			std::swap(_finish, v._finish);
    47. 			std::swap(_endofstorage, v._endofstorage);
    48. 		}
    49. 		//v2(v1)
    50. 		//现代写法
    51. 		vector(const vector& v)
    52. 		{
    53. 			vector tmp(v.begin(),v.end());
    54. 			/*swap(_start, tmp._start);
    55. 			swap(_finish, tmp._finish);
    56. 			swap(_endofstorage, tmp._endofstorage);*/
    57. 			//this->swap(tmp);
    58. 			swap(tmp);
    59. 		}
    60. 		//v1=v2
    61. 		//现代写法
    62. 		vector& operator=(vector v)
    63. 		{
    64. 			/*swap(_start, v._start);
    65. 			swap(_finish, v._finish);
    66. 			swap(_endofstorage, v._endofstorage);*/
    67. 			swap(v);
    68.  
    69. 			return *this;
    70. 		}
    71. 		~vector()
    72. 		{
    73. 			if (_start)
    74. 			{
    75. 				delete[] _start;
    76. 				_start = _finish = _endofstorage = nullptr;
    77. 			}
    78. 		}
    79. 		const_iterator begin() const
    80. 		{
    81. 			return _start;
    82. 		}
    83. 		const_iterator end() const
    84. 		{
    85. 			return _finish;
    86. 		}
    87. 		iterator begin()
    88. 		{
    89. 			return _start;
    90. 		}
    91. 		iterator end()
    92. 		{
    93. 			return _finish;
    94. 		}
    95. 		T& operator[](size_t i)
    96. 		{
    97. 			assert(i < size());
    98. 			return _start[i];
    99. 		}
    100. 		size_t size() const
    101. 		{
    102. 			return _finish - _start;
    103. 		}
    104. 		size_t capacity() const
    105. 		{
    106. 			return _endofstorage - _start;
    107. 		}
    108.  
    109. 		void reserve(size_t n)
    110. 		{
    111. 			if (n > capacity())
    112. 			{
    113. 				//扩容
    114. 				size_t sz = size();
    115. 				T* tmp = new T[n];
    116. 				if (_start)
    117. 				{
    118. 					//memcpy是浅拷贝
    119. 					//memcpy(tmp, _start, sizeof(T) * size());
    120. 					for (size_t i = 0; i < sz; i++)
    121. 					{
    122. 						//T 是int，一个一个拷贝没问题
    123. 						//T 是string，一个一个拷贝调用是T的深拷贝复制，也没问题
    124. 						tmp[i] = _start[i];
    125. 					}
    126. 					delete[] _start;
    127. 				}
    128. 				_start = tmp;
    129. 				_finish = _start + sz;
    130. 				/*_finish = tmp + size();
    131. 				_start = tmp;*/
    132. 				_endofstorage = _start + n;
    133.  
    134. 			}
    135. 		}
    136. 		void resize(size_t n, const T& val = T())
    137. 		{
    138. 			if (n < size())
    139. 			{
    140. 				_finish = _start + n;
    141. 			}
    142. 			else
    143. 			{
    144. 				if (n > capacity())
    145. 				{
    146. 					reserve(n);
    147. 				}
    148. 				while (_finish != _start + n)
    149. 				{
    150. 					*_finish = val;
    151. 					_finish++;
    152. 				}
    153. 			}
    154. 		}
    155. 		iterator insert(iterator pos, const T& x)
    156. 		{
    157. 			assert(pos >= _start);
    158. 			assert(pos <= _finish);
    159. 			//满了就扩容
    160. 			if (_finish == _endofstorage)
    161. 			{
    162. 				//扩容
    163. 				//扩容会导致pos失效，扩容需要更新一下pos
    164. 				size_t len = pos - _start;//计算一下扩容前pos与_start直接的距离以便以计算新pos
    165. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    166. 				pos = _start + len;//得到新pos的位置
    167. 			}
    168.  
    169. 			//移动数据
    170. 			iterator end = _finish - 1;
    171. 			while (end >= pos)
    172. 			{
    173. 				*(end + 1) = *end;
    174. 				end--;
    175. 			}
    176. 			*pos = x;
    177. 			_finish++;
    178.  
    179. 			return pos;
    180. 		}
    181. 		iterator erase(iterator pos)
    182. 		{
    183. 			assert(pos >= _start);
    184. 			assert(pos <= _finish);
    185.  
    186. 			iterator begin = pos + 1;
    187. 			while (begin < _finish)
    188. 			{
    189. 				*(begin - 1) = *begin;
    190. 				begin++;
    191. 			}
    192. 			_finish--;
    193. 			return pos;
    194. 		}
    195. 		void push_back(const T& x)
    196. 		{
    197. 			if (_finish == _endofstorage)
    198. 			{
    199. 				扩容
    200. 				//size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    201. 				size_t sz = size();
    202. 				//T* tmp = new T[newCapacity];
    203. 				//if (_start)
    204. 				//{
    205. 				//	memcpy(tmp, _start, sizeof(T) * size());
    206. 				//	delete[] _start;
    207. 				//}
    208. 				_start = tmp;
    209. 				_finish = _start + sz;
    210. 				//_finish = tmp + size();
    211. 				//_start = tmp;
    212. 				//_endofstorage = _start + newCapacity;
    213.  
    214. 				reserve(capacity() == 0 ? 4 : capacity() * 2);
    215. 			} 
    216. 			*_finish = x;
    217. 			_finish++;
    218. 		}
    219. 		void pop_back()
    220. 		{
    221. 			assert(_finish > _start);//检查是否为空
    222.  
    223. 			_finish--;
    224. 		}
    225. 	private:
    226. 		iterator _start;
    227. 		iterator _finish;
    228. 		iterator _endofstorage;
    229. 	};
    230. }

  • 相关阅读:
    Java 中的集合框架有哪些主要接口？ArrayList 和 LinkedList 在使用场景上的不同是什么？
    java8-Stream流常用API
    webpack 中 require.context() 的用法
    C++ Reference: Standard C++ Library reference: Containers: deque: deque: back
    【BurpSuite】插件学习之dotnet-Beautifier
    解析全闪对象存储
    【JavaEE进阶系列 | 从小白到工程师】正则表达式的语法&使用
    vue父子组件间数据的双向绑定
    看完这篇 教你玩转ATT&CK红队评估实战靶场Vulnstack（三）
    使用JPA和Hibernate查询分页
  • 原文地址：https://blog.csdn.net/m0_57249790/article/details/127591533