【C++ vector 类】-EW帮帮网

1. 标准库中的vector类

vector 类的介绍：

注意：

1. vector是表示可变大小数组的序列容器。

2. 就像数组一样，vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

a. vector 的构造函数

代码举例1

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
}

代码举例2

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t(10,2); 
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
}

运行结果：

代码举例3

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t(10,2); 
    vector<int>t1(t);
    for (int i = 0; i < t.size(); i++)
    {
        cout << t1[i] << " ";
    }
}

运行结果：

代码举例4

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t(10,2); 
    vector<int>t1(t.begin(),t.end());
    for (int i = 0; i < t.size(); i++)
    {
        cout << t1[i] << " ";
    }
}

运行结果：

b. vector iterator 的使用

begin + end ( begin : 获取第一个数据位置的iterator/const_iterator，end : 获取最后一个数据的下一个位置的iterator/const_iterator )

画图分析

rbegin + rend (rbegin : 获取最后一个数据位置的reverse_iterator , rend : 获取第一个数据前一个位置的 reverse_iterator )

画图分析

c. vector 空间增长问题

代码举例（resize）

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t(10,2); 
    t.resize(5); 
    //缩容 , size 变小 , capacity 不变
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
    t.resize(10); 
    //扩容 , size 变大 , 多余的默认赋值为 T(),这里是调用 int()
    // 注意 ：在类的模板里面 ,允许内置类型也有自己的构造函数
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
    cout << endl;
    t.resize(15, 5);
    //扩容 , size 变大 , 多余的赋值为 5
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
}

运行结果：

d. vector 增删查改

代码举例1 （push_back）

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
}

运行结果：

代码举例2 (pop_back)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    t.pop_back();
    for (int i = 0; i < t.size(); i++)
    {
        cout << t[i] << " ";
    }
}

运行结果：

代码举例3 (find)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    t.pop_back();
    vector<int> :: iterator pos = find(t.begin(), t.end(), 5);
    cout << *pos << endl;
}

运行结果：

代码举例4 (insert)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    vector<int> :: iterator pos = find(t.begin(), t.end(), 5);
    t.insert(pos, 7);
    for (auto i : t)
    {
        cout << i << " ";
    }
}

运行结果：

代码举例5 (erase)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    vector<int> :: iterator pos = find(t.begin(), t.end(), 5);
    t.erase(pos);
    for (auto i : t)
    {
        cout << i << " ";
    }
}

运行结果：

代码举例6 (swap)

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(10);
    t.push_back(5);
    t.push_back(3);
    vector<int> t1(5,7);
    t.swap(t1);
    for (auto i : t)
    {
        cout << i << " ";
    }
    cout << endl;
    for (auto i : t1)
    {
        cout << i << " ";
    }
}

运行结果：

2. 迭代器失效

a. 概念

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

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

1. 会引起其底层空间改变的操作(扩容)，都有可能是迭代器失效

如：push_back ，resize , reserve , insert

画图分析

具体详情配合看 vector 的实现

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

如：erase

画图分析

具体详情配合看 vector 的实现

注意：

vs 对于迭代器失效检查很严格，如使用了 erase 之后，之前的迭代器就不允许使用，只有重新给迭代器赋值，才可以继续使用
Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端

3. vector 类的模拟实现

代码

namespace lhy
{
	template<class T>
	class vector
	{
	public:
	  typedef T* iterator;
	  typedef const T* const_iterator;
	  vector()
	  {}
	  vector(size_t n,const T&val = T())
	  {
		  reserve(n);
		  for (int i = 0; i < n; i++)
		  {
			  push_back(val);
		  }
	  }
	  vector(int n, const T& val = T())
	  {
		  reserve(n);
		  for (int i = 0; i < n; i++)
		  {
			  push_back(val);
		  }
	  }
	  template<class InputerIterator>
	  vector(InputerIterator x, InputerIterator y)
	  {
		  while (x != y)
		  {
			  push_back(*x);
			  x++;
		  }
	  }
	  vector(const vector<T>& t)
	  {
		  _start = new T[t.capacity()];
		  for (int i = 0; i < t.size(); i++)
		  {
			  _start[i] = t._start[i];
		  }
		  _finish = _start + t.size();
		  _end_of_storage = _start + t.capacity();
	  }
	  ~vector()
	  {
		  delete[] _start;
		  _start = _finish = _end_of_storage = nullptr;
	  }
	  vector<T>& operator=(const vector<T>& t)
	  {
		  _start = new T[t.capacity()];
		  for (int i = 0; i < t.size(); i++)
		  {
			  _start[i] = t._start[i];
		  }
		  _finish = _start + t.size();
		  _end_of_storage = _start + t.capacity();
      return *this;
	  }
	  void reserve(size_t n)
	  {
		  if (n > capacity())
		  {
			  size_t sz = size();
			  T* tmp = new T[n];
			  if (_start)
			  {
				  for (int i = 0; i < sz; i++)
				  {
					  tmp[i] = _start[i];
				  }
				  delete[] _start;
			  }
			  _start = tmp;
			  _finish = tmp + sz;
			  _end_of_storage = tmp + n;
		  }
	  }
	  void resize(size_t n,const T x = T())
	  {
		  if (n <= size())
		  {
			  size_t m = size() - n;
			  _finish -= m;
		  }
		  else
		  {
			  size_t m = n - size();
			  reserve(n);
			  while (m--)
			  {
				  *_finish++ = x;
			  }
		  }
	  }
	  size_t capacity()  const
	  {
		  return _end_of_storage - _start;
	  }
	  size_t size() const
	  {
		  return _finish - _start;
	  }
	  void push_back(const T & x)
	  {
		  if (_finish == _end_of_storage)
		  {
			  reserve(capacity() * 2 == 0 ?  4 : capacity() * 2);
		  }
		  *_finish = x;
		  _finish++;
	  }
	  void pop_back()
	  {
		  assert(size() != 0);
		   _finish--;
		  
	  }
	  T& operator[](size_t pos)
	  {
		  assert(pos < size());
		  return *(_start + pos);
	  }
	  const T& operator[](size_t pos) const
	  {
		  assert(pos < size());
		  return _start[pos];
	  }
	  iterator insert(iterator pos, const T& x)
	  {
		  assert(pos <= _finish && pos >= _start);
		  size_t n = pos - _start;
		  if (_finish == _end_of_storage)
		  {
			  reserve(size() == 0 ? 4 : size() * 2);
		  }
		  pos = n + _start;
		  iterator tmp = _finish;
		  while (tmp != pos)
		  {
			  *tmp = *(tmp - 1);
			  tmp--;
		  }
		  *pos = x;
		  _finish++;
		  return pos;
	  }
	  iterator erase(iterator pos)
	  {
		  assert(pos >= _start && pos < _finish);
		  iterator tmp = pos;
		  while (tmp != _finish - 1)
		  {
			  *tmp = *(tmp + 1);
			  tmp++;
		  }
		  _finish--;
		  return pos;
	  }
	  bool empty()
	  {
		  return _start == _finish;
	  }
	  iterator begin()
	  {
		  return _start;
	  }
	  iterator end()  
	  {
		  return _finish;
	  }
	  const_iterator begin() const
	  {
		  return _start;
	  }
	  const_iterator end() const
	  {
		  return _finish;
	  }
	  private:
	  iterator _start = nullptr;
	  iterator _finish = nullptr;
	  iterator _end_of_storage = nullptr;
	 };
  }

vector 深浅拷贝问题分析

分析：

tmp[i] 是 T类型，对于 T类型，有两者可能：

一种是内置类型，发生浅拷贝

另一种是自定义类型，调用自身的构造函数（这里的问题在于自定义类型发生的是浅拷贝还是深拷贝）

如：T 是 string 类型，会调用 string类里面的构造函数，且发生深拷贝

但是如果是 vector<int> 类型呢？

回到它的成员变量：

很明显，_start 不能指向的相同的空间（否则析构函数会释放同一块空间两次），所以这里发生深拷贝

所以这里我们构造一个赋值运算符重载函数，完成深拷贝

vector 迭代器的类型（从功能上分类）

vector 有随机迭代器，可以实现 ++ -- + -

本文含有隐藏内容，请开通VIP 后查看

【C++ vector 类】

1. 标准库中的vector类

a. vector 的构造函数

b. vector iterator 的使用

c. vector 空间增长问题

d. vector 增删查改

2. 迭代器失效

a. 概念

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

3. vector 类的模拟实现

网站公告

今日签到

热门文章

最新发布