C++ STL 容器 vector

1. vector 对象

我们在 main 函数中使用默认构造函数创建一个 vector<int> vec; 对象

vector<int> vec;

这个对象的大小为 24 字节，3 个指针的大小

对象的内部表示如图所示
在这里插入图片描述
这是源码中的定义

struct _Vector_impl_data {
pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;
// ...
}

这三个指针是什么含义后面再介绍

这三个指针变量本身是在栈上的，它们的值，也就是地址，是堆上的地址

也就是说，vec 对象在栈上，它通过这三个指针维护了堆上的一块连续空间，来实现一个连续、动态的数组

2. vector 大小 size 和容量 capacity

想要了解 vec 的底层模型就必须先了解这两个概念

size：是指数组元素的个数
capacity：是指当前可用空间能够容纳的元素的个数

上面默认构造的 vec 对象的大小和容量都为 0

现在我们再看一下 vec 对象中的三个指针的含义，分别为：

start：指向第一个元素
finish：指向最后一个元素的下一个位置
end_of_storage：指向当前可用空间的下一个位置

现在我们改变一下 vec 对象的大小和容量

vec.reserve(4);
vec.resize(2);

现在 vec 的大小是 2，容量是 4

看下面的图就清楚大小和容量了
在这里插入图片描述
上图所示的空间是堆上的空间，vec 容器所管理的元素是在堆上的

start 和 finish 之间就是我们口头说的数组

start 和 end_of_storage 之间则是当前可用的空间，一共有 4 个容量，我们已经使用了 2 个元素了，还能再使用 2 个，如果使用完了，再向这个 vec 对象添加元素，就需要进行动态扩充了

3. vector 成员函数

通过上面两张图，相信大家已经大概了解 vector 在内存中的模型了

vec 对象通过这三个指针来完成动态数组的功能，下面来看看 vector 提供的成员方法是如何实现的吧

3.1 迭代器

我们首先搞懂 vector 的迭代器是怎么实现的

vector 迭代器是一个随机访问迭代器，需要提供 ++、- - 、+ i、- i、[ i ] 、比较等操作

这样的话完全可以使用指针来实现

1. __normal_iterator

在 vector 定义里，gcc 中是这样定义的

typedef __normal_iterator<pointer, vector> iterator;
typedef __normal_iterator<const_pointer, vector> const_iterator;

其中的 pointer 其实就是 T*

来看看这个 __normal_iterator

template<typename _Iterator, typename _Container>
class __normal_iterator
{
protected:
  _Iterator _M_current;
  // ...
}

内部就是一个 T* 指针

下面是部分它提供的接口

_GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
: _M_current(_Iterator()) { }

通过 T* 指针来构造

_GLIBCXX20_CONSTEXPR
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *_M_current; }

_GLIBCXX20_CONSTEXPR
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return _M_current; }

_GLIBCXX20_CONSTEXPR
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return _M_current[__n]; }

_GLIBCXX20_CONSTEXPR
__normal_iterator&
operator++() _GLIBCXX_NOEXCEPT
{
	++_M_current;
	return *this;
}

// ...

可以看到，其实就是对普通指针 T* 的封装

2. vector 迭代器

那么从 vector 中得到迭代器访问数组，其实就是得到 vector 中的 start 和 finish 指针了，这两个指针之间就是当前管理的元素

iterator begin() 
{ return iterator(start); }

iterator end()
{ return iterator(finish); }

所以 end( ) 不是最后一个元素，而是最后元素的下一个

得到了 iterator 就可以像普通指针一样访问这个数组了

在这里插入图片描述

3.2 容量

通过上面的图，我们很容易想到 size( ) 和 capacity( ) 如何实现

size 只需要 start 和 finish 两个指针相减

size_t size() const 
{ return size_t(finish - start); }

capacity 只需要 start 和 end_of_storage 两个指针相减

size_t capacity() const 
{ return size_t(end_of_storage - start); }

在这里插入图片描述

empty( ) 用来检查 vector 是否为空，是指容器管理的元素个数是否为 0

bool empty() const 
{ return start == finish; }

// 源码是这样，一个意思
_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
bool
empty() const _GLIBCXX_NOEXCEPT
{ return begin() == end(); }

3.3 元素访问

可以通过下标和 at 函数来访问 vector 中的元素

reference operator[](size_t n)
{ return *(start + n); }

reference at(size_t n)
{
	if (n >= this->size())
	  __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
				       "(which is %zu) >= this->size() "
				       "(which is %zu)"),
				   n, this->size());
	return (*this)[n];
}

[ ] 和 at 区别就是 at 会进行越界检查，越界会抛出异常

可以使用 front 和 back 来访问第一个和最后一个元素

reference front()
{
	__glibcxx_requires_nonempty();
	return *begin();
}

reference back()
{
	__glibcxx_requires_nonempty();
	return *(end() - 1);
}

最后一个元素是 end() - 1 啦

最后 vector 还提供了底层指针的获取，就是 start，指向堆空间中的第一个元素

T* data()
{ return empty() ? nullptr : start; }

3.4 插入

后面的函数涉及对象的创建和销毁，默认情况下，STL 容器都是通过 std::allocator 来实现的，主要是这 4 个步骤

申请空间 allocate
构造对象 construct
析构对象 destroy
释放空间 deallocate

这 4 个步骤其实就对应了 new 和 delete。简单实现如下：

1.申请空间使用 operator new，里面调用 malloc 来申请空间

template <class T>
T* allocate()
{
  return static_cast<T*>(::operator new(sizeof(T)));
}

2.构造对象调用对象的构造函数

template <class Ty>
void construct(Ty* ptr)
{
  ::new ((void*)ptr) Ty();
}

template <class Ty1, class Ty2>
void construct(Ty1* ptr, const Ty2& value)
{
  ::new ((void*)ptr) Ty1(value);
}

template <class Ty, class... Args>
void construct(Ty* ptr, Args&&... args)
{
  ::new ((void*)ptr) Ty(mystl::forward<Args>(args)...);
}

3.析构对象调用对象的析构函数

template <class Ty>
void destroy(Ty* ptr)
{
  ptr->~Ty();
}

template <class ForwardIter>
void destroy(ForwardIter first, ForwardIter last)
{
  for (; first != last; ++first)
    destroy(&*first);
}

4.释放空间使用 operator delete ，里面调用 free 来释放空间

template <class T>
void deallocate(T* ptr)
{
  if (ptr == nullptr)
    return;
  ::operator delete(ptr);
}

析构函数可以直接通过指针调用，但构造函数不能，需要使用 operator new(size_t, void* p) 来调用，可以在 p 这个地址上构造一个对象

下面是 vector 常用的函数实现（仅提供关键信息，具体请自行查看源码）

1. push_back

void push_back(const T& x)
{
	if (finish != end_of_storage)
	{
		construct(finish, x);
		++finish;
	}
	else
		//realloc_insert
		//...
}

在 finish 上构造一个新对象

2. pop_back

void pop_back()
{
	__glibcxx_requires_nonempty();
	--finish;
	destroy(finish);
}

从实现上便可以看出，vector 在末尾插入或移除元素复杂度——均摊常数 O(1)

3. insert

iterator insert(const_iterator __position, const T& __x)
{
	const size_t __n = __position - begin();
	if (finish != end_of_storage)
	{
		if (__position == end())
		{
			construct(finish, __x);
			++finish;
		}
		else
		{

			const auto __pos = begin() + (__position - cbegin());
			// __x could be an existing element of this vector, so make a
			// copy of it before _M_insert_aux moves elements around.
			_Temporary_value __x_copy(this, __x);
			_M_insert_aux(__pos, std::move(__x_copy._M_val()));
		}
	}
	else
		_M_realloc_insert(begin() + (__position - cbegin()), __x);
	return iterator(start + __n);
}

void _M_insert_aux(iterator __position, _Arg&& __arg)
{
	construct(finish, _GLIBCXX_MOVE(*(finish - 1)));
	++finish;
	
	_GLIBCXX_MOVE_BACKWARD3(__position.base(),
							finish - 2,
							finish - 1);

	*__position = std::forward<_Arg>(__arg);
}

其中 _GLIBCXX_MOVE_BACKWARD3 最后是这样的

__copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
{
  while (__first != __last)
    *--__result = *--__last;
  return __result;
}

所以在中间插入元素，后面的元素需要后移，与到 vector 结尾的距离成线性 O(n)

3.5 删除

1. clear

void clear()
{
	destroy(start, finish);
	finish = start;
}

clear 影响 size ，不影响 capacity

2. erase

iterator erase(const_iterator __position)
{ return _M_erase(begin() + (__position - cbegin())); }

iterator _M_erase(iterator __position)
{
	if (__position + 1 != end())
		_GLIBCXX_MOVE3(__position + 1, end(), __position);
	--finish;
	destroy(finish);
	return __position;
}

其中 _GLIBCXX_MOVE3 最后可能是这样

__copy_m(_II __first, _II __last, _OI __result)
{
	typedef typename iterator_traits<_II>::difference_type _Distance;
	for(_Distance __n = __last - __first; __n > 0; --__n)
	{
		*__result = std::move(*__first);
		++__first;
		++__result;
	}
	return __result;
}

仔细分析一下，要 erase 的元素是先通过 move 获得后面一个元素的资源，被析构的是最后一个元素，当然，析构之前这个元素的资源已经转移给前一个了

所以，vector 插入或移除元素复杂度——与到 vector 结尾的距离成线性 O(n)

3.6 动态扩充与收缩

1. reserve

void reserve(size_type __n)
{
	if (__n > max_size())
		__throw_length_error(__N("vector::reserve"));
	if (capacity() < __n)
	{
		const size_type __old_size = size();
		pointer __tmp;
		#if __cplusplus >= 201103L
		if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
		  {
		  	// 申请新空间
		    __tmp = this->_M_allocate(__n);
		    // 移动构造，析构旧元素（此时旧元素资源已转移）
		    _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
		  __tmp, _M_get_Tp_allocator());
		  }
		else
		#endif
		  {
		  	// 申请新空间，拷贝构造
		    __tmp = _M_allocate_and_copy(__n,
		_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
		_GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
			// 析构旧元素
		    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
		    _M_get_Tp_allocator());
		  }
		_GLIBCXX_ASAN_ANNOTATE_REINIT;
		
		// 释放旧空间
		_M_deallocate(this->_M_impl._M_start,
		this->_M_impl._M_end_of_storage
		- this->_M_impl._M_start);
		
		this->_M_impl._M_start = __tmp;
		this->_M_impl._M_finish = __tmp + __old_size;
		this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
	}
}

vector 的扩容就是三点

申请新空间
转移元素到新空间（构造新元素，析构旧元素）
释放旧空间

debug 发现，代码中 if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) 这个条件判断应该是元素是否支持移动，大概是这样

可移动则走第一个分支，先分配需要的全部空间，然后通过移动将元素转移，具体是遍历，在新空间移动构造一个元素（获得旧空间一个元素的资源），析构旧空间的一个元素，即 move, destroy, move, destroy, …

否则走第二个分支，_M_allocate_and_copy 内部是先分配需要的全部空间，然后挨个拷贝过去，拷贝完毕使用 std::_Destroy 析构旧空间元素，即 copy, copy … destroy, destroy,…

所以转移元素时，该类型 T 支持移动则调用移动，否则复制

具体如何移动请看下面

// _S_relocate 调用
static pointer
_S_do_relocate(pointer __first, pointer __last, pointer __result,
_Tp_alloc_type& __alloc, true_type) noexcept
{
	return std::__relocate_a(__first, __last, __result, __alloc);
}
// __relocate_a 调用
inline _ForwardIterator
__relocate_a_1(_InputIterator __first, _InputIterator __last,
 _ForwardIterator __result, _Allocator& __alloc)
{
  //...
  _ForwardIterator __cur = __result;
  // 遍历，转移
  for (; __first != __last; ++__first, (void)++__cur)
	std::__relocate_object_a(std::__addressof(*__cur),
	 std::__addressof(*__first), __alloc);
  return __cur;
}

inline void
__relocate_object_a(_Tp* __restrict __dest, _Up* __restrict __orig,
_Allocator& __alloc)
{
  typedef std::allocator_traits<_Allocator> __traits;
  // 构造
  __traits::construct(__alloc, __dest, std::move(*__orig));
  // 析构
  __traits::destroy(__alloc, std::__addressof(*__orig));
}

每一次都是使用 move 将一个 orig 转移到 dest，然后析构 orig

2. shrink_to_fit

void shrink_to_fit()
{ _M_shrink_to_fit(); }

bool _M_shrink_to_fit()
{
	if (capacity() == size())
		return false;
	_GLIBCXX_ASAN_ANNOTATE_REINIT;
	return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
}

bool _S_do_it(_Tp& __c) noexcept
{
	#if __cpp_exceptions
	try
	{
		// 与临时对象交换
		_Tp(__make_move_if_noexcept_iterator(__c.begin()),
		__make_move_if_noexcept_iterator(__c.end()),
		__c.get_allocator()).swap(__c);
		return true;
	}
	catch(...)
		{ return false; }
	#else
	return false;
	#endif
}

shrink_to_fit 就是创建一个临时 vector ，然后进行交换，最后 size 和 capacity 相等

3. resize

void resize(size_type __new_size)
{
	if (__new_size > size())
		_M_default_append(__new_size - size());
	else if (__new_size < size())
		_M_erase_at_end(this->_M_impl._M_start + __new_size);
}

参数 size 大于原 size 时，末尾添加

参数 size 小于原 size 时，末尾删除

4. vector 迭代器失效问题

首先，迭代器失效到底是什么意思？是迭代器指向的地址不能访问了吗？

个人认为，迭代器失效是指，一开始我们从 vector 中获得一个迭代器，然后进行一些操作（插入、删除等等），后面再使用这个迭代器可能会把我们想做的事情搞砸，这个迭代器指向的元素已经不是我们想当然认为的元素了

vector 因重新分配的特点（元素转移到新空间了），迭代器失效的问题较多：

插入元素

末尾插入：size < capacity 时，首迭代器不失效尾迭代失效（未重新分配空间），size == capacity 时，所有迭代器均失效（需要重新分配空间）

中间插入：size < capacity 时，首迭代器不失效但插入元素之后所有迭代器失效，size == capacity 时，所有迭代器均失效
删除元素

末尾删除：只有尾迭代器失效

中间删除：删除位置之后所有迭代器失效

总结

vector 的特点就是它的重新分配机制了，这样实现了动态数组的功能，但另一方面，需要转移元素到新空间，释放旧空间造成了一定的开销，这就要求我们善于利用 reserve 以及移动来减少一些不必要的开销了

其他补充

这里记录一个例子，怎么正确地删除 vector 容器中的元素

vector<int> vec(6);
std::iota(vec.begin(), vec.end(), 1);

auto it = vec.begin();
for (; it != vec.end(); it++) {
    // if (...)
    vec.erase(it);
}
for (auto n : vec) {
    cout << n << endl;
}

结果是

2
4
6

要正确实现需要这样修改

for (; it != vec.end(); ) {
    // if (...)
    it = vec.erase(it);
}

这里要搞明白 erase 的返回值是什么，erase 返回的迭代器还是指向了要 erase 的那个元素的位置，只不过现在这个元素的内容其实是之前的下一个元素