我只是想知道 deque 是如何实现的,以及该实现中如何提供 push_front 和随机访问运算符等基本操作。
最佳答案
I just wanted to know how deque is implemented
找个借口做 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 |
+-------------------------------------------------------------+
how are the basic operations like
push_front
and random access operator are provided in that implementation?
首先,std::deque::push_front
,来自 libcxx:
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
这里应该是一个子数组的大小。
关于c++ - c++ STL中deque是如何实现的,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56321742/