[C++] vector 는 2배씩 늘어나는게 맞을까?

개요

벡터는 용량이 부족하면 더 큰 용량을 할당한 뒤 그곳으로 복사를 한다고 다들 알고 있을 겁니다. 여기서 더 큰 용량 을 생각할 때 '벡터는 당연히 2배씩 용량 늘어나겠지' 싶었습니다.

 

그런데 일을하면서 사수분이 생겼고 이 사수분이 이런 논제를 하나 던져줬습니다. '진짜 2배씩 늘어나는지 찍어보셨나요?'. 이걸 듣고 핫차 싶어서 시간 날 때 바로 테스트를 해보기로 했습니다.

 

 

결론은 마냥 2배는 아니다.

그냥 간단하게 2, 4, 8...등으로 늘어날 수 있게 유도해 봤습니다. 코드는 아래 접은 글에 있습니다.

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    vector<int> vec;

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

    //...
    vec.push_back(0);
    //...

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

    //...
    for(int i = 0; i < 2; i++)
        vec.push_back(0);
    //...

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

    //...
    for(int i = 0; i < 2; i++)
        vec.push_back(0);
    //...

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

    //...
    for(int i = 0; i < 4; i++)
        vec.push_back(0);
    //...

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

        //...
    for(int i = 0; i < 8; i++)
        vec.push_back(0);
    //...

    cout << "===============\n";

    cout << "vector size     : " << vec.size() << '\n';
    cout << "vector capacity : " << vec.capacity() << '\n';

}

 

일단 GCC 6.3.0 버전의 컴파일러가 있는 VS Code에서 실행해 봤습니다.

in GCC 6.3.0

조금 재미없게도 2의 배수대로 늘어나는 모습을 볼 수 있었습니다. 여기서 '내 환경은 다 2배인가?' 했습니다.

 

in Visual Studio 22 (C++14)

그런데 Visual Studio의 C++14 버전 컴파일러 환경에서 하면 1, 3, 6, 9, 19... 등으로 뭔가 신기하게 늘어나는 모습을 볼 수 있습니다. 확실한 건 2의 배수로 증가하지 않는다는 걸 알 수 있습니다. 

 

 

template <class... _Valty>
    _CONSTEXPR20 pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {
        // reallocate and insert by perfectly forwarding _Val at _Whereptr
        _Alty& _Al        = _Getal();
        auto& _My_data    = _Mypair._Myval2;
        pointer& _Myfirst = _My_data._Myfirst;
        pointer& _Mylast  = _My_data._Mylast;

        _STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); // check that we have no unused capacity

        const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);
        const auto _Oldsize  = static_cast<size_type>(_Mylast - _Myfirst);

        if (_Oldsize == max_size()) {
            _Xlength();
        }

        const size_type _Newsize     = _Oldsize + 1;
        const size_type _Newcapacity = _Calculate_growth(_Newsize);

        const pointer _Newvec           = _Al.allocate(_Newcapacity);
        const pointer _Constructed_last = _Newvec + _Whereoff + 1;
        pointer _Constructed_first      = _Constructed_last;

        _TRY_BEGIN
        _Alty_traits::construct(_Al, _Unfancy(_Newvec + _Whereoff), _STD forward<_Valty>(_Val)...);
        _Constructed_first = _Newvec + _Whereoff;

        if (_Whereptr == _Mylast) { // at back, provide strong guarantee
            if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
                _Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
            } else {
                _Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
            }
        } else { // provide basic guarantee
            _Uninitialized_move(_Myfirst, _Whereptr, _Newvec, _Al);
            _Constructed_first = _Newvec;
            _Uninitialized_move(_Whereptr, _Mylast, _Newvec + _Whereoff + 1, _Al);
        }
        _CATCH_ALL
        _Destroy_range(_Constructed_first, _Constructed_last, _Al);
        _Al.deallocate(_Newvec, _Newcapacity);
        _RERAISE;
        _CATCH_END

        _Change_array(_Newvec, _Newsize, _Newcapacity);
        return _Newvec + _Whereoff;
    }

 

VS 에서 C++17 기준으로 뽑아봤을 때 _NewCapacity는 (현재 사이즈 + 1)에서 _Calculate_growth를 호출한 형태입니다.

 

_CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
    // given _Oldcapacity and _Newsize, calculate geometric growth
    const size_type _Oldcapacity = capacity();
    const auto _Max              = max_size();

    if (_Oldcapacity > _Max - _Oldcapacity / 2) {
        return _Max; // geometric growth would overflow
    }

    const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

    if (_Geometric < _Newsize) {
        return _Newsize; // geometric growth would be insufficient
    }

    return _Geometric; // geometric growth is sufficient
}

 

해당 함수를 보면 인자로 들어온 _NewSize(이전 사이즈 + 1)  또는 이전 capacity에서 50% 증가 한 사이즈로 capacity를 잡는 것을 볼 수 있습니다. 아마 50% 증가인데 _NewSize와 비교하는 건 아무것도 없는, size, capacity 둘 다 0인 경우에 해당하는 것으로 보입니다.

 

때문에 마냥 2배로 늘어나는게 아니라 다양한 방식으로 늘어난다 나는걸 알 수 있습니다. 그나저나 이렇게 되면 나중에 reserve를 잘해야겠네요. 50% 늘어나는 거 잘못 잡으면 복사에 비용을 다 빼앗길 테니깐요.