[cfe-dev] deque --> __add_back_capacity / I think that it could be better (but I'm not sure)

Eric Fiselier via cfe-dev cfe-dev at lists.llvm.org
Fri Apr 6 01:50:56 PDT 2018


It's important to point out the code you cite is from a function called
`__add_back_capacity()`, used to expand the deque in functions like
push_back when more capacity is needed.
`__add_front_capacity()` which does the opposite, and is used by
`push_front`.

Additionally, both __front_capacity and __back_capacity will "steal" unused
capacity from the other end of the deque.

For these reason I don't see the advantage in achieving equilibrium between
the front and back. Perhaps you could
elaborate further? Or, better yet, provide some benchmarks?

/Eric


On Thu, Apr 5, 2018 at 2:28 PM, Christiano SA via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> Project: libc++
> file: include/deque
> line: 2422-2473
>
> Code:
>
>     else
>     {
>         __split_buffer<pointer, typename __base::__pointer_allocator&>
>             __buf(max<size_type>(2* __base::__map_.capacity(), 1),
>                   __base::__map_.size(),
>                   __base::__map_.__alloc());
>
>         typedef __allocator_destructor<_Allocator> _Dp;
>         unique_ptr<pointer, _Dp> __hold(
>             __alloc_traits::allocate(__a, __base::__block_size),
>                 _Dp(__a, __base::__block_size));
>         __buf.push_back(__hold.get());
>         __hold.release();
>
>         for (typename __base::__map_pointer __i = __base::__map_.end();
>                 __i != __base::__map_.begin();)
>             __buf.push_front(*--__i);
>         _VSTD::swap(__base::__map_.__first_, __buf.__first_);
>         _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
>         _VSTD::swap(__base::__map_.__end_, __buf.__end_);
>         _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
>     }
>
>
> See this part:
> __split_buffer<pointer, typename __base::__pointer_allocator&>
>             __buf(max<size_type>(2* __base::__map_.capacity(), 1),
>                   __base::__map_.size(),
>                   __base::__map_.__alloc());
>
> You have a full map (capacity == size)
> map = [a b c d e f ]
> and you want to create a new map with double capacity
> new_map = [_ _ _ _ _ _ _ _ _ _ _ _ ]
>
> the second argument of split_buffer constructor (x) is used to assign
> __begin:
> __begin_ = __end_ = __first_ + x;
>
> So, at the end you will have
> new_map = [a b c d e f g _ _ _ _ _ ]
>
> Where g is the address of the new block created.
>
> However, you can see that adress's of blocks are left aligned. A better
> alternative is:
>
> __split_buffer<pointer, typename __base::__pointer_allocator&>
>             __buf(max<size_type>(2* __base::__map_.capacity(), 1),
>                   __base::__map_.size()*3/2,
>                   __base::__map_.__alloc());
>
> Using this code, at the end the new map will be:
> new_map = [_ _ _ a b c d e f g _ _ ]
> which is better because there is equilibrium, avoiding complex operations
> (pop_back + push_back(pt)) if the programmer call a subsequent push_front
> --> __add_front_capacity.
>
> But I am not expert, I am learning C++ and navigating inside of the libc++
> source to understand how some containers work.
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180406/ec98a8b7/attachment.html>


More information about the cfe-dev mailing list