C++ STL 容器设计实现 -- deque
5、deque
deque 是双端队列（double-ended queue），其实现比较特殊，有多段地址连续的存储空间组成，整理布局如下：
- 每段地址连续内存成为一个 node
- map 是指针构成的数据，每个元素指向一个 node
- start 和 finish 是一个迭代器变量，分别指向第一个和最后一个 node
迭代器以 node 为单位
- cur 指向当前元素
- first 指向 node 第一个元素
- last 指向 node 最后一个元素的下一个地址
- node 指向 map 中相应位置，可以很方便找到前一个或者后一个 node
- node 计算如下
- 元素占用内存小于 512 字节，最大占用 512 字节
- 否则，默认分配一个元素大小的内存
/// stl_deque.h
_GLIBCXX_CONSTEXPR inline size_t
__deque_buf_size(size_t __size)
{ return (__size < _GLIBCXX_DEQUE_BUF_SIZE // 512
? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
5.1、_Deque_iterator
deque 的迭代器是 random access 类型的迭代器，四个成员如上图所示。
/// stl_deque.h
template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator
{
#if __cplusplus < 201103L
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
typedef _Tp* _Elt_pointer;
typedef _Tp** _Map_pointer;
#else
private:
template<typename _CvTp>
using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
public:
typedef __iter<_Tp> iterator;
typedef __iter<const _Tp> const_iterator;
typedef __ptr_rebind<_Ptr, _Tp> _Elt_pointer;
typedef __ptr_rebind<_Ptr, _Elt_pointer> _Map_pointer;
#endif
static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
{ return __deque_buf_size(sizeof(_Tp)); }
typedef std::random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Deque_iterator _Self;
_Elt_pointer _M_cur;
_Elt_pointer _M_first;
_Elt_pointer _M_last;
_Map_pointer _M_node;
/* ... */
void
_M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
{
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
/* ... */
};
_Deque_iterator 进行 ++ 或者 -- 操作时，当 cur 移动到 last 或回退到 first 时，自动跳转到下一个 node 或者上一个 node
/// stl_deque.h
_Self&
operator++() _GLIBCXX_NOEXCEPT
{
++_M_cur;
if (_M_cur == _M_last) // 进入下一个 node
{
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
_Self&
operator--() _GLIBCXX_NOEXCEPT
{
if (_M_cur == _M_first) // 进入上一个 node
{
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
运算符 += 或者 -= 也是同样的道理。
/// stl_deque.h
_Self&
operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else
{
const difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1)
/ _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first + (__offset - __node_offset
* difference_type(_S_buffer_size()));
}
return *this;
}
_GLIBCXX_NODISCARD
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return *(*this + __n); }
5.2、_Deque_base::_Deque_impl_data
_Deque_impl_data 封装了 deque 的数据结构 map。
/// stl_deque.h
struct _Deque_impl_data
{
_Map_pointer _M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
_Deque_impl_data() _GLIBCXX_NOEXCEPT
: _M_map(), _M_map_size(), _M_start(), _M_finish()
{ }
/* ... */
};
5.3、_Deque_base::_Deque_impl
_Deque_impl 继承 _Deque_impl_data 和 内存分配器 _Tp_alloc_type。采用继承的方法，是避免空类（内存分配器通常没有数据成员）引入内存消耗。
/// stl_deque.h
// This struct encapsulates the implementation of the std::deque
// standard container and at the same time makes use of the EBO
// for empty allocators.
struct _Deque_impl
: public _Tp_alloc_type, public _Deque_impl_data
{
/* ... */
};
5.4、_Deque_base
_Deque_base 只有一个 _Deque_impl 成员变量，_Deque_base 另外负责 node 和 map 的内存分配与释放。
/// stl_deque.h
template<typename _Tp, typename _Alloc>
class _Deque_base
{
protected:
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<_Tp>::other _Tp_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits;
typedef typename _Alloc_traits::pointer _Ptr;
typedef typename _Alloc_traits::const_pointer _Ptr_const;
typedef typename _Alloc_traits::template rebind<_Ptr>::other
_Map_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
typedef _Alloc allocator_type;
allocator_type
get_allocator() const _GLIBCXX_NOEXCEPT
{ return allocator_type(_M_get_Tp_allocator()); }
typedef _Deque_iterator<_Tp, _Tp&, _Ptr> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const> const_iterator;
/* ... */
typedef typename iterator::_Map_pointer _Map_pointer;
/* ... */
enum { _S_initial_map_size = 8 };
_Deque_impl _M_impl;
};
成员函数 _M_allocate_node() 和 _M_deallocate_node() 用于分配和释放一个 node 内存。
/// stl_deque.h
_Ptr
_M_allocate_node()
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
}
void
_M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
{
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
_Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
}
_M_create_nodes() 和 _M_destroy_nodes() 分别调用 _M_allocate_node() 和 _M_deallocate_node() 函数，用于申请或者释放多个 node 的内存。
/// stl_deque.h
template<typename _Tp, typename _Alloc>
void
_Deque_base<_Tp, _Alloc>::
_M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
{
_Map_pointer __cur;
__try
{
for (__cur = __nstart; __cur < __nfinish; ++__cur)
*__cur = this->_M_allocate_node();
}
__catch(...)
{
_M_destroy_nodes(__nstart, __cur);
__throw_exception_again;
}
}
template<typename _Tp, typename _Alloc>
void
_Deque_base<_Tp, _Alloc>::
_M_destroy_nodes(_Map_pointer __nstart,
_Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
{
for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
_M_deallocate_node(*__n);
}
成员函数 _M_allocate_map() 和 _M_deallocate_map() 用于分配和释放 map 的内存。
/// stl_deque.h
_Map_pointer
_M_allocate_map(size_t __n)
{
_Map_alloc_type __map_alloc = _M_get_map_allocator();
return _Map_alloc_traits::allocate(__map_alloc, __n);
}
void
_M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
{
_Map_alloc_type __map_alloc = _M_get_map_allocator();
_Map_alloc_traits::deallocate(__map_alloc, __p, __n);
}
_M_initialize_map() 函数用于初始化 map，包括申请 node 内存。
- 1）计算 node 个数
- 2）申请 map 内存（至少额外申请 2 个空间，用于应对未来的元素插入）
- 3）申请 node
- 4）初始化 _Deque_impl_data 成员变量
/// deque.tcc
template<typename _Tp, typename _Alloc>
void
_Deque_base<_Tp, _Alloc>::
_M_initialize_map(size_t __num_elements)
{
const size_t __num_nodes = (__num_elements / __deque_buf_size(sizeof(_Tp))
+ 1);
this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
size_t(__num_nodes + 2)); // 2 个额外空间
this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
// For "small" maps (needing less than _M_map_size nodes), allocation
// starts in the middle elements and grows outwards. So nstart may be
// the beginning of _M_map, but for small maps it may be as far in as
// _M_map+3.
_Map_pointer __nstart = (this->_M_impl._M_map
+ (this->_M_impl._M_map_size - __num_nodes) / 2);
_Map_pointer __nfinish = __nstart + __num_nodes;
__try
{ _M_create_nodes(__nstart, __nfinish); }
__catch(...)
{
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = _Map_pointer();
this->_M_impl._M_map_size = 0;
__throw_exception_again;
}
this->_M_impl._M_start._M_set_node(__nstart);
this->_M_impl._M_finish._M_set_node(__nfinish - 1);
this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
+ __num_elements
% __deque_buf_size(sizeof(_Tp))); // 最后一个元素下一个位置
}
5.5、std::deque
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc>
{
typedef _Deque_base<_Tp, _Alloc> _Base;
typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
typedef typename _Base::_Alloc_traits _Alloc_traits;
typedef typename _Base::_Map_pointer _Map_pointer;
public:
typedef _Tp value_type;
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
/* ... */
};
deque 重点分析插入元素的几个成员函数，push_back/front，pop_back/front，insert。
5.5.1、push_back/front
如果预留有空间，直接插入，否则需要申请 node 或者重新扩展 map。push_back() 和 push_front() 分别调用 _M_push_back_aux() 和 _M_push_front_aux() 用于处理预留空间消耗完的情况。
/// stl_deque.h
void
push_back(const value_type& __x)
{
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_last - 1)
{ // 直接插入
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_finish._M_cur, __x);
++this->_M_impl._M_finish._M_cur;
}
else
_M_push_back_aux(__x);
}
void
push_front(const value_type& __x)
{
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{ // 直接插入
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_start._M_cur - 1,
__x);
--this->_M_impl._M_start._M_cur;
}
else
_M_push_front_aux(__x);
}
_M_push_back_aux() 和 _M_push_front_aux() 两个函数原理相同，首先判断是否需要拓展 map，必要时先拓展 map，然后申请一个 node，最后插入新增元素。
/// deque.tcc
template<typename _Tp, typename _Alloc>
#if __cplusplus >= 201103L
template<typename... _Args>
void
deque<_Tp, _Alloc>::
_M_push_back_aux(_Args&&... __args)
#else
/* ... */
#endif
{
if (size() == max_size())
__throw_length_error(
__N("cannot create std::deque larger than max_size()"));
_M_reserve_map_at_back(); // 必要时拓展 map
*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); // 申请 node
__try
{
#if __cplusplus >= 201103L
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_finish._M_cur,
std::forward<_Args>(__args)...); // 插入元素
#else
/* ... */
#endif
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
+ 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
}
__catch(...)
{
_M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
__throw_exception_again;
}
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
template<typename _Tp, typename _Alloc>
#if __cplusplus >= 201103L
template<typename... _Args>
void
deque<_Tp, _Alloc>::
_M_push_front_aux(_Args&&... __args)
#else
/* ... */
#endif
{
if (size() == max_size())
__throw_length_error(
__N("cannot create std::deque larger than max_size()"));
_M_reserve_map_at_front(); // 必要时拓展 map
*(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
__try
{
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
- 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
#if __cplusplus >= 201103L
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_start._M_cur,
std::forward<_Args>(__args)...); // 插入元素
#else
/* ... */
#endif
}
__catch(...)
{
++this->_M_impl._M_start;
_M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
__throw_exception_again;
}
}
_M_reserve_map_at_back() 和 _M_reserve_map_at_front() 都调用 _M_reallocate_map() 函数拓展 map。
/// deque.tcc
void
_M_reserve_map_at_back(size_type __nodes_to_add = 1)
{
if (__nodes_to_add + 1 > this->_M_impl._M_map_size
- (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void
_M_reserve_map_at_front(size_type __nodes_to_add = 1)
{
if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
- this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, true);
}
_M_reallocate_map() 函数定义如下，如果 map 预留的空间足够大（2 倍），不需要拓展 map，只需要移动 nodes 就可以了，否则旧重新申请一个 map，新 map 的大小至少是原来的两倍 + 2。
/// deque.tcc
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
const size_type __old_num_nodes
= this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
{ // 不需要拓展 map，只需要移动 nodes
__new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
- __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < this->_M_impl._M_start._M_node)
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart);
else
std::copy_backward(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else
{ // 拓展 map
size_type __new_map_size = this->_M_impl._M_map_size
+ std::max(this->_M_impl._M_map_size,
__nodes_to_add) + 2; // 新 map 的大小
// 申请新 map
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart); // 释放原来 map
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
5.5.2、pop_back/front
相对于 push_back/front，pop_back/front 就比较简单，只需要考虑 node 的释放，不需要对 map 进行收缩。
/// stl_deque.h
void
pop_back() _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_first)
{ // 在 [_M_first, _M_cur) 中
--this->_M_impl._M_finish._M_cur;
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_finish._M_cur);
}
else
_M_pop_back_aux();
}
void
pop_front() _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
if (this->_M_impl._M_start._M_cur
!= this->_M_impl._M_start._M_last - 1)
{ // 在 [_M_cur, _M_last) 中
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_start._M_cur);
++this->_M_impl._M_start._M_cur;
}
else
_M_pop_front_aux();
}
_M_pop_back_aux() 和 _M_pop_front_aux() 也比较简单
/// deque.tcc
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::
_M_pop_back_aux()
{
_M_deallocate_node(this->_M_impl._M_finish._M_first); // 释放 node
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_finish._M_cur); // 析构元素
}
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::
_M_pop_front_aux()
{
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_start._M_cur); // 析构元素
_M_deallocate_node(this->_M_impl._M_start._M_first);
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); // 释放 node
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
}
5.5.3、insert
deque 支持在任意位置插入元素，insert() 的实现比较复杂。
首先是插入单个元素，比如 insert(pos, val)
- 插入位置在 begin()，调用 push_front() 函数插入
- 插入位置在 end()，调用 push_end() 函数插入
- 调用 _M_insert_aux() 函数处理
/// deque.tcc
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
/* ... */
#endif
{
if (__position._M_cur == this->_M_impl._M_start._M_cur)
{ // 插入位置在 begin()
push_front(__x);
return this->_M_impl._M_start;
}
else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
{ // 插入位置在 end()
push_back(__x);
iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return __tmp;
}
else
return _M_insert_aux(__position._M_const_cast(), __x);
}
_M_insert_aux() 先移动元素，腾出插入位置，然后插入元素。
/// deque.tcc
template<typename _Tp, typename _Alloc>
#if __cplusplus >= 201103L
template<typename... _Args>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, _Args&&... __args)
{
value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
#else
/* ... */
#endif
difference_type __index = __pos - this->_M_impl._M_start;
if (static_cast<size_type>(__index) < size() / 2)
{ // 移动前半部
push_front(_GLIBCXX_MOVE(front())); // 赋值第一个元素
iterator __front1 = this->_M_impl._M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = this->_M_impl._M_start + __index;
iterator __pos1 = __pos;
++__pos1; // 将 [front2, pos1) 元素移动到 [front1, )
_GLIBCXX_MOVE3(__front2, __pos1, __front1);
}
else
{ // 移动后半部
push_back(_GLIBCXX_MOVE(back()));
iterator __back1 = this->_M_impl._M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = this->_M_impl._M_start + __index;
_GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
}
*__pos = _GLIBCXX_MOVE(__x_copy);
return __pos;
}
然后插入多个相同的值，比如 insert(pos, n, val)
/// stl_deque.h
iterator
insert(const_iterator __position, size_type __n, const value_type& __x)
{
difference_type __offset = __position - cbegin();
_M_fill_insert(__position._M_const_cast(), __n, __x);
return begin() + __offset;
}
_M_fill_insert() 处理逻辑是
- 插入位置在 begin()，在 begin() 插入 n 个元素
- 插入位置在 end()，在 end() 后面插入 n 个元素
- 调用 _M_insert_aux() 处理，先整体移动出 n 个位置的空间，再插入
/// deque.tcc
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
{
if (__pos._M_cur == this->_M_impl._M_start._M_cur)
{ // 插入位置在 begin()，先申请空间，在赋值
iterator __new_start = _M_reserve_elements_at_front(__n);
__try
{
std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
__x, _M_get_Tp_allocator());
this->_M_impl._M_start = __new_start;
}
__catch(...)
{
_M_destroy_nodes(__new_start._M_node,
this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
{ // 插入位置在 end()
iterator __new_finish = _M_reserve_elements_at_back(__n);
__try
{
std::__uninitialized_fill_a(this->_M_impl._M_finish,
__new_finish, __x,
_M_get_Tp_allocator());
this->_M_impl._M_finish = __new_finish;
}
__catch(...)
{
_M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
}
else
_M_insert_aux(__pos, __n, __x);
}
_M_insert_aux() 定义如下，根据插入位置，决定移动较少部分元素，腾出 n 个元素的空间。
/// deque.tcc
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
{
const difference_type __elems_before = __pos - this->_M_impl._M_start;
const size_type __length = this->size();
value_type __x_copy = __x;
if (__elems_before < difference_type(__length / 2))
{ // 移动前半部
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = this->_M_impl._M_start;
__pos = this->_M_impl._M_start + __elems_before;
__try
{
if (__elems_before >= difference_type(__n))
{
iterator __start_n = (this->_M_impl._M_start
+ difference_type(__n));
std::__uninitialized_move_a(this->_M_impl._M_start,
__start_n, __new_start,
_M_get_Tp_allocator());
this->_M_impl._M_start = __new_start;
_GLIBCXX_MOVE3(__start_n, __pos, __old_start);
std::fill(__pos - difference_type(__n), __pos, __x_copy);
}
else
{
std::__uninitialized_move_fill(this->_M_impl._M_start,
__pos, __new_start,
this->_M_impl._M_start,
__x_copy,
_M_get_Tp_allocator());
this->_M_impl._M_start = __new_start;
std::fill(__old_start, __pos, __x_copy);
}
}
__catch(...)
{
_M_destroy_nodes(__new_start._M_node,
this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
else
{ // 移动后半部
iterator __new_finish = _M_reserve_elements_at_back(__n);
iterator __old_finish = this->_M_impl._M_finish;
const difference_type __elems_after =
difference_type(__length) - __elems_before;
__pos = this->_M_impl._M_finish - __elems_after;
__try
{
if (__elems_after > difference_type(__n))
{
iterator __finish_n = (this->_M_impl._M_finish
- difference_type(__n));
std::__uninitialized_move_a(__finish_n,
this->_M_impl._M_finish,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish = __new_finish;
_GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
std::fill(__pos, __pos + difference_type(__n), __x_copy);
}
else
{
std::__uninitialized_fill_move(this->_M_impl._M_finish,
__pos + difference_type(__n),
__x_copy, __pos,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish = __new_finish;
std::fill(__pos, __old_finish, __x_copy);
}
}
__catch(...)
{
_M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
}
}
最后一种是插入迭代器指向的区间元素，比如 insert(pos, begin, end)
/// stl_deque.h
template<typename _InputIterator,
typename = std::_RequireInputIter<_InputIterator>>
iterator
insert(const_iterator __position, _InputIterator __first,
_InputIterator __last)
{
difference_type __offset = __position - cbegin();
_M_range_insert_aux(__position._M_const_cast(), __first, __last,
std::__iterator_category(__first));
return begin() + __offset;
}
_M_range_insert_aux() 需要区分迭代器类型，如果是 input_iterator_tag，调用 std::copy() 单个元素进行插入。否则处理方式和 _M_fill_insert() 函数类似。
/// deque.tcc
template <typename _Tp, typename _Alloc>
template <typename _InputIterator>
void
deque<_Tp, _Alloc>::
_M_range_insert_aux(iterator __pos,
_InputIterator __first, _InputIterator __last,
std::input_iterator_tag)
{ std::copy(__first, __last, std::inserter(*this, __pos)); }
template <typename _Tp, typename _Alloc>
template <typename _ForwardIterator>
void
deque<_Tp, _Alloc>::
_M_range_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
std::forward_iterator_tag)
{
const size_type __n = std::distance(__first, __last);
if (__pos._M_cur == this->_M_impl._M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
__try
{
std::__uninitialized_copy_a(__first, __last, __new_start,
_M_get_Tp_allocator());
this->_M_impl._M_start = __new_start;
}
__catch(...)
{
_M_destroy_nodes(__new_start._M_node,
this->_M_impl._M_start._M_node);
__throw_exception_again;
}
}
else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
__try
{
std::__uninitialized_copy_a(__first, __last,
this->_M_impl._M_finish,
_M_get_Tp_allocator());
this->_M_impl._M_finish = __new_finish;
}
__catch(...)
{
_M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
__throw_exception_again;
}
}
else
_M_insert_aux(__pos, __first, __last, __n);
}
_M_insert_aux() 函数处理方法类似，根据插入位置，决定移动较少部分元素，腾出 n 个元素的空间，然后将 [first, last) 拷贝 n 个元素到 deque。
欢迎关注公众号“源知源为”，阅读更多技术干货
#STL#C/C++基础 文章被收录于专栏
C/C++ 语言基础
投递招商银行·招银网络科技等公司10个岗位 >
滴滴二面48人在聊