devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ vector类_c++ vector 构造

作者：繁依Fanyi0 | 2024-04-19 16:29:06

赞

踩

c++ vector 构造

目录

一.vector使用

1.vector构造

2.vector迭代器使用

3.vector容量操作

4.vector增删查改

二.vector迭代器失效问题

三.memcpy拷贝问题

四.vector分部模拟实现

1.私有成员

2.typedef

3.3种构造函数

4.拷贝构造、赋值运算符重载函数

5.析构函数

6.迭代器

7.大小、容量

8.reserve函数

9.resize函数

10.尾插、尾删函数

11.下标运算符重载函数

12.插入函数

13.删除函数

14.清理函数 

五.vector类模拟实现总代码

前言：vector类的学习，可以模仿string，并且有很多地方都与string类类似，因此在这里的相关说明就会比较简洁一些。

一.vector使用

在使用之前我们先介绍一下vector：

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

介绍OK，开始使用vector。

1.vector构造

① vector()        无参构造

② vector(size_t n, const value_type& val = value_type())        构造并初始化n个val

③ vector(const vector& x)        拷贝构造

④ vector(InputIterator first, InputIterator last)        使用迭代器进行初始化构造

  1. vector<string> v1;
  2.  
  3. vector<int> v2(10, 5);
  4.  
  5. vector<int> v3(v2);
  6.  
  7. vector<int> v4(++v2.begin(), --v2.end());
  8.  
  9. string s = "hello world";
  10. vector<char> v5(s.begin(), s.end());

2.vector迭代器使用

① begin + end        正向

② rbegin + rend        反向

③ iterator        正向迭代器

④ reverse_iterator        反向迭代器

⑤ const_iterator        常量迭代器

⑥ const_reverse_iterator        常量反向迭代器

  1. // 正向遍历
  2. vector<int>::iterator it = v.begin();
  3. while (it != v.end())
  4. {
  5. 	*it -= 1;
  6. 	cout << *it << " ";
  7. 	++it;
  8. }
  9. cout << endl;
  10.  
  11. // 反向遍历
  12. vector<int>::reverse_iterator rit = v.rbegin();
  13. while (rit != v.rend())
  14. {
  15. 	*rit -= 1;
  16. 	cout << *rit << " ";
  17. 	++rit;
  18. }
  19. cout << endl;
  20.  
  21.  
  22. // const迭代器
  23. vector<int>::const_iterator it = v.begin();
  24. while (it != v.end())
  25. {
  26. 	*it -= 1;
  27. 	cout << *it << " ";
  28. 	++it;
  29. }
  30. cout << endl;

3.vector容量操作

① size()        获取数据个数

② capacity()        获取容量大小

③ empty()        判断是否为空

④ resize()        改变vector的size

⑤ reserve()        改变vector的capacity

  1. void test_vector()
  2. {
  3. 	//vector<char> v;
  4. 	//cout << v.max_size() << endl;
  5. 	size_t sz;
  6. 	std::vector<int> foo;
  7. 	foo.reserve(100);
  8. 	//foo.resize(100);
  9. 	sz = foo.capacity();
  10. 	std::cout << "making foo grow:\n";
  11. 	for (int i = 0; i < 100; ++i) {
  12. 		foo.push_back(i);
  13. 		if (sz != foo.capacity()) {
  14. 			sz = foo.capacity();
  15. 			std::cout << "capacity changed: " << sz << '\n';
  16. 		}
  17. 	}
  18.  
  19. 	//vector<int> countV;
  20. 	//countV.resize(100, 1);
  21. 	//countV.resize(10);
  22.  
  23. 	// string vector等都有一个特点，删除数据，一般是不会主动缩容
  24. 	foo.resize(10);
  25. 	cout << foo.size() << endl;
  26. 	cout << foo.capacity() << endl;
  27. }

4.vector增删查改

① push_back()        尾插

② pop_back()        尾删

③ find        查找（位于算法algorithm中）

④ insert        在pos之前插入

⑤ erase        删除pos位置

⑥ swap        交换

⑦ operator[]        让vector像数组一样被访问

  1. void test_vector1()
  2. {
  3. 	// 遍历
  4. 	vector<int> v;
  5. 	v.push_back(1);
  6. 	v.push_back(2);
  7. 	v.push_back(3);
  8. 	v.push_back(4);
  9.  
  10. 	v.insert(v.begin(), -1);
  11. 	v.insert(v.begin(), -2);
  12. 	v.insert(v.begin(), -3);
  13.  
  14. 	for (auto e : v)
  15. 	{
  16. 		cout << e << " ";
  17. 	}
  18. 	cout << endl;
  19.  
  20. 	v.insert(v.begin() + 7, 300);
  21. 	//v.insert(v.begin()+8, 300);
  22.  
  23. 	for (auto e : v)
  24. 	{
  25. 		cout << e << " ";
  26. 	}
  27. 	cout << endl;
  28. 	v.erase(v.begin());
  29. 	v.erase(v.begin());
  30.  
  31. 	for (auto e : v)
  32. 	{
  33. 		cout << e << " ";
  34. 	}
  35. 	cout << endl;
  36. }
  37.  
  38. void test_vector2()
  39. {
  40. 	// 遍历
  41. 	vector<int> v;
  42. 	v.push_back(1);
  43. 	v.push_back(2);
  44. 	v.push_back(3);
  45. 	v.push_back(4);
  46.  
  47. 	//vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  48. 	auto pos = find(v.begin(), v.end(), 3);
  49. 	if (pos != v.end())
  50. 	{
  51. 		cout << "找到了" << endl;
  52. 		v.erase(pos);
  53. 	}
  54. 	else
  55. 	{
  56. 		cout << "没有找到" << endl;
  57. 	}
  58.  
  59. 	for (auto e : v)
  60. 	{
  61. 		cout << e << " ";
  62. 	}
  63. 	cout << endl;
  64.  
  65. 	v.push_back(0);
  66. 	v.push_back(9);
  67. 	v.push_back(3);
  68. 	v.push_back(1);
  69.  
  70. 	// 默认是升序
  71. 	//sort(v.begin(), v.end());   // <
  72.  
  73. 	// 排降序，仿函数
  74. 	// sort(v.begin(), v.end(), greater<int>());  // >
  75.  
  76. 	greater<int> g;
  77. 	sort(v.begin(), v.end(), g);  // >
  78.  
  79.  
  80. 	for (auto e : v)
  81. 	{
  82. 		cout << e << " ";
  83. 	}
  84. 	cout << endl;
  85. }

二.vector迭代器失效问题

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

        因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果可能是程序崩溃。

        迭代器失效一共有两种：①野指针  ②意义变了

这里主要通过insert和erase来演示迭代器失效的问题：

 （1）insert

①野指针：

  1. void reserve(size_t n)
  2. {
  3. 	size_t sz = size();
  4. 	if (n > capacity())
  5. 	{
  6. 		T* tmp = new T[n];
  7. 		if (_start)
  8. 		{
  9. 			for (size_t i = 0; i < size(); ++i)
  10. 			{
  11. 				tmp[i] = _start[i];
  12. 			}
  13. 			delete _start;
  14. 		}
  15.  
  16. 		_start = tmp;
  17.  
  18. 	}
  19.  
  20. 	_finish = _start + sz;
  21. 	_endofstorage = _start + n;
  22. }
  23.  
  24. iterator insert(iterator pos, const T& x)
  25. {
  26. 	assert(pos >= _start && pos <= _finish);
  27.  
  28. 	// 扩容
  29. 	if (_finish == _endofstorage)
  30. 	{
  31. 		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  32. 		reserve(newCapacity);
  33. 	}
  34.  
  35. 	// 挪动数据
  36. 	iterator end = _finish - 1;
  37. 	while (end >= pos)
  38. 	{
  39. 		*(end + 1) = *end;
  40. 		--end;
  41. 	}
  42.  
  43. 	*pos = x;
  44. 	++_finish;
  45.  
  46. 	return pos;
  47.  
  48. }

         这是一个正常实现的insert函数，但是这里如果测试时如果发生扩容就会发现报错，原因是pos在发生扩容时，因为扩容的过程中是创建了一个临时tmp数组并开辟了扩容后的空间，将原数组拷贝tmp后将原数组给delete掉，这时再重新把tmp拷贝给_start数组。

        这时的_start的地址已经不是原来的地址了，已经有了新的地址。这时，pos所指向的位置就不再是一个有效的空间了，就出现了野指针的问题。

        修改方式：

  1. void reserve(size_t n)
  2. {
  3. 	size_t sz = size();
  4. 	if (n > capacity())
  5. 	{
  6. 		T* tmp = new T[n];
  7. 		if (_start)
  8. 		{
  9. 			for (size_t i = 0; i < size(); ++i)
  10. 			{
  11. 				tmp[i] = _start[i];
  12. 			}
  13. 			delete _start;
  14. 		}
  15.  
  16. 		_start = tmp;
  17.  
  18. 	}
  19.  
  20. 	_finish = _start + sz;
  21. 	_endofstorage = _start + n;
  22. }
  23.  
  24. iterator insert(iterator pos, const T& x)
  25. {
  26. 	assert(pos >= _start && pos <= _finish);
  27.  
  28. 	// 扩容
  29. 	if (_finish == _endofstorage)
  30. 	{
  31.         size_t n = pos - _start;
  32.  
  33. 		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  34. 		reserve(newCapacity);
  35.  
  36.         pos = _start + n;
  37. 	}
  38.  
  39. 	// 挪动数据
  40. 	iterator end = _finish - 1;
  41. 	while (end >= pos)
  42. 	{
  43. 		*(end + 1) = *end;
  44. 		--end;
  45. 	}
  46.  
  47. 	*pos = x;
  48. 	++_finish;
  49.  
  50. 	return pos;
  51.  
  52. }

         这里通过n来保存原来pos和_start间的距离，然后在_start更新地址后，也更新pos的指向位置，就可以避免野指针的问题。

②意义变了：

        实现了该insert函数之后，我们想要在一个数组中的偶数前加上20，按照原遍历方式：

  1. void test_vector()
  2. {
  3. 	// 在所有的偶数的前面插入20
  4. 	vector<int> v;
  5. 	//v.reserve(10);
  6. 	v.push_back(1);
  7. 	v.push_back(2);
  8. 	v.push_back(3);
  9. 	v.push_back(4);
  10. 	v.push_back(5);
  11. 	v.push_back(6);
  12.  
  13. 	vector<int>::iterator it = v.begin();
  14. 	while (it != v.end())
  15. 	{
  16. 		if (*it % 2 == 0)
  17. 		{
  18. 			it = v.insert(it, 20);
  19. 		}
  20.  
  21.         ++it;
  22. 	}
  23.  
  24. 	for (auto e : v)
  25. 	{
  26. 		cout << e << " ";
  27. 	}
  28. 	cout << endl;
  29. }

        这里在*it为2时，会插入20，插入结束之后，it就变为刚插入的20，这时再++it，那么*it又为2了，就会导致死循环，这就是迭代器的意义变了。

        修改方式：

  1. void test_vector()
  2. {
  3. 	// 在所有的偶数的前面插入20
  4. 	vector<int> v;
  5. 	//v.reserve(10);
  6. 	v.push_back(1);
  7. 	v.push_back(2);
  8. 	v.push_back(3);
  9. 	v.push_back(4);
  10. 	v.push_back(5);
  11. 	v.push_back(6);
  12.  
  13. 	vector<int>::iterator it = v.begin();
  14. 	while (it != v.end())
  15. 	{
  16. 		if (*it % 2 == 0)
  17. 		{
  18. 			it = v.insert(it, 20);
  19.             ++it;
  20. 		}
  21.  
  22.         ++it;
  23. 	}
  24.  
  25. 	for (auto e : v)
  26. 	{
  27. 		cout << e << " ";
  28. 	}
  29. 	cout << endl;
  30. }

        在插入之后多进行一次++it，就可以让it会到它原来的位置处，就可以避免因意义变了导致的迭代器失效问题。

（2）erase

  1. iterator erase(iterator pos)
  2. {
  3. 	assert(pos >= _start && pos <= _finish);
  4.  
  5. 	iterator it = pos + 1;
  6. 	while (it != _finish)
  7. 	{
  8. 		*(it - 1) = *it;
  9. 		++it;
  10. 	}
  11.  
  12. 	--_finish;
  13.  
  14. 	return pos;
  15. }
  16.  
  17. void test_vector()
  18. {
  19. 	vector<int> v;
  20. 	//v.reserve(10);
  21. 	v.push_back(1);
  22. 	v.push_back(2);
  23. 	v.push_back(2);
  24. 	v.push_back(2);
  25. 	v.push_back(3);
  26. 	v.push_back(4);
  27. 	v.push_back(4);
  28. 	v.push_back(5);
  29. 	cout << v.size() << ":" << v.capacity() << endl;
  30. 	auto pos = find(v.begin(), v.end(), 4);
  31. 	if (pos != v.end())
  32. 	{
  33. 		v.erase(pos);
  34. 	}
  35.  
  36. 	cout << *pos << endl;
  37. 	*pos = 10;
  38. 	cout << *pos << endl << endl;
  39.  
  40. 	cout << v.size() << ":" << v.capacity() << endl;
  41.  
  42. 	for (auto e : v)
  43. 	{
  44. 		cout << e << " ";
  45. 	}
  46. 	cout << endl;
  47. }

        这里在删除掉了4之后，pos的意义就变了，这里的pos就是原来pos的下一个元素了。

        因此迭代器失效了。

  1. void test_vector8()
  2. {
  3. 	std::vector<int> v;
  4. 	v.push_back(1);
  5. 	v.push_back(2);
  6. 	v.push_back(2);
  7. 	v.push_back(2);
  8. 	v.push_back(3);
  9. 	v.push_back(4);
  10. 	v.push_back(4);
  11. 	v.push_back(4);
  12. 	v.push_back(5);
  13.  
  14.  
  15. 	auto it = v.begin();
  16. 	while (it != v.end())
  17. 	{
  18. 		if (*it % 2 == 0)
  19. 		{
  20. 			it = v.erase(it);
  21. 		}
  22.  
  23. 		++it;
  24. 	}
  25.  
  26. 	for (auto e : v)
  27. 	{
  28. 		cout << e << " ";
  29. 	}
  30. 	cout << endl;
  31. }

        这里我们想要删除偶数的数据，按照原来的方法进行，但是这里在删除掉一个偶数时，it就已经变为下一个元素了，而这时再次++，就会导致it的意义变了。

        修改方式：

  1. void test_vector8()
  2. {
  3. 	std::vector<int> v;
  4. 	v.push_back(1);
  5. 	v.push_back(2);
  6. 	v.push_back(2);
  7. 	v.push_back(2);
  8. 	v.push_back(3);
  9. 	v.push_back(4);
  10. 	v.push_back(4);
  11. 	v.push_back(4);
  12. 	v.push_back(5);
  13.  
  14.  
  15. 	auto it = v.begin();
  16. 	while (it != v.end())
  17. 	{
  18. 		if (*it % 2 == 0)
  19. 		{
  20. 			it = v.erase(it);
  21. 		}
  22. 		else
  23. 		{
  24. 			++it;
  25. 		}
  26. 	}
  27.  
  28. 	for (auto e : v)
  29. 	{
  30. 		cout << e << " ";
  31. 	}
  32. 	cout << endl;
  33. }

        删除的时候，就不进行++，而不删除的时候再++，就可以避免这一种意义变了的迭代器失效问题。 

三.memcpy拷贝问题

        memcpy是将一段内存空间的内容拷贝到另一段内存空间中，地址不会发生变化，是浅拷贝。

  1. void reserve(size_t n)
  2. {
  3. 	size_t sz = size();
  4. 	if (n > capacity())
  5. 	{
  6. 		T* tmp = new T[n];
  7. 		if (_start)
  8. 		{
  9. 			// memcpy(tmp, _start, size() * sizeof(T));
  10. 			for (size_t i = 0; i < size(); ++i)
  11. 			{
  12. 				tmp[i] = _start[i];
  13. 			}
  14. 			delete _start;
  15. 		}
  16.  
  17. 		_start = tmp;
  18.  
  19. 	}
  20.  
  21. 	_finish = _start + sz;
  22. 	_endofstorage = _start + n;
  23. }

        那么如果在reserve中使用memcpy，那么就会出现浅拷贝的统一问题，拷贝之后因为地址相同，在delete时，delete掉其中的一个之后，另一个随之失效，这时就会出现野指针的问题。

        当然，出现这种问题的情况是当拷贝的是自定义类型时，例如vector<string>，或是vector<vector<int>>，都会出现这种情况，因此为了避免这种情况，应该使用深拷贝。

        修改如下：

  1. void reserve(size_t n)
  2. {
  3. 	size_t sz = size();
  4. 	if (n > capacity())
  5. 	{
  6. 		T* tmp = new T[n];
  7. 		if (_start)
  8. 		{
  9. 			for (size_t i = 0; i < size(); ++i)
  10. 			{
  11. 				tmp[i] = _start[i];
  12. 			}
  13. 			delete _start;
  14. 		}
  15.  
  16. 		_start = tmp;
  17. 	}
  18.  
  19. 	_finish = _start + sz;
  20. 	_endofstorage = _start + n;
  21. }

四.vector分部模拟实现

        这里的vector的模拟实现有很多与string的模拟实现类似，就不再详细说明了。 

1.私有成员

        _start为vector头，_finish为size大小位置，_ebdifstorage为capacity容量位置。

  1. private:
  2. 	iterator _start;
  3. 	iterator _finish;
  4. 	iterator _endofstorage;

2.typedef

        vector中的iterator就是T*。

  1. typedef T* iterator;
  2. typedef const T* const_iterator;

3.3种构造函数

（1）无参构造函数

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

（2）迭代器区间构造函数

  1. template <class InputIterator>
  2. vector(InputIterator first, InputIterator last)
  3. 	: _start(nullptr)
  4. 	, _finish(nullptr)
  5. 	, _endofstorage(nullptr)
  6. {
  7. 	while (first != last)
  8. 	{
  9. 		push_back(*first);
  10. 		++first;
  11. 	}
  12. }

（3）给想要的大小和给定的值进行的构造函数

        n是构造size的大小，val是确定的值。

        这里之所以有两个是因为当给的数是两个int类型的数时，会去调用上面的迭代器的构造函数，但是迭代器的构造函数又不能进行解引用操作，导致报错。

        因此实现两个可以有效的避免这种问题。

  1. vector(size_t n, const T& val = T())
  2. 	: _start(nullptr)
  3. 	, _finish(nullptr)
  4. 	, _endofstorage(nullptr)
  5. {
  6. 	reserve(n);
  7. 	for (size_t i = 0; i < n; ++i)
  8. 	{
  9. 		push_back(val);
  10. 	}
  11. }
  12.  
  13. vector(int n, const T& val = T())
  14. 	: _start(nullptr)
  15. 	, _finish(nullptr)
  16. 	, _endofstorage(nullptr)
  17. {
  18. 	reserve(n);
  19. 	for (int i = 0; i < n; ++i)
  20. 	{
  21. 		push_back(val);
  22. 	}
  23. }

4.拷贝构造、赋值运算符重载函数

（1）实现自己的swap函数

        这里的拷贝构造和赋值运算符重载函数都是现代写法，因此需要自己实现一个swap函数来更方便的完成。

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

（2）拷贝构造函数

  1. vector(const vector<T>& v)
  2. 	: _start(nullptr)
  3. 	, _finish(nullptr)
  4. 	, _endofstorage(nullptr)
  5. {
  6. 	vector<T> tmp(v.begin(), v.end());
  7. 	swap(tmp);
  8. }

（3）赋值运算符函数

  1. vector<T>& operator=(vector<T> v)
  2. {
  3. 	swap(v);
  4. 	return *this;
  5. }

5.析构函数

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

6.迭代器

        迭代器要实现非const和const两种版本的。

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

7.大小、容量

        _finish - _start就是size。

        _endofstorage - _start就是capacity。

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

8.reserve函数

        这里要注意用深拷贝，使用for循环，而不要用memcpy。

  1. void reserve(size_t n)
  2. {
  3. 	size_t sz = size();
  4. 	if (n > capacity())
  5. 	{
  6. 		T* tmp = new T[n];
  7. 		if (_start)
  8. 		{
  9. 			// memcpy(tmp, _start, size() * sizeof(T));
  10. 			for (size_t i = 0; i < size(); ++i)
  11. 			{
  12. 				tmp[i] = _start[i];
  13. 			}
  14. 			delete _start;
  15. 		}
  16.  
  17. 		_start = tmp;
  18.  
  19. 	}
  20.  
  21. 	_finish = _start + sz;
  22. 	_endofstorage = _start + n;
  23. }

9.resize函数

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

10.尾插、尾删函数

        尾插、尾删函数可以自己实现，也可以调用insert和erase函数来实现。

        尾插函数调用时参数为end()的原因是，end()函数返回的迭代器是最后一位元素的下一位，因此在end()前插入，就正好相当于尾插。

        尾删函数同理，end() - 1才相当于最后一位元素。

  1. void push_back(const T& x)
  2. {
  3. 	/*if (_finish == _endofstorage)
  4. 	{
  5. 		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  6. 		reserve(newCapacity);
  7. 	}
  9. 	*_finish = x;
  10. 	++_finish;*/
  11.  
  12. 	insert(end(), x);
  13. }
  14.  
  15. void pop_back()
  16. {
  17. 	/*if (_finish > _start)
  18. 	{
  19. 		--_finish;
  20. 	}*/
  21.  
  22. 	erase(end() - 1);
  23. }

11.下标运算符重载函数

        要实现非const和const两种。

  1. T& operator[](size_t pos)
  2. {
  3. 	assert(pos < size());
  4.  
  5. 	return _start[pos];
  6. }
  7.  
  8. const T&operator[](size_t pos) const
  9. {
  10. 	assert(pos < size());
  11.  
  12. 	return _start[pos];
  13. }

12.插入函数

        这里要注意野指针的情况，详细可以看迭代器失效中insert的第一种情况。

        在STL库中insert要返回iterator，因此我们模拟也是返回iterator，这里返回iterator还是一种避免迭代器失效的方法。

  1. iterator insert(iterator pos, const T& x)
  2. {
  3. 	assert(pos >= _start && pos <= _finish);
  4.  
  5. 	// 扩容
  6. 	if (_finish == _endofstorage)
  7. 	{
  8. 		size_t n = pos - _start;
  9.  
  10. 		size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  11. 		reserve(newCapacity);
  12.  
  13. 		pos = _start + n;
  14. 	}
  15.  
  16. 	// 挪动数据
  17. 	iterator end = _finish - 1;
  18. 	while (end >= pos)
  19. 	{
  20. 		*(end + 1) = *end;
  21. 		--end;
  22. 	}
  23.  
  24. 	*pos = x;
  25. 	++_finish;
  26.  
  27. 	return pos;
  28.  
  29. }

13.删除函数

        在STL库中erase要返回iterator，因此我们模拟也是返回iterator，这里返回iterator还是一种避免迭代器失效的方法。

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

14.清理函数 

  1. void clear()
  2. {
  3. 	_finish = _start;
  4. }

五.vector类模拟实现总代码

  1. #pragma once
  2.  
  3. #include <assert.h>
  4.  
  5. namespace hb
  6. {
  7. 	template <class T>
  8. 	class vector
  9. 	{
  10. 	public:
  11. 		typedef T* iterator;
  12. 		typedef const T* const_iterator;
  13.  
  14. 		vector()
  15. 			: _start(nullptr)
  16. 			, _finish(nullptr)
  17. 			, _endofstorage(nullptr)
  18. 		{}
  19.  
  20. 		template <class InputIterator>
  21. 		vector(InputIterator first, InputIterator last)
  22. 			: _start(nullptr)
  23. 			, _finish(nullptr)
  24. 			, _endofstorage(nullptr)
  25. 		{
  26. 			while (first != last)
  27. 			{
  28. 				push_back(*first);
  29. 				++first;
  30. 			}
  31. 		}
  32.  
  33. 		vector(size_t n, const T& val = T())
  34. 			: _start(nullptr)
  35. 			, _finish(nullptr)
  36. 			, _endofstorage(nullptr)
  37. 		{
  38. 			reserve(n);
  39. 			for (size_t i = 0; i < n; ++i)
  40. 			{
  41. 				push_back(val);
  42. 			}
  43. 		}
  44.  
  45. 		vector(int n, const T& val = T())
  46. 			: _start(nullptr)
  47. 			, _finish(nullptr)
  48. 			, _endofstorage(nullptr)
  49. 		{
  50. 			reserve(n);
  51. 			for (int i = 0; i < n; ++i)
  52. 			{
  53. 				push_back(val);
  54. 			}
  55. 		}
  56.  
  57. 		void swap(vector<T>& v)
  58. 		{
  59. 			std::swap(_start, v._start);
  60. 			std::swap(_finish, v._finish);
  61. 			std::swap(_endofstorage, v._endofstorage);
  62. 		}
  63.  
  64. 		vector(const vector<T>& v)
  65. 			: _start(nullptr)
  66. 			, _finish(nullptr)
  67. 			, _endofstorage(nullptr)
  68. 		{
  69. 			vector<T> tmp(v.begin(), v.end());
  70. 			swap(tmp);
  71. 		}
  72. 		
  73. 		vector<T>& operator=(vector<T> v)
  74. 		{
  75. 			swap(v);
  76. 			return *this;
  77. 		}
  78.  
  79. 		~vector()
  80. 		{
  81. 			if (_start)
  82. 			{
  83. 				delete[] _start;
  84. 				_start = _finish = _endofstorage = nullptr;
  85. 			}
  86. 		}
  87.  
  88. 		iterator begin()
  89. 		{
  90. 			return _start;
  91. 		}
  92.  
  93. 		iterator end()
  94. 		{
  95. 			return _finish;
  96. 		}
  97.  
  98. 		const_iterator begin() const
  99. 		{
  100. 			return _start;
  101. 		}
  102.  
  103. 		const_iterator end() const
  104. 		{
  105. 			return _finish();
  106. 		}
  107.  
  108. 		size_t size() const
  109. 		{
  110. 			return _finish - _start;
  111. 		}
  112.  
  113. 		size_t capacity() const
  114. 		{
  115. 			return _endofstorage - _start;
  116. 		}
  117.  
  118. 		void reserve(size_t n)
  119. 		{
  120. 			size_t sz = size();
  121. 			if (n > capacity())
  122. 			{
  123. 				T* tmp = new T[n];
  124. 				if (_start)
  125. 				{
  126. 					// memcpy(tmp, _start, size() * sizeof(T));
  127. 					for (size_t i = 0; i < size(); ++i)
  128. 					{
  129. 						tmp[i] = _start[i];
  130. 					}
  131. 					delete _start;
  132. 				}
  133.  
  134. 				_start = tmp;
  135.  
  136. 			}
  137.  
  138. 			_finish = _start + sz;
  139. 			_endofstorage = _start + n;
  140. 		}
  141.  
  142. 		void resize(size_t n, T val = T())
  143. 		{
  144. 			if (n > capacity())
  145. 			{
  146. 				reserve(n);
  147. 			}
  148.  
  149. 			if (n > size())
  150. 			{
  151. 				while (_finish < _start + n)
  152. 				{
  153. 					*_finish = val;
  154. 					++_finish;
  155. 				}
  156. 			}
  157. 			else
  158. 			{
  159. 				_finish = _start + n;
  160. 			}
  161. 		}
  162.  
  163. 		void push_back(const T& x)
  164. 		{
  165. 			/*if (_finish == _endofstorage)
  166. 			{
  167. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  168. 				reserve(newCapacity);
  169. 			}
  171. 			*_finish = x;
  172. 			++_finish;*/
  173.  
  174. 			insert(end(), x);
  175. 		}
  176.  
  177. 		void pop_back()
  178. 		{
  179. 			/*if (_finish > _start)
  180. 			{
  181. 				--_finish;
  182. 			}*/
  183.  
  184. 			erase(end() - 1);
  185. 		}
  186.  
  187. 		T& operator[](size_t pos)
  188. 		{
  189. 			assert(pos < size());
  190.  
  191. 			return _start[pos];
  192. 		}
  193.  
  194. 		const T&operator[](size_t pos) const
  195. 		{
  196. 			assert(pos < size());
  197.  
  198. 			return _start[pos];
  199. 		}
  200.  
  201. 		iterator insert(iterator pos, const T& x)
  202. 		{
  203. 			assert(pos >= _start && pos <= _finish);
  204.  
  205. 			// 扩容
  206. 			if (_finish == _endofstorage)
  207. 			{
  208. 				size_t n = pos - _start;
  209.  
  210. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  211. 				reserve(newCapacity);
  212.  
  213. 				pos = _start + n;
  214. 			}
  215.  
  216. 			// 挪动数据
  217. 			iterator end = _finish - 1;
  218. 			while (end >= pos)
  219. 			{
  220. 				*(end + 1) = *end;
  221. 				--end;
  222. 			}
  223.  
  224. 			*pos = x;
  225. 			++_finish;
  226.  
  227. 			return pos;
  228.  
  229. 		}
  230.  
  231. 		iterator erase(iterator pos)
  232. 		{
  233. 			assert(pos >= _start && pos <= _finish);
  234.  
  235. 			iterator it = pos + 1;
  236. 			while (it != _finish)
  237. 			{
  238. 				*(it - 1) = *it;
  239. 				++it;
  240. 			}
  241.  
  242. 			--_finish;
  243.  
  244. 			return pos;
  245. 		}
  246.  
  247. 		void clear()
  248. 		{
  249. 			_finish = _start;
  250. 		}
  251. 	private:
  252. 		iterator _start;
  253. 		iterator _finish;
  254. 		iterator _endofstorage;
  255. 	};
  256. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/452652
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号