[C++] STL Container II

1. vector capacity vs size

#include <iostream>
#include <vector>

void check(const std::vector<int>& v) 
{
	std::cout << "capacity : " << v.capacity() << ", size : " << v.size() << std::endl;
}

int main()
{
	std::vector v = { 1, 2, 3, 4, 5 };

	v.resize(3); 

	check(v);	// c : 5    s : 3


	v.push_back(0);	// capacity > size 이므로
					// 빠르게 동작 
	
	check(v);	// c : 5   s : 4

	v.shrink_to_fit();		

	check(v);	// c : 4   s : 4

	v.push_back(0); // capacity == size  이므로 메모리 재할당 필요
					// 느리다.

	check(v);	// c : ?   s : 5

	v.clear();	// 메모리를 제거하지는 않음.
				// size 만 0으로

	check(v);

	v.resize(0); // 또는 v.clear()

	v.shrink_to_fit();

	check(v);
}

- vector에서는 capacity 라는 것과 size라는 개념이 별도로 존재한다.

- 이들은 분명히 차이가 존재한다.

- vector는 이와 같이 할당 된다.

 

1-1. resize()의 구현

- 소스코드에서 해당 부분을 잘 확인해야 한다.

v.resize(3);

- 실제 STL에서 resize를 어떻게 구현했을까에 대한 생각이다.

- 크기를 3으로 조정한다는 것은, 크기를 3으로 줄이고, 메모리 복사를 진행해야 한다.

- myvector 구현에서 이를 보인적이 있다. 이는 성능 저하가 크다.

 

※ 잦은 메모리 할당과 메모리 복사는 성능 저하의 가장 큰 원인이다.

 

① C++ STL은 그럼 어떻게 이 문제를 해결했는가?

- 이처럼 실제 메모리 사용 공간은 5이다. 하지만 여기서 크기 값만 조정하여 사용하는 것이다.

- size : 벡터가 현재 가지고 있는 데이터의 수를 의미한다.

- capacity : 벡터가 현재 할당받은 메모리 공간의 크기를 의미한다. size에 대해서 사이즈가 항상 크거나 같다.

 

② 이 상황에서 0을 추가하면 어떻게 되는가?

v.push_back(0);

 

- 이렇게 바뀌는 것이다.

 

※ 결론 : vector의 resize는 실제 메모리를 줄이지 않는다.

 

③ 실제 메모리를 줄이려면 어떻게 해야하는가?

- v.shink_to_fit() 멤버 함수를 사용하면, capacity 자체가 줄어들게 된다.

 

④ 여유 공간이 없는 상태에서 추가를 하게되면 어떻게 되는가?

v.push_back(0);

- 지금은 vector에 충분한 메모리 공간이 존재하지 않는다. capacity와 size가 일치하다.

- 따라서 메모리 재할당이 필요하기 때문에 느려진다.

 

⑤ 메모리 재할당이 일어난 이후 확인해보면, Capacity는 size 값보다 더 크게 늘어난다. 

check(v);	// c : ?   s : 5

- 이 부분을 재호출하면 확인이 가능한 것은, Capacity가 더 늘어난다는 것이다.

- 이는 gcc, visual studio에서 컴파일 할때 Capacity가 어느정도 크기로 늘어나는 가는 조금씩 다르다.

 

1-2. clear()의 구현

- 임의의 vector에서 clear()를 해보면 size만 0이 되는 것을 확인할 수 있다.

- 기존 들어있던 데이터만 지우고, 메모리 사용량이 줄어드는 것은 아니다.

- 즉, 벡터가 완전하게 지워지는 것은 아니다.

1-3. vector를 완전히 제거하는 방법

v.resize(0); // 또는 v.celar()

v.shrink_to_fit();

- 사이즈가 0인 상태로 v.shrink_to_fit()를 호출하면, capacity 자체가 0으로 줄어든다.

 

1-4. reserve()

int main()
{
    std::vector<int> v1;    // capacity : 0 size : 0
    check(v1);
    
    std::vector<int> v2(5); // capacity : 5 size : 5
    check(v2);
    
    std::vector<int> v3;
    v3.reserve(5);          // capacity : 5 size : 0
    check(v3);
}

- reserve()를 사용하면, capacity를 미리 확보 할 수 있다.

- 즉, 이렇게 하면 메모리 재할당은 발생하지 않을 수 있다.

- 이와 같이 할당 되는 것이다.

- 이렇게 할당함으로서 메모리 재할당이 일어나지 않음에 따라 성능 저하는 발생하지 않는다.

- 대신에 메모리가 조금 낭비된다는 문제가 존재한다.

- 이는 연속된 메모리에서만 유효하다.

 

1-5. 정리

- size : 벡터가 현재 가지고 있는 데이터의 수를 의미한다.

- capacity : 벡터가 현재 할당받은 메모리 공간의 크기를 의미한다. size에 대해서 사이즈가 항상 크거나 같다.

- capacity는 메모리 재할당에 따른 성능 저하를 막기 위해 나온 개념이나, 메모리 사용량은 줄어들지 않는다.

- resize(), clear() 등은 size에만 영향을 미치고, capacity에는 영향을 미치지 않는다.

- 만약 capacity를 초기화 하고 싶다면, shrink_to_fit()를 사용해야 한다.

- reserve()를 이용하면, Capacity를 미리 확보가 가능하다. 대신 메모리 낭비가 될 수 있으니 신중히 판단해야 한다.

---

2. std::array

 

2-1. array vs std::vector

#include <vector>
int main()
{
    int x[5]      = {1,2,3,4,5};
    std::vector v = {1,2,3,4,5};
    
    x[0] = 10;
    v[0] = 10;
}

- 이 예제는 배열과 벡터의 차이를 보여주기 위해서이다.

 

- 일반 배열 x와 vector v는 다음과 같은 차이가 있다.

- vector 자체는 stack에 있지만, 실제 여기에 들어있는 요소들은 동적메모리로 할당되어 heap에 올라간다.

- 이 때문에 크기를 조절하는 것이 가능한 것이다.

- 사이즈 조절이나 요소 추가할 필요가 없다면, 배열이 조금 더 빠를 수 있다.

- stack에 있는 것이 heap보다 빠르다.

 

2-2. std::array //C++11

#include <array>
{
    std::array  a = {1,2,3,4,5};
    a[0] = 10;
    
    auto n = a.size(); // 멤버 함수가 존재한다.
    
    a.resize(3);       // error
    a.push_back(3);    // error
}

- std::array는 멤버 함수가 존재하고, 메모리 상에 stack에 놓인다.

- 다만 스택에 할당되기 때문에 메모리를 늘려주는 행위는 불가능하다.

- 일부 구현에서는 성능 저하가 있을 수 있지만 raw array와 비슷한 성능을 가진다.

- 또 여러 멤버 함수를 통해 기존 배열에 없는 편의 기능을 제공한다.

 

2-2-1. std::array 관련 유의사항

#include <array>

int main()
{
	// C++17 부터는 초기값이 있으면 타입 인자 생략가능
	std::array arr1 = {1,2,3,4,5};


	// 초기값이 없거나 
	// C++17 이하의 환경에서는 타입인자를 전달해야 한다.
	std::array<int, 5> arr2; 		
	std::array<int, 5> arr3 = {1,2,3,4,5}; 		
}

- C++17 부터는 초기값이 있으면 타입 인자 생략이 가능하다.

- 하지만  초기값이 없거나, C++17 이하 환경에서는 타입 인자를 전달해야 한다.