<div dir="ltr"><div class="gmail_extra">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.</div><div class="gmail_extra">`__add_front_capacity()` which does the opposite, and is used by `push_front`.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Additionally, both __front_capacity and __back_capacity will "steal" unused capacity from the other end of the deque.</div><div class="gmail_extra"><br></div><div class="gmail_extra">For these reason I don't see the advantage in achieving equilibrium between the front and back. Perhaps you could </div><div class="gmail_extra">elaborate further? Or, better yet, provide some benchmarks?</div><div class="gmail_extra"><br></div><div class="gmail_extra">/Eric</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 5, 2018 at 2:28 PM, Christiano SA via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Project: libc++<br>
file: include/deque<br>
line: 2422-2473<br>
<br>
Code:<br>
<br>
    else<br>
    {<br>
        __split_buffer<pointer, typename __base::__pointer_allocator&><br>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),<br>
                  __base::__map_.size(),<br>
                  __base::__map_.__alloc());<br>
<br>
        typedef __allocator_destructor<_Alloca<wbr>tor> _Dp;<br>
        unique_ptr<pointer, _Dp> __hold(<br>
            __alloc_traits::allocate(__a, __base::__block_size),<br>
                _Dp(__a, __base::__block_size));<br>
        __buf.push_back(__hold.get());<br>
        __hold.release();<br>
<br>
        for (typename __base::__map_pointer __i = __base::__map_.end();<br>
                __i != __base::__map_.begin();)<br>
            __buf.push_front(*--__i);<br>
        _VSTD::swap(__base::__map_.__f<wbr>irst_, __buf.__first_);<br>
        _VSTD::swap(__base::__map_.__b<wbr>egin_, __buf.__begin_);<br>
        _VSTD::swap(__base::__map_.__e<wbr>nd_, __buf.__end_);<br>
        _VSTD::swap(__base::__map_.__e<wbr>nd_cap(), __buf.__end_cap());<br>
    }<br>
<br>
<br>
See this part:<br>
__split_buffer<pointer, typename __base::__pointer_allocator&><br>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),<br>
                  __base::__map_.size(),<br>
                  __base::__map_.__alloc());<br>
<br>
You have a full map (capacity == size)<br>
map = [a b c d e f ]<br>
and you want to create a new map with double capacity<br>
new_map = [_ _ _ _ _ _ _ _ _ _ _ _ ]<br>
<br>
the second argument of split_buffer constructor (x) is used to assign __begin:<br>
__begin_ = __end_ = __first_ + x;<br>
<br>
So, at the end you will have<br>
new_map = [a b c d e f g _ _ _ _ _ ]<br>
<br>
Where g is the address of the new block created.<br>
<br>
However, you can see that adress's of blocks are left aligned. A better alternative is:<br>
<br>
__split_buffer<pointer, typename __base::__pointer_allocator&><br>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),<br>
                  __base::__map_.size()*3/2,<br>
                  __base::__map_.__alloc());<br>
<br>
Using this code, at the end the new map will be:<br>
new_map = [_ _ _ a b c d e f g _ _ ]<br>
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.<br>
<br>
But I am not expert, I am learning C++ and navigating inside of the libc++ source to understand how some containers work.<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</blockquote></div><br></div></div>