`<deque>`: Make `deque::shrink_to_fit` never relocate elements

[frederick-vs-ja]

trafficstars

Fixes #4072 by providing stronger guarantee.

[achabense]

Hmm, the impl is still not correct... try:

    std::deque<int> deq(128);
    for (int i = 0; i < 120; i++) {
        deq.pop_back();
    }
    for (int i = 0; i < 5; i++) {
        deq.push_front(0);
    }
    deq.shrink_to_fit();

[achabense]

(ignorable)

    void shrink_to_fit() {
        if (empty()) {
            if (_Map() != nullptr) {
                _Reset_map();
            }
            return;
        }

        const _Map_difference_type _Index_mask = _Map_distance() - 1;
        const _Map_difference_type _First_block_idx = _Getblock(_Myoff());
        const _Map_difference_type _Last_block_idx = _Getblock(_Myoff() + size() - 1); // the block `back()` belongs to.

        if (_First_block_idx == _Last_block_idx) {
            return; // every block is occupied
        }

        // deallocate unused blocks
        _Map_difference_type _Unused_block_idx = (_Last_block_idx + 1) & _Index_mask; // masked
        size_type _Unused_block_count = 0;
        while (_Unused_block_idx != _First_block_idx) {
            ++_Unused_block_count;
            auto& _Block_ptr = _Map()[_Unused_block_idx];
            if (_Block_ptr != nullptr) {
                _Getal().deallocate(_Block_ptr, _Block_size);
                _Block_ptr = nullptr;
            }
            _Unused_block_idx = (_Unused_block_idx + 1) & _Index_mask;
        }

        const size_type _Used_block_count = _Mapsize() - _Unused_block_count;

        size_type _New_block_count = _Minimum_map_size; // should be power of 2
        while (_New_block_count < _Used_block_count) {
            _New_block_count *= 2;
        }
        if (_New_block_count >= _Mapsize()) {
            return;
        }

        // worth shrinking the internal map, do it

        _Alpty _Almap(_Getal());
        const auto _New_map = _Almap.allocate(_New_block_count);

        _Orphan_all(); // shrinkable, invalidate all iterators

        _Map_difference_type _New_block_idx = 0;
        while (_New_block_idx < static_cast<_Map_difference_type>(_Used_block_count)) {
            _STD _Construct_in_place(
                _New_map[_New_block_idx], _Map()[(_First_block_idx + _New_block_idx) & _Index_mask]);
            ++_New_block_idx;
        }
        // zero out the rest of the new map
        _STD _Uninitialized_value_construct_n_unchecked1(
            _New_map + _New_block_idx, _New_block_count - _Used_block_count);

        // destroy block pointers, and free storage for map.
        for (_Map_difference_type _Block = 0; _Block < _Map_distance(); ++_Block) {
            _STD _Destroy_in_place(_Map()[_Block]);
        }
        _Almap.deallocate(_Map(), _Mapsize());

        _Map() = _New_map;
        _Mapsize() = _New_block_count;
        _Myoff() %= _Block_size;
    }

[StephanTLavavej]

Thank you! :heart_eyes_cat: After getting up to speed with your excellent overhaul here, I pushed a bunch of changes to make the logic clearer for my cat-sized brain. Please double-check that I didn't mess anything up.

This is vastly better than our original implementation of shrink_to_fit(), and now that I can see what the fix is doing, I'm not too worried about it subtly breaking deque invariants. However, this is definitely complex enough to need 3 maintainer eyes, so I'll ask for a final review before moving this to ready to merge.

[StephanTLavavej]

I'm mirroring this to the MSVC-internal repo - please notify me if any further changes are pushed.

[StephanTLavavej]

Thanks for fixing everyone's favorite STL container! :hammer_and_wrench: :joy_cat: :tada: