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

[Christiano SA via cfe-dev]

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.