如何在c++ stl中实现deque
如何在c++ stl中实现deque
提问于 2019-05-27 07:43:27
我只想知道deque是如何实现的，以及在该实现中如何提供诸如、push_front和随机访问操作符之类的基本操作。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-05-27 08:15:05
我只想知道deque是如何实现的
做ASCII艺术的借口总是很好的：
+-------------------------------------------------------------+
| std::deque<int> |
| |
| subarrays: |
| +---------------------------------------------------------+ |
| | | | | | | |
| | int(*)[8] | int(*)[8] | int(*)[8] |int(*)[8]|int(*)[8] | |
| | | | | | | |
| +---------------------------------------------------------+ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| / \ |
| - - |
| +------------------------------+ |
| | ?, ?, 42, 43, 50, ?, ?, ?, ? | |
| +------------------------------+ |
| |
| additional state: |
| |
| - pointer to begin of the subarrays |
| - current capacity and size |
| - pointer to current begin and end |
+-------------------------------------------------------------+ 在该实现中如何提供诸如
push_front和随机访问操作符之类的基本操作？
首先，来自libcxx的std::deque::push_front：
template <class _Tp, class _Allocator>
void
deque<_Tp, _Allocator>::push_front(const value_type& __v)
{
allocator_type& __a = __base::__alloc();
if (__front_spare() == 0)
__add_front_capacity();
__alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
--__base::__start_;
++__base::size();
}这显然会检查前面已经分配的内存是否可以容纳额外的元素。如果没有，它就分配。然后，主要工作转移到迭代器上：_VSTD::addressof(*--__base::begin())位于容器当前前端元素之前的一个位置，这个地址被传递给分配器，通过复制v构造一个新的元素(默认的分配器肯定会执行布局-new)。
现在随机进入。同样来自libcxx，std::deque::operator[] (非const版本)是
template <class _Tp, class _Allocator>
inline
typename deque<_Tp, _Allocator>::reference
deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
{
size_type __p = __base::__start_ + __i;
return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
}这很大程度上计算了相对于某个开始索引的索引，然后确定子数组和相对于子数组开始的索引。这里的__base::__block_size应该是一个子数组的大小。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56321742
复制相关文章
相似问题
腾讯云开发者
