（1）vector采用连续空间来存储元素，可以使用下标访问vector元素，访问元素和数组一样方便。vector大小可以动态改变，而且会被容器自动处理，这一点数组无法做到。

（2）vector使用动态分配分配数组来存储元素，插入新元素时，vector数组为了增加存储空间，会分配一个新数组，再把所有元素全部移动到这个数组里，代价相对高一些。

（3）vector会分配额外的空间来满足可能的增长，因为分配的存储空间比实际需要的的存储空间更大。vector以动态增长的方式管理存储空间。

（4）vector在访问元素、末尾添加删除元素时很高效，在其他位置插入删除需要挪动元素，效率低。

二、vector类成员


#include<iostream>
#include<vector>
 
using namespace std;
int main()
{   
    vector<int> v;//构造一个没有元素的空容器
 
    vector<int> v1(3, 5);//构造一个有3个元素的容器，每个元素的值都为5
 
    vector<int> v2(v1.begin(),v1.end());// 使用迭代器区间初始化
 
	string s1("good morning");
    vector<char> v3(s1.begin() + 2, --s1.end()); // 使用一部分区间初始化
 
    vector<int> v4(v2);//以与v2相同的顺序及值拷贝构造一个容器
 
    //插入4个元素
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
 
    return 0;
}

1.vector类对象构造


//构造空的vector
explicit vector (const allocator_type& alloc = allocator_type());
	
//构造一个vector,有n个元素，每个元素值为val
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());	
 
//构造一个vector,值为InputIterator的first到last之间的元素
template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());	
 
//使用x拷贝构造一个vector
vector (const vector& x);

(1).无参的构造函数

说明:

我们使用vector<int> a; 创建一个对象a时,编译器会调用其构造函数对该对象进行初始化,三个指针都指向同一块空间,此时空间中没有元素,因为我们要求的是_start指向第一个元素,_finish指向最后一个元素的后一位,而这里_start和_finish在同一个位置,那我们就认为容器中元素个数为0.(_endOfStorage指向空间的最后一位)


        vector()
            :_start(nullptr)
            ,_finish(nullptr)
            ,_endOfStorage(nullptr)
        {}

(2)范围构造函数。

说明：

函数模板InputIterator是输入迭代器类型，并且类型不确定，我们在创建的时候传入参数为一段空间的前闭后开的区间,因为我们无法知道这段空间是以什么类型存在的,所以使用函数模板的方式进行定义,当该构造函数被调用的时候,first就会变成实际对应的类型了


template <class InputIterator>
// 重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);   
				++first;  
			}
		}

(3) 填充构造函数。

向容器中插入n个值为val的元素


        vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reverse(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
 
		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reverse(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

理论上将，提供了vector(size_t n, const T& value = T())之后 vector(int n, const T& value = T())就不需要提供了，但是对于： vector<int> v(10, 5)；编译器在编译时，认为T已经被实例化为int，而10和5编译器会默认其为int类型就不会走vector(size_t n, const T& value = T())这个构造方法，最终选择的是：vector(InputIterator first, InputIterator last)因为编译器觉得区间构造两个参数类型一致，因此编译器就会将InputIterator实例化为int但是10和5根本不是一个区间，编译时就报错了故需要增加该构造方法

2.拷贝构造


vector<string> v6;
v6.push_back(string("delia"));
 
vector<string> v7(v6);//用v6拷贝构造v7
PrintVector(v7);// delia
 
vector<double> v8(v5);//用v5拷贝构造v8

假如不写vector类的拷贝构造函数，那么编译器自动生成的默认拷贝构造函数只能完成浅拷贝，vector类的3个成员变量的类型都是T*，如果T是内置类型，那么拷贝OK；但如果T是自定义类型，那么拷贝对象和被拷贝对象指向同一块空间，后定义的先析构，这块空间会被释放两次，程序就会崩掉。

(1)传统写法


		// 拷贝传统写法
		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T) * v.size());
            
            // 拷贝数据
			for (size_t i = 0; i < v.size(); ++i)
			{
				// 若这里是string对象，调用的是string的赋值重载，是深拷贝
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}

为什么2.拷贝数据时不使用memcpy呢？

1. memcpy 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

2. 如果拷贝的是自定义类型的元素， memcpy 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy 的拷贝实际是浅拷贝。

如vector<string>：

注意： memcpy拷贝的元素为string对象，是自定义类型，拷贝时为浅拷贝，其中两块空间的string数据的_str会指向同一串字符串，在析构时，vector的每个元素析构两次，那么同一块空间会被释放两次，程序会崩。

（2）现代的拷贝构造：开空间+逐个尾插

使用现代的拷贝构造时必须初始化，否则_start、_finish、_end_of_storage都是随机值，拷贝数据时可能会导致越界。如果T是自定义类型，那么会调用T的拷贝构造函数进行深拷贝


        vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(v.capacity());//开与v一样大小的空间
 
			//逐个尾插数据
			for (auto& e: v)
			{
				push_back(e);
			}
		}

3.vector元素访问符


      reference operator[] (size_type n);      //可读可写
const_reference operator[] (size_type n) const;//只读

vector使用operator[ ]遍历元素，像数组一样：


	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;

模拟实现：


		T& operator[](size_t pos)
		{
			assert(pos < size());// 判断pos是否合法
			return _start[pos];
		}
 
		const T& operator[](size_t pos) const
		{
			assert(pos < size());
			return _start[pos];
		}

4.赋值运算符重载

(1）传统的赋值运算符重载


		// 传统写法
		vector<T> operator=(vector<T> v)
		{
			if (this != &v)
			{
				//1.清理空间，让空间变干净
				delete[] _start;
 
				//2.申请空间
				_start = new T[v.capacity()];
 
				//3.拷贝数据
				for (size_t i = 0; i < v.size(); i++)
				{
					_start[i] = v._start[i];
				}
 
				//4.更新大小及容量
				_finish = _start + v.size();
				_end_of_storage = _start + v.capacity();
			}
		}

（2）现代的赋值运算符重载函数

形参是实参的一份拷贝所以在operator=就不需要检测是否给自己赋值了就可以直接交换了


void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
		// v1 = v2
		vector<T>& operator=(vector<T> v)// 形参是实参的一份拷贝
		{
			swap(v);// 直接交换*this和v的内容
			return *this;
		}

5.vector迭代器

迭代器是一种容器可以统一使用的遍历方式，因此vector也支持使用迭代器遍历


      iterator begin();      //可读可写
const_iterator begin() const;//只读
 
      iterator end();        //可读可写
const_iterator end() const;  //只读
 
      reverse_iterator rbegin();       //反向迭代器 可读可写
const_reverse_iterator rbegin() const; //反向迭代器 只读
 
      reverse_iterator rbegin();       //反向迭代器 可读可写
const_reverse_iterator rbegin() const; //反向迭代器 只读

(1）迭代器

①可读可写


    vector<int>::iterator it = v.begin();//可读可写
	while (it != v.end())
	{
        *it += 2;
        cout << *it << " ";
        ++it;
	}
	cout << endl;

模拟实现：


		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}

②只读


    vector<int>::const_iterator it = v.begin();//只读
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;


		const_iterator begin() const
		{
			return _start;
		}
		const_iterator end() const
		{
			return _finish;
		}

（2）反向迭代器

①可读可写


    vector<int>::reverse_iterator rit = v.rbegin();//可读可写
    while (rit != v.rend())
    {
        *rit += 2;
        cout << *rit << " ";
        rit++;
    }
    cout << endl;

②只读


    vector<int>::const_reverse_iterator rit = v.rbegin();//只读
    while (rit != v.rend())
    {
        cout << *rit << " ";
        rit++;
    }
    cout << endl;

6.vector容量

（1）vector增容机制

在VS下执行这段代码：


void test_vector3()
{
    size_t sz;
    std::vector<int> foo;
    sz = foo.capacity();
  
    std::cout << "making foo grow:\n";
 
    for (int i = 0; i < 100; i++)
    {
        foo.push_back(i);
        if (sz != foo.capacity())
        {
            sz = foo.capacity();
            std::cout << "capacity changed:" << sz << endl;
        }
    }
}

同样的代码在linux下运行，发现是2倍增容的：

因此，在不同的编译器下增容机制不同。

（2）reserve()和resize()


void reserve (size_type n);//开辟n个元素空间
void resize (size_type n, value_type val = value_type());
//开辟n个元素空间，并将每个元素默认初始化为val

如果加上reserve()，那么会提前知道要开多少空间，就提前开好了，避免后面再开空间


void test_vector3()
{
    size_t sz;
    std::vector<int> foo;
    sz = foo.capacity();
    foo.reserve(100);
  
    std::cout << "making foo grow:\n";
 
    for (int i = 0; i < 100; i++)
    {
        foo.push_back(i);
        if (sz != foo.capacity())
        {
            sz = foo.capacity();
            std::cout << "capacity changed:" << sz << endl;
        }
    }
}

监视如下代码发现，reserve()之后，capacity变了，但是size没变；resize()之后，capacity变了，size也变了，且每个元素都被默认赋值为0


    vector<int> v1;
    v1.reserve(10);
 
    vector<int> v2;
    v2.resize(10);

reserve()

注意 : 将数据拷贝到新空间，仍然不能用memcpy函数，因为对于需要深拷贝的自定义类型，使用memcpy函数以后，新开辟空间里的元素和原空间里的元素所指向的内存空间是一样的，当旧空间被释放时，会调用自定义类型的析构函数，从而使得新开辟空间里的元素指向的内存空间也被释放掉了


		void reverse(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();// 提前把原空间大小记录下来
				T* tmp = new T[n];
				if (_start) // 旧空间不为空就拷贝
				{
					//memcpy(tmp, _start, sizeof(T) * size());
					
					// 拷贝数据
					for (size_t i = 0; i < n; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;// 释放旧空间
				}
 
				// 更新成员变量
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

reszie()

(1). 当 n < size 时，直接将 _finish = _start + n (将有效数据长度缩小)即可
(2). 当 size < n <= capacity 时，我们将有效数据的长度增加到 n，增加出来的有效数据内容是val
(3). 当 n > capacity时，先调用上面的 reserve 函数进行增容，再将有效数据的长度增加到 n，增加出来的有效数据内容是val


		void resize(size_t n, const T& val = T())
		{
			// 1.如果n小于当前的size，则数据个数缩小到n，相当于是删除数据
			if (n <= size())
			{
				_finish = _start + n;
			}
			else
			{
				// 2.空间不够则增容
				if (n > capacity())
					reverse(n);
				//赋值
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

（3）size()、capacity()

返回vector元素个数和容量


size_type size() const;
 
size_t size() const
{
	return _finish - _start;
}
 
size_t capacity() const
{
	return _end_of_storage - _start;
}

求v5的size()


    vector<int> v5;
    //插入4个元素
    v5.push_back(1.1);
    v5.push_back(2.2);
    v5.push_back(3.3);
    v5.push_back(4.4);
    cout << v5.size() << endl; //4

（4）empty()

判断vector是否为空，为空返回1，不为空返回0


bool empty() const;
 
bool empty()
{
	return _finish == _start;
}

判断v5是否为空

cout << v5.empty() << endl; //0

7.vetor尾插和尾删


void push_back (const value_type& val);//尾插元素
void pop_back();//尾删元素

向v5尾插元素和尾删元素


    v5.push_back(5.5);
 
    v5.pop_back();

模拟实现


		void push_back(const T& x)
		{
			// 判断是否需要增容
			if (_finish == _end_of_storage)
			{
				reverse(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;// 插入元素
			++_finish;// 更新位置
		}
 
 
        void pop_back()
		{
			assert(!empty());
			--_finish;// 直接更新大小
		}

8.vector在任意位置插入和删除


iterator insert (iterator position, const value_type& val);//插入val到position位置
 
void insert (iterator position, size_type n, const value_type& val);
//将n个val插入到position位置
 
template <class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);
    //将值为InputIterator的first到last之间的元素插入到position位置


    vector<double> v5;
    //插入4个float元素
    v5.push_back(1.1);
    v5.push_back(2.2);
    v5.push_back(3.3);
    v5.push_back(4.4);
    v5.push_back(5.5);
    
    v5.insert(v5.end(), 6.6);//在v5末尾插入6.6
    PrintVector(v5);// 1.1 2.2 3.3 4.4 5.5 6.6
    
    v5.insert(v5.begin(), 2,0);//在v5开头插入2个0
    PrintVector(v5);// 0 0 1.1 2.2 3.3 4.4 5.5 6.6
 
    vector<double> v6;
    v6.push_back(7.7);
    v6.push_back(8.8);
 
    v5.insert(v5.begin(), v6.begin(),v6.end());//在v5开头插入v6
    PrintVector(v5);//  7.7 8.8 0 0 1.1 2.2 3.3 4.4 5.5 6.6


		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);
 
			// 空间不够先扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;// 相对距离
				reverse(capacity() == 0 ? 4 : capacity() * 2);
 
				// 插入数据需扩容时，_start已经不是原来的了，而是新开空间后的了，
				// 这时候pos和_start不是同一块空间的了，所以就需更新pos，解决pos失效的问题
				pos = _start + len;
			}
            
            // 挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = val;
			++_finish;
 
			return pos;
		}

（2）删除


iterator erase (iterator position);//删除某一位置元素
 
iterator erase (iterator first, iterator last);
//删除迭代器first和last之间的元素
 
 
    v5.erase(v5.begin());//删除v5开头元素
    PrintVector(v5);// 8.8 0 0 1.1 2.2 3.3 4.4 5.5 6.6 
 
    v5.erase(v5.begin(), v5.begin()+2);//从v5开头删除2个元素
    PrintVector(v5);// 0 1.1 2.2 3.3 4.4 5.5 6.6


		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
 
			iterator start = pos + 1;
			while (start != _finish)
			{
				*(start - 1) = *start;
				++start;
			}
			--_finish;
 
			return pos;
		}

insert()和erase()之后需要挪动元素，时间复杂度为O(N)，效率较低，不推荐用insert()和erase()插入删除元素

9.find()

在迭代器区间内查找元素，find函数实现在algorithm中，可以给所有容器使用，因此要使用find函数，就要include<algorithm>


template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
//在InputIterator迭代器first和last区间内查找val元素的位置

注意：迭代器区间是左闭右开，因此能取到第一个位置，但取不到最后一个位置


    vector<double>::iterator pos = find(v5.begin(), v5.begin() + 3, 1.1);
//在第一个元素和第四个元素（左闭右开，不包含第四个元素）之间查找值为1.1的元素位置
    v5.erase(pos);//删除1.1位置的元素，即删除1.1
 
     PrintVector(v5);

10.swap()

将this指针指向的对象的内容和x进行交换

void swap (vector& x);


    vector<int> v1;
    v1.push_back(20);
 
    vector<int> v2(10,0);
    v1.swap(v2);//交换v1和v1的元素
 
    PrintVector(v1);// 0 0 0 0 0 0 0 0 0 0 
    PrintVector(v2);// 20


void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}

vector自己实现了swap()，相比较，库里的swap需要3次深拷贝，代价比较高：


template <class T> void swap (T& a, T& b);
{
    T c(a); a=b; b=c;
}

三、迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如： vector 的迭代器就是原生态指针 T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃 ( 即如果继续使用已经失效的迭代器，程序可能会崩溃) 。

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

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

比如：resize、reserve、insert、assign、 push_back等。

（1）在v中插入元素1,2,3,4,5后，在3前面插入30


    vector<int> v;
 
    //插入6个int元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
 
    //在3的前面插入30
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);//查找3的位置
    if (pos != v.end())
    {
        v.insert(pos, 30);
    }
    PrintVector(v);

但是当删除30时，执行如下代码，程序崩了


    v.erase(pos);
    PrintVector(v);

这是因为先查找3，找到后挪动3的位置及之后的数据，插入30，3已经挪走了，但pos还指向原来的位置，也就是现在30的位置。再erase的时候，pos失效了，因为pos的意义变了，不再指向3了，所以程序崩溃。

（2）如下代码当删除所有偶数时，程序会崩


    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中所有的偶数
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            v.erase(it);
        }
        it++;
    }
 
    PrintVector(v);

执行过程：end不固定，删除数据后，每次都会去重新拿取，end是最后一个数的下一个位置

而且执行过程中，由于删除数据后，it++了，迭代器的意义变了，所以结果一定不正确。

迭代器失效有两种情况：

（1）pos意义变了，插入数据以后，pos不再指向3，而是指向30，导致erase(pos)没有达到删除3的目的，反而删除的是30

（2）程序可能崩溃，pos变成了野指针

2.如何解决迭代器失效

在使用迭代器之前，对迭代器重新赋值

对于（1）使用迭代器之前，对迭代器重新赋值


    vector<int> v;
 
    //插入6个int元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
 
    //在3的前面插入30
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    if (pos != v.end())
    {
        v.insert(pos, 30);
    }
 
    PrintVector(v);
 
    //使用迭代器之前，对迭代器重新赋值
    pos = find(v.begin(), v.end(), 3);
    //然后再使用迭代器
    if (pos != v.end())
    {
        v.erase(pos);
    }
    PrintVector(v);

对于（2）每次使用迭代器之前，对迭代器重新赋值，当it为偶数的位置时，删除偶数后，it不用++


    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中所有的偶数
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            //每次使用迭代器之前，对迭代器重新赋值
            it = v.erase(it);//删除偶数后，it不用++
        }
        else 
        {
            it++;//奇数，it++
        }
        
    }
 
    PrintVector(v);

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