[C++] push_back 내부구현

본 게시글은 MSVC STL(std::vector)에서의 push_back 내부 구현을 살펴본다.

결론부터 말하면 다음과 같다.
push_back은 상각(amorized) O(1) 성능을 갖도록 설계되어있다.
이를 위해 대부분 구현체는 capacity가 부족해지는 시점에 저장 공간을 기하급수적으로 확장하여 재할당/이동이 발생하는 비싼 작업의 빈도를 낮춘다.
(상각=여러 번의 연산을 수행했을 때의 평균 값)

push_back

class vector {
    ...
    _CONSTEXPR20_CONTAINER void push_back(_Ty&& _Val) {
        // insert by moving into element at end, provide strong guarantee
        emplace_back(_STD move(_Val));
    }
    
    template <class... _Valty>
    _CONSTEXPR20_CONTAINER decltype(auto) emplace_back(_Valty&&... _Val) {
        // insert by perfectly forwarding into element at end, provide strong guarantee
        auto& _My_data   = _Mypair._Myval2;
        pointer& _Mylast = _My_data._Mylast;
        if (_Mylast != _My_data._Myend) {
            return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
        }

        _Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
        return _Result;
    }
	...   
}

vector의 push_back을 호출하면 emplace_back을 내부적으로 호출한다.
그리고 vector에 남은 공간이 있는지 확인하여 재할당 없이 끝에 삽입하는 fast path로 들어간다. (_Mylast != _My_data._Myend)

반대로 vector에 남은 공간이 없다면, _Emplace_reallocate로 가서 capacity를 늘리는 작업을 진행한다.

_Emplace_reallocate

해당 함수에서는 capacity 재할당 (growth) 및 삽입이 진행된다.

	...
    template <class... _Valty>
    _CONSTEXPR20_CONTAINER 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;
        ...

        const size_type _Newcapacity = _Calculate_growth(...);
        ...
    }
    
    _CONSTEXPR20_CONTAINER size_type _Calculate_growth(const size_type _Newsize) const {
        // given _Oldcapacity and _Newsize, calculate geometric growth
        const size_type _Oldcapacity = capacity();
        ...
        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
		...
        return _Geometric; // geometric growth is sufficient
    }
    ...
}

_Calculate_growth 함수를 보면 이전 capacity (_Oldcapacity)의 1.5배씩 확장하는 식으로 진행된다.
(반면, GCC에서는 2배씩 확장한다.)

검증

아래는 vector에 200개의 데이터를 삽입할 때의 capacity 변화량이 출력되도록 한 코드이다.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;

    std::size_t prev_cap = v.capacity();

    for (int i = 0; i < 200; ++i) {
        v.push_back(i);

        if (v.capacity() != prev_cap) {
            std::cout << "capacity: " << prev_cap << " -> " << v.capacity() << "\n";
            prev_cap = v.capacity();
        }
    }
}

---

# result
capacity: 0 -> 1
capacity: 1 -> 2
capacity: 2 -> 3
capacity: 3 -> 4
capacity: 4 -> 6
capacity: 6 -> 9
capacity: 9 -> 13
capacity: 13 -> 19
capacity: 19 -> 28
capacity: 28 -> 42
capacity: 42 -> 63
capacity: 63 -> 94
capacity: 94 -> 141
capacity: 141 -> 211