【C++】vector容器详解&&迭代器失效问题_vector const allocator_type

目录

vector介绍：

vector常用接口：

1、构造函数（constructor）

2、析构（destructor）

3、迭代器（iterator） 

4、容量相关

5、元素访问 

6、修改相关

迭代器失效问题 

什么是迭代器？

迭代器与指针：

迭代器的分类和操作：

为什么对迭代器分类？

迭代器失效问题即解决方法

---

vector介绍：

1、vector是表示可变大小的序列容器

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

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

4、vector分配空间粗略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于再末尾插入一个元素的时候是在常数时间的复杂度完成的。

 5、因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态曾张。

6、与其他动态序列容器相比（deques、lists and forward _lists）， vector在访问元素时候更加高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_lists统一的迭代器和引用更好。

vector常用接口：

1、构造函数（constructor）

const allocator_type & alloc = allocator_type()是一个配置器相关内容，它是用于指定要使用的空间配置器的，STL提供的默认的空间配置器，我们基本不用管这个参数，除非是我们自己实现了一个空间配置器，然后希望使用我们自己写的空间配置器。暂时忽略即可。

①explicit vector(const allocator_type & alloc = allocator_type())：构建一个没有元素的空容器

②explicit vector(size_type n, const value_type& val = value_type(), const allocator_type & alloc = allocator_type())：构造n个值为val的容器

③template<class InputIterator>

vector(InputIterator first, InputIterator last, const allocator_type & alloc = allocator_type())：根据给定的范围构造容器v3，这个范围也可以是数组的一部分。

 ④vector(const vector& x)：拷贝构造，用容器x的内容来构造新的容器

vector& operator=(const vector& x)：赋值运算符重载 

2、析构（destructor）

~vector() 

3、迭代器（iterator） 

迭代器都是左闭右开

①begin() & end()

iterator begin()  |  const_iterator begin() const：获取第一个数据位置的iterator或者const_iterator

iterator end()  |  const_iterator end() const：获取最后一个数据的下一个位置的iterator或者const_iterator

②rbegin() & rend()

reverse_iterator rbegin()  |   const_reverse_iterator rbegin() const：获取最后一个数据位置的reverse_iterator或者const_reverse_iterator

 reverse_iterator rend()  |   const_reverse_iterator rend() const：获取第一个数据的前一个位置的reverse_iterator或者const_reverse_iterator

③cbegin() & cend()   （C++11）

const_iterator cbegin() const noexcept;

const_iterator cend() const noexcept;

返回的迭代器指向的元素不可被修改。

④crbegin() & crend()  （C++）：返回的迭代器指向的元素不可被修改

4、容量相关

①size_type size() const：获取容器中有效元素的个数

②size_type capacity() const：获取容器的容量

③empty：判断容器是否为空，是的话返回true

④void  resize(size_type n, value_type val = value_ type())：将容器有效元素的个数更新为n个，如果n大于原来容器的有效元素size，则多出来的元素使用val填充：

n <= size ：将容器的有效元素减少至n个（将size的值改为n）

n > size：

        n <= capacity：将容器的有效元素个数增加至n,多出来的n - size个元素使用val填充

        n > capacity：扩容，将容器的有效元素增加至n

⑤void  reserve(size_type n)：扩容

n <= capacity：直接忽略，不做处理

n > capacity：扩容

注意：vs下capacity是按照1.5倍增长的，g++是按照2倍增长的。reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。resize在开辟空间的同时还会进行初始化，影响size。 

5、元素访问 

①operator[]：通过下标的方式访问元素

reference operator[] (size_type n);

const_reference operator[] (size_type n)const;

②通过下标访问元素

reference at(size_type n);

const_reference at(size_type n) const;

二者的功能一直，都是访问下标n处的元素。唯一不同的是：处理异常情况的方式不同。operator[]->触发assert断言，at->抛出异常。

③front & back：front获取第一个元素，back获取最后一个元素。

④data  (C++11)：获取指向内部元素数组的指针

value_type* data() noexcept  |  const value_type* data() const noexcept;

6、修改相关

① push_back：在容器末尾插入一个元素

void push_back (const value_type& val);

②pop_back：将容器的最后一个元素删除

void pop_back()；对一个空的容器使用，pop_back会触发assert会触发assert断言，导致程序崩溃。

③insert

iterator insert(iterator position, const value_type&val)：在position位置插入元素val

iterator insert(iterator position,size_type n,  const value_type&val)：在position处插入n个元素val。

void insert (iterator position, InputIterator first, InpurIterator last)：在position处插入一段区间内的元素。

④erase

iterator erase(iterator position)：删除position位置的元素

iterator erase(iterator first, iterator last)：删除一段范围[first, last)内的元素

⑤swap：交换

⑥clear：清空容器的有效元素

迭代器失效问题 

什么是迭代器？

在STL中，容器的迭代器（Iterator）被作为容器元素对象或者IO流中的对象的位置指示器。因此，我们可以把迭代器理解为面向对象的指针（一种泛型指针或者通用指针），它不依赖元素的真是类型。

简而言之，迭代器是为了降低容器和泛型算法之间的耦合性而设计的，泛型算法的参数不是容器，而是迭代器。

容器迭代器的作用类似于数据库中的游标，它屏蔽了底层存储空间的不连续性，在上层使容器元素维持一种“逻辑连续”的假象。

迭代器与指针：

迭代器只是在某些操作上与我们学过的指针有些类似，但是迭代器并不是指针。

指针代表真正的内存地址，即对象在内存中的存储位置。

迭代器则代表元素在容器中的相对位置。

迭代器的分类和操作：

 具体分为5类：

支持的操作：

对于完全连续的容器（例如vector），没有必要重新定义迭代器类型，其元素的职责就可以完全直接充当迭代器。vector::iterator 和 const_iterator一般定义如下：

typedef T* iterator;
typedef const T* const_iterator;

 对于不连续存储或以其他方式存储的容器，例如list等，需要自己定义迭代器类（class），一般情况下它们是对元素指针的封装，即模拟指针。

常用的容器的迭代器类别：

为什么对迭代器分类？

 主要是泛型算法可以根据不同类别的迭代器具有不同能力来实现不同性能的版本，使得能力大的迭代器用于这些算法时具有更高的效率。

连续存储的容器，其元素的位置指示器有两种，下标和迭代器。下标的类型为unsigned int(size_t) ,有效范围是begin() ~ end()

这类容器的接口中都会提供相应的两种元素访问方法，典型的就是string和vector，它们都支持begin(), end(), operator[]操作

使用建议：

尽量使用迭代器类型，而不是使用指针。

只使用迭代器提供的标准操作，不使用任何非标准操作，以避免版本更新时出现不兼容的情况。

当不会改变容器中的元素值得时候，使用const迭代器 

迭代器失效问题即解决方法

迭代器失效是指容器底层存储发生变动时，原来指向容器中某个或某些元素得迭代器由于元素存储位置发生了改变而不再指向他们，从而成为无效的迭代器。

引起迭代器失效的主要操作：

改变容器容量得方法：reserve()、resize()、push_back()、pop_back()、insert()、erase()、clear()

一些泛型算法：sort()、copy()、replace()、remove()、unipue()等 

push_back()： 

 
	vector<int> v1;
	v1.push_back(1);
	vector<int>::iterator iter = v1.begin();
	for (int i = 0; i < 10; i++) {
		v1.push_back(2);
	}
	cout << *iter << endl;//迭代器失效
	system("pause");
	return 0;

解决方法：

①在调用上述操作后重新获取迭代器

	vector<int> v1;
	v1.push_back(1);
	auto iter = v1.begin();
	for (int i = 0; i < 10; i++) {
		v1.push_back(2);
	}
	iter = v1.begin();  //重新获取迭代器
	cout << *iter << endl;

②在修该容器前为其预留足够的空间避免存储空间重新分配。

erase()：

	vector<int> v2{ 1,2,3,4,5 };
	auto it = find(v2.begin(), v2.end(), 5);
	//删除末尾元素，此时迭代器失效
	v2.erase(it);
	cout << *it << endl;
	system("pause");
	return 0;

由于erase得返回值是被删除元素的下一个位置，所以会存在一种情况：删除末尾元素，这样该函数返回得就是end()的位置。

如何解决？

删除非末尾元素：使用语句iter = v.erase(iter)在删除元素的同时更新迭代器。

	vector<int> v2{ 1,2,3,4,5 };
	//找到并删除非末尾元素
	auto it = find(v2.begin(), v2.end(), 3);
	it = v2.erase(it);
 
	cout << *it << endl;

删除末尾元素：此时erase返回的是end()的位置，因此要想继续使用该迭代器，应该重新为其赋值为合法值。

	vector<int> v2{ 1,2,3,4,5 };
	//找到并删除非末尾元素
	//auto it = find(v2.begin(), v2.end(), 3);
	//it = v2.erase(it);
 
	auto it = find(v2.begin(), v2.end(), 5);
	v2.erase(it);
	it = v2.begin();
	cout << *it << endl;