2

我试图了解 STL 双端队列是如何在 libcxx 中实现的。

据我了解，libcxx STL 双端队列被实现为包含指向其他向量的指针的向量。这个包含指向其他向量的向量的名称为__map_并且类型为__split_buffer。现在这__split_buffer显然不是 a vector，因为它具有 a没有的push_front功能vector。我的问题是：这个push_front功能的效率如何？这是该push_front函数的源代码：

template <class _Tp, class _Allocator>
void
__split_buffer<_Tp, _Allocator>::push_front(const_reference __x)
{
    if (__begin_ == __first_)
    {
        if (__end_ < __end_cap())
        {
            difference_type __d = __end_cap() - __end_;
            __d = (__d + 1) / 2;
            __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
            __end_ += __d;
        }
        else
        {
            size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
            __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
            __t.__construct_at_end(move_iterator<pointer>(__begin_),
                                   move_iterator<pointer>(__end_));
            _VSTD::swap(__first_, __t.__first_);
            _VSTD::swap(__begin_, __t.__begin_);
            _VSTD::swap(__end_, __t.__end_);
            _VSTD::swap(__end_cap(), __t.__end_cap());
        }
    }
    __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x);
    --__begin_;
}

似乎它使用了move_backward根据 cppreference 标准实现简单地移动数组中的每个元素的函数，这在我看来效率极低。我假设它正在使用一些聪明的 O(1) move_backward 实现，但是我不知道如何找到它正在使用的实现。但是我想它可能真的使用了 O(n) 实现，并且每次调用只调用一次push_front它，将成本摊销到 O(1)，但最坏的情况仍然是 O(n)。

在第一种情况下，看起来整个数组首先__d移动__end_了__d? 这是否意味着该__end_变量会增加它与 之间的全部差异__end_cap()？

在第二种情况下，它看起来首先分配了__split_buffer两倍于 current 容量的a __split_buffer，然后它调用了__construct_at_end可能将整个 current 复制到新分配__map_的END__split_buffer的函数，这似乎是明智的，但也令人惊讶。这是明智的，因为您当然希望该push_front函数有多余的空间来添加新元素。但也令人惊讶，因为您为什么要添加到末尾而不是新分配__split_buffer函数的中间？这不会立即导致新分配__split_buffer的大小再次翻倍吗？

总而言之，我对该函数的理解是，push_front当前面没有更多空闲空间时调用__map_可能会导致以下两种情况之一发生：

  1. 分配了一个新__split_buffer的，其大小是旧的两倍，原始内容被复制到新的末尾__split_buffer（这肯定会导致新__split_buffer的大小立即翻倍？）
  2. 当前内容移动到__split_buffer. __split_buffer在必须重新分配之前，此操作只能发生一次。

我的理解正确吗？

4

0 回答 0