1. std::vector resizing and capacity

std::vector의 resizing과 capacity

배열 타입은 크게 고정 크기 배열(fixed-size array)와 동적 배열(dynamic array)로 나눌 수 있다

고정 크기 배열은 배열의 length가 인스턴스화 시점에 알려져야 하며 그 이후에는 length를 변경할 수 없는 배열을 의미한다
(std::array, C-style array 등)

동적 배열은 배열의 length를 인스턴스 된 후에 변경할 수 있는 배열을 의미한다, 대표적인 예로 std::vector가 있다

그렇다면 런타임에 std::vector의 length를 어떻게 조절할까? resize() 멤버함수를 사용하면 된다

	std::vector v{ 1, 2, 3, 4, 5};
	std::cout << v.size() << std::endl; //5

	v.resize(10); //vector의 크기를 10으로 재조정
	std::cout << v.size() << std::endl; //10

이때 resize()를 해도 기존 값은 보존되고 새로 추가되는 element들은 전부 타입의 기본 값으로 값 초기화 된다 (int인 경우 0)

물론 더 작은 크기로도 resize() 될 수 있다

	std::vector v{ 1, 2, 3, 4, 5};
	std::cout << v.size() << std::endl; //5

	v.resize(2);
	std::cout << v.size() << std::endl; //2

length를 줄이면 잘리는 값들은 제거된다 (3, 4, 5 element가 제거됨)

capacity

지금까지 vector의 length에 대해서만 정리했는데 vector에는 capacity 개념이 존재한다

쉽게 말하면 capacity는 저장 공간을 할당한 element의 수이고 length는 실제 사용중인 element의 수이다

따라서 위의 그림에서 capacity는 5인데 size는 2가 나오는것이다

마찬가지로 capcity()라는 멤버함수를 통해 capacity를 얻을 수 있다

	std::vector v{ 1, 2, 3, 4, 5};
	std::cout << v.size() << std::endl; //5
	std::cout << v.capacity() << std::endl; //5

	v.resize(2);
	std::cout << v.size() << std::endl; //2
	std::cout << v.capacity() << std::endl; //5

reallocation

std::vector 저장 공간의 크기를 변경할 때 재할당 (reallocation)이 발생한다

1. std::vector는 원하는 수의 element를 담을 수 있는 용량의 새로운 메모리를 할당받고, 이때 element는 값 초기화된다
2. 이전 메모리에 있던 element는 할당받은 새로운 메모리로 복사/이동한다
3. 이전 메모리는 system에 반환
4. std::vector가 새로운 capacity와 length를 얻게 된다

외부에서 보면 std::vector의 크기 자체가 조절된 듯 보이지만 실제로는 메모리가 교체된 것이다
(이러한 과정을 동적할당이라고 한다)

reallocation은 비용이 많이 드는 동작이다 (배열의 모든 element를 복사/이동 해야하기 때문에), 불필요한 reallocation은 지양하자

std::vector는 capacity를 통해 이러한 reallocation을 최대한 방지한다

	std::vector v{ 1, 2, 3 };
	std::cout << v.size() << std::endl; //3
	std::cout << v.capacity() << std::endl; //3

	v.resize(1);
	std::cout << v.size() << std::endl; //1
	std::cout << v.capacity() << std::endl; //3

	v.resize(3);
	std::cout << v.size() << std::endl; //3
	std::cout << v.capacity() << std::endl; //3

중간에 resize(1)이 되어도 capacity는 그대로 3이다 (의미없는 벡터 재할당이 동작하지 않음), 그리고 다시 resize(3)을 하면 capacity가 그대로 3이기 때문에 마찬가지로 재할당이 필요없다

이렇게 length와 capacity를 별도로 분리하여 std::vector의 길이가 변경될 때 필요없는 재할당을 피할 수 있다

중요한 점은 vector의 인덱싱은 length가 기준이다 (capacity가 기준이 아님)
ex) capacity는 5이고 length는 3이라면 index는 0,1,2까지만 valid하다, 그 외 4, 5는 out of bounds!

std::vector는 resize()를 더 큰 사이즈로 하면 length가 증가하고 필요한 경우 capacity도 증가한다, 하지만 더 작게 resize()하면 length는 감소하지만 capacity는 감소하지 않는다

이때 더 이상 필요하지 않은 capacity가 유지되면 메모리 낭비가 심하기 때문에 std::vector의 shrink_to_fit() 함수를 이용하여 length를 capacity에 맞게 줄이도록 요청하는게 좋다

	std::vector<int> a(1000);
	std::cout << "Length : " << a.size() << " Capacity : " << a.capacity() << std::endl;
	//1000, 1000

	a.resize(10);
	std::cout << "Length : " << a.size() << " Capacity : " << a.capacity() << std::endl;
	//10, 1000
    
    
	a.shrink_to_fit();
	std::cout << "Length : " << a.size() << " Capacity : " << a.capacity() << std::endl;
	//10, 10

이때 std::vector는 shrink_to_fit()가 호출되었다고 반드시 실행하지 않는다, 메모리를 줄이는것이 비효율적이거나 다른 이유에서 좋지 않다고 판단하면 무시될 수 있다

stack

프로그래밍에서 stack이란 삽입/삭제가 LIFO(Last-In, First-Out, 선입선출) 방식으로 발생하는 컨테이너 데이터 타입을 의미한다

push로 stack의 맨 위에 새로운 element를 삽입, pop으로 stack의 맨 위의 element를 삭제한다

Top으로 stack의 맨 위 element를 가져오기 (제거X)

Empty로 stack에 element가 없는지 확인, Size로 stack에 있는 element의 갯수 세기 등 다양한 연산을 지원한다

이제까지도 디버깅하면서 많이 사용한 call stack도 여기서 설명하는 stack이다
(함수가 호출되면 해당 함수에 대한 정보가 담긴 스택 프레임이 call stack의 맨 위에 추가되고 함수가 return되면 call stack의 맨 위에 추가된 스택 프레임이 제거된다)

따라서 call stack의 가장 위는 현재 실행중인 함수이고 그 아래는 각 함수 이전에 실행중이던 함수를 나타내는것이다

std::vector의 stack behavior

push_back()으로 std::vector의 맨 끝에 element를 추가할 수 있다
pop_back()으로 std::vector의 맨 끝 element를 제거할 수 있다 (void를 반환함)
back()으로 std::vector의 맨 끝 element를 가져온다 (제거X)
emplace_back()으로 std::vector의 맨 끝에 element를 추가할 수 있다 (상황에 따라 단순 push_back보다 효율적임)

	//print()는 length, capacity를 출력하는 함수
    
	std::vector<int> stackvector{};

	print(stackvector); //0, 0

	stackvector.push_back(1);
	stackvector.push_back(2);
	stackvector.push_back(3);

	print(stackvector); //3, 3

	std::cout << stackvector.back() << std::endl; //3

	stackvector.pop_back();

	print(stackvector); //2, 2

push_back()과 emplace_back()은 벡터의 length를 증가시키고 값을 삽입할 때 capacity가 부족하다면 reallocation을 유발한다
(위 코드에서 vector는 3번 reallocation됨)

이때 컴파일러에 따라 capacity가 다르게 나올 수 있다 (GCC, Clang은 두 배 늘어날 수 있음 (1, 2, 4), msvc는 1.5배 늘어날 수 있음)

이렇게 reallocation 시 capacity가 두 배 혹은 1.5배 씩 늘어나는 이유는 다음번에 std::vector에 요소가 추가될 때 추가적인 reallocation을 하지 않게 하기 위해 여유롭게 capacity를 늘리는것이다

물론 컴파일러에 따라 다르기 때문에 정확히 얼마가 늘어나는지 단언할 수 없다

reserve

그렇다면 미리 vector의 크기를 지정하고 push_back()을 하게 되면 재할당이 일어나지 않을까?

	std::vector<int> stackvector(3);

	stackvector.push_back(1);
	print(stackvector); //4, 4

재할당이 발생한다, ()와 resize()는 vector의 capacity와 length 모두 설정하기 때문이다, 따라서 (3)은 capacity뿐 아니라 length도 3으로 만들기 때문에 다음 push_back()에 의해 reallocation이 발생하는것이다

그렇다면 length는 조절하지 않고 capacity만 조절하고 싶으면 어떻게 해아할까? reserve()를 사용하면 된다

	std::vector<int> stackvector{};

	stackvector.reserve(6);
	print(stackvector); //0, 6

	stackvector.push_back(1);
	print(stackvector); //1, 6

	stackvector.push_back(1);
	print(stackvector); //2, 6

	stackvector.push_back(1);
	print(stackvector); //3, 6

reserve()로 메모리 공간만 할당하고 length는 같이 조절하지 않았다, 따라서 push_back을 할 때 앞에서부터 남는 메모리 공간에 element를 채우기 때문에 reallocation이 발생하지 않는다

push_back, emplace_back()

둘 다 element를 push한다

만약 push할 객체가 존재한다면 push_back()과 emplace_back()은 동일하고 push_back()을 선호하는게 좋다

단 vector에 push할 목적으로 임시객체를 생성한다면 emplace_back()이 더 효율적일 수 있다

    class Foo
    {
    public:
        Foo(std::string a, int b) : FooString{ a }, FooInt{ b } {}

        explicit Foo(int Input) : FooString{}, FooInt { Input } {}

    private:
        std::string FooString{};
        int FooInt{};
    };

    int main()
    {
        std::vector<Foo> FooVector{};

        Foo f{ "k", 2 };
        FooVector.push_back(f);
        FooVector.emplace_back(f);

        FooVector.push_back({ "e", 3 }); //임시객체 생성 후 vector로 복사
        FooVector.emplace_back("e", 3); //인자를 받아서 vector 내부에서 객체가 직접 생성되도록 함
        
        FooVector.push_back({ 4 }); //explicit 생성자 사용 불가 compile error
		FooVector.emplace_back(4); //explicit 생성자 사용 가능 ok
    }

emplace_back은 인자를 받아서 vector내부에서 객체를 직접 생성되도록 하기 때문에 불필요한 임시객체 복사 비용이 발생하지 않으며 임시객체 생성도 필요가 없어진다 (완벽 전달 perfect forwarding이라는 기능을 사용한다고 함)

또한 emplace_back은 explicit 생성자를 사용할 수 있다 (push_back은 불가능함)
따라서 emplace_back은 말도 안되는 변환을 수행할 수 있다 (위험함)

C++20 이전에는 emplace_back()은 aggregate intialization과 함께 작동하지 않았다 ({ })

std::vector< bool >

std::vector < bool >은 8개의 bool값을 1byte안에 압축해서 저장한다 (like std::bitset)
(메모리 절약을 위한)

이렇게 std::vector가 bool이라는 특정 타입에 대해서만 다른 방식으로 구현되는걸 class template 특수화라고 부른다

대부분의 경우 std::vector< bool >은 일반 std::vector와 마찬가지로 작동한다
([ ]를 통한 인덱싱, for문을 통한 순회, { true, false, }와 같은 초기화 방법 등등)

    int main() 
    {
        std::vector<bool> vecBool{ true, false, true, false, true, false };

        for (int i : vecBool)
        {
            std::cout << i;
        }

        vecBool[0] = false;

        return 0;
    }

사실 내부적으로 std::vector< bool >은 vector가 아니며 C++의 컨테이너 정의를 충족하지 않는다 (인덱싱 해서 나온 값이 T&여야 하는데 그렇지 않고 std::vector< bool >::reference인 proxy객체를 반환한다)

std::vector< bool >에서 [ 0 ]으로 값을 인덱싱 하게 되면 실제 bool값에 대한 참조 bool&을 return하지 않고 개별 bit에 접근하고 수정할 수 있게 해주는 임시 proxy 객체를 return한다

따라서 이러한 proxy객체는 bool처럼 동작하지만 실제 bool&이 아니기 때문에 template에서 타입 불일치가 발생하여 컴파일 에러가 발생할 수 있다

    template<typename T>
    void foo(std::vector<T>& v) {
        T& first = v[0];
    }

    int main() 
    {
        std::vector<int> int_vec = { 1, 2, 3 };
        foo(int_vec); // OK

        std::vector<bool> bool_vec = { true, false, true };
        foo(bool_vec); // T& first = v[0]에서 Compile Error
        
        return 0;
    }

std::vector< bool >은 일반적으로 지양하는게 좋다, 적절한 컨테이너로 사용이 불가능하기에 호환성 문제가 발생할 수 있다

std::vector< bool >대신에 constexpr std::bitset이나 std::vector< char >(bool값을 저장할 resizable한 컨테이너가 필요할 때), 서드파티 비트셋을 사용하는걸 권장한다

	#include <bitset>
    
    std::bitset<8> flag;
    std::bitset<8> flag(42); //00101010
    std::bitset<8> flag(std::string("11000101"));
    
    flag[0] = 1;
    flag.set(2); //2번째 bit를 1로 설정
    flag.reset(2); //2번째 bit를 0으로 설정
    flag.flip(2); //2번째 bit를 반대로 뒤집기
    
    flag.test(1); //1번째 bit가 1인가?

std::bitset은 std::vector< bool >과 달리 비트 단위 연산을 지원하기 때문에 성능상 유리하고 vector는 heap에 할당되지만 bitset은 stack에 할당할 수 있어 생성 속도가 빠르다