3. 벡터 메모리 (reserve, size, capacity, noexcept)_ C++

 vector 오브젝트의 size와 capacity, 그리고 reserve 메소드

 이전 게시글에서 벡터의 시간 복잡도 Time complexity에 대하여 다뤘다.
벡터의 마지막에 삽입/제거할 경우에는 O(1) 의 Time Complexity를 가진다고 이야기했다.
하지만 이런 O(1)의 시간 복잡도는 항상 보장되는 것이 아니다.
실제로는 가끔 O(n) 의 시간 복잡도를 가지게 된다.
예시를 통해 간단히 살펴보면,

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums;
	std::cout << sizeof(nums) << std::endl;

	return 0;
}

 

int형 vector nums를 만들어 주고 nums의 사이즈를 출력해 보면 24byte 라는 결과가 출력된다.
이를 그림으로 보면, 

 벡터 오브젝트 nums는 힙 공간의 array를 가리키고 있는데, 
array에는 아무것도 들어있지 않기 때문에 사이즈는 0일 것이다.

그런데 방금 벡터의 사이즈가 24라고 나왔다. 
이건 벡터 오브젝트의 사이즈가 24byte라는 것이다.
이 안에 들어있는 정보는 다음 세 가지이다.
1) 포인터 정보 (힙 위에 있는 array의 시작점을 가리켜야 하기 때문에, 64바이트의 컴퓨터에서 8byte의 사이즈를 가짐)
2) size에 대한 정보 (8byte)
3) capacity에 대한 정보 (8byte)

검증을 위해서 
nums에 1,2,3,4,5 다섯개의 숫자를 넣어주고 nums의 사이즈와 capacity를 리턴 받아 보면

#include <vector>

int main()
{
	std::vector<int> nums{1,2,3,4,5};
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	return 0;
}

똑같이 5가 나온다.

그런데 nums에 하나의 데이터 6을 더 넣어주고 사이즈와 capacity를 확인해보면 

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums{1,2,3,4,5};
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	nums.emplace_back(6);
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	return 0;
}

이번엔 6과 7이 나온다. 응?

capacity는 size와는 다른 정보인데 
방금 코드에서 봤듯 현재 nums는 1~6에 대한 정보를 가지고 있으니 사이즈는 당연히 6이 나오는 것은 이해가 쉽다.
그런데 capacity는 대체 왜 7이 나오는 것일까?

그러니까 현재 vector 뒤에 1개의 공간이 더 있고 그렇기에 capacity를 7이라고 말 해주는 것이다.
size는 현재 vector에 들어있는 element의 개수이고
capacity는 vector가 확보한 메모리의 크기이다.
만약 여기에 계속해서 emplace_back(7)을 통해서 7을 넣어 주었을 때 capacty와 vector의 size는 같게 된다.
이 때 한번의 emplace_back(8)을 더 해 주게 되면 확보한 메모리가 없기 때문에 (7개밖에 없었으니)
vector는 다시 한 번 메모리를 확보받은 후에 이곳에 8을 넣어주고
stack 위에 올라가 있는 벡터 정보에 size는 8 capacity는 10 이라는 정보가 나오게 되는 것이다. 

더 테스트해서 벡터에 11까지 넣어보면,
1~11까지 들어있는 vector의 사이즈는 11이지만, 
capacity는 15가 나온다.
즉 메모리의 확보를 15까지 해 두었다는 의미인 것이다.

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums{1,2,3,4,5};
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	nums.emplace_back(6);
	nums.emplace_back(7);
	nums.emplace_back(8);
	nums.emplace_back(9);
	nums.emplace_back(10);
	nums.emplace_back(11);
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	return 0;
}

 결론은, 이를 통해 확보된 메모리에 emplace_back()을 할 때는 이미 메모리가 확보되어 있기 때문에 0(1)의 time complexity만 필요로 하지만,
새로 메모리를 할당받기 위해서는 추가적인 시간이 필요할 것이라는 사실은 짐작할 수 있다는 것이다.
이 때 사용하는 명령어가 reserve이다.

reserve를 cppreference에서 확인해보면,

---

void reserve( size_type new_cap );

---

reserve는 vector의 capacity를 new_cap의 사이즈 혹은 그것보다 더 크게 증가시켜준다고 쓰여인다.
코드를 통해 확인해 보자.

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums{1,2,3,4,5};
	nums.reserve(100000);

	nums.emplace_back(6);
	nums.emplace_back(7);
	nums.emplace_back(8);
	nums.emplace_back(9);
	nums.emplace_back(10);
	nums.emplace_back(11);
	std::cout << nums.size() << std::endl;
	std::cout << nums.capacity() << std::endl;

	return 0;
}

nums.reserve(100000); 을 통해 10만개의 공간을 확보해 놓고 emplace_back()을 하게 되면 
벡터의 사이즈는 11이지만 capacity는 100000이 된다!!
이제 10만의 메모리를 다 채울 때까지 벡터의 emplace_back()은 O(1)의 Time complexity만을 갖게 된다.
물론 이런 capacity를 너무 크게 잡아 버리면 이 프로세스의 메모리 사용률이 급격하게 높아지기 때문에 필요한 크기의 최대치만 잡아주는 것이 좋다.

그렇다면 이런 경우에는 어떻게 될까?
현재 벡터에 1,2,3,4 가 들어 있는데, emplace_back()을 통해서 하나의 벡터를 더 넣고 싶은 경우가 있을 것이다.
그런데 4 다음 공간이 이미 다른 메모리가 사용 중일 수 있다.
(예를 들어 string type name이 들어있고  name은 힙 위에 어떤 문자를 가리키고 있는 상황일 수 있다.)

emplace_back(5) 를 통해 5를 4 뒤에 넣고 싶은데 오른쪽으로 더 이상 증가를 할 수가 없다.
이럴 때 5를 넣기 위해서 새로운 벡터 전체를 만들어 주고 1,2,3,4,5 전부 move 또는 copy 해 준 뒤에
nums는 이 부분을 가리키게 되고 미리 있던 앞쪽의 벡터 공간은 메모리 해제 되게 된다.

즉, 이 경우엔 5를 하나 더 넣어주기 위한 emplace_back() 이 O(1)이 아닌 O(n)의 시간 복잡도를 갖게 되는 것이다.

 그래서 미리 reserve라는 vector메소드를 통해서 capacity를 미리 확보해놓으면 전체가 복사가 되거나 move 될 필요 없는 O(1)의 시간 복잡도를 가져갈 수 있는 것이다.

디스트럭터, move 컨스트럭터, 할당을 정의할 때 noexcept 써주기

당연히 C++는 더 효율적인 프로그램을 짜기 위해서 move를 할 수 있는 경우엔 move를 하겠지만,
그것이 불가능할 경우에는 copy를 해야 하는 경우가 있다.
(일반적인 클래스나 오브젝트를 만들게 되면 오브젝트가 copy 되는 일은 일어나지 않는다.)
copy 컨스트럭터, move 컨스트럭터, copy 할당, move 할당을 정의한 다음
고양이의 array인 cats를 만들어주고 cats 안에 "kitty", "nabi"를 만들어 보자.

#include <iostream>
#include <vector>

class Cat
{
public:
	explicit Cat(std::string name) : mName{ std::move(name) }
	{
		std::cout << mName << "Cat constructor" << std::endl;
	}
	~Cat()
	{
		std::cout <<mName<< "~Cat()" << std::endl;
	}
	Cat(const Cat& other) : mName(other.mName)
	{
		std::cout <<mName<< "copy constructor" << std::endl;
	}
	Cat(Cat&& other) : mName(other.mName)
	{
		std::cout << "move constructor";
	}
	//copy assignment
	//move assignment

private:
	std::string mName;
};

int main()
{
	std::vector<Cat> cats;
	cats.emplace_back("kitty");

	cats.emplace_back("nabi");

	return 0;
}

kitty 컨스트럭터가 만들어지고 
nabi 컨스트럭터가 만들어 졌는데
그 이후에 copy 컨스트럭터가 불러지고
디스트럭터가 3번이 불러진다. 

간단하게 array안에 고양이 1마리가 들어 있고 바로 다음 고양이 "nabi"를 넣어주니까 
예상하기로는 간단하게 이 공간 뒤에 나비인 고양이 오브젝트가 생길 것이라고 생각할  수 있는데,
실제 작동 방식은 위에서 확인할 수 있듯이 kitty의 copy 컨스트럭터와 디스트럭터가 불러졌다.
즉, 바로 나비 고양이 오브젝트가 바로 뒤에 생성되는 것이 아니라
새로운 array 2칸이 생기면서 nabi가 들어가고 
kitty 에서 kitty로 copy 컨스트럭터가 불러지는 것이다.
새로운 메모리 공간을 확보하지 못해서 전체가 복사되는 일이 벌어진 것이다.

전에 배웠듯이
copy 보다는 move가 일어나는 것이 훨씬 효율적이라는 것을 알고있다.

그런데 move가 아니라 copy가 불리어진 이유는, class를 정의할 때 exception이 날 수 있기 때문에
컴파일러가 안전하게 프로그램을 짜기 위해서 copy를 불러진 것이다.
현재 상황에서는 move가 새로운 리소스를 요청하지 않기 때문에 에외가 발생할 수 없다.
따라서 noexcept 키워드를 붙여주게 되면, 

#include <iostream>
#include <vector>

class Cat
{
public:
	explicit Cat(std::string name) : mName{ std::move(name) }
	{
		std::cout << mName << "Cat constructor" << std::endl;
	}
	~Cat() noexcept
	{
		std::cout <<mName<< "~Cat()" << std::endl;
	}
	Cat(const Cat& other) : mName(other.mName)
	{
		std::cout <<mName<< "copy constructor" << std::endl;
	}
	Cat(Cat&& other) noexcept : mName(other.mName)
	{
		std::cout << "move constructor";
	}
	//copy assignment
	//move assignment

private:
	std::string mName;
};

int main()
{
	std::vector<Cat> cats;
	cats.emplace_back("kitty");

	cats.emplace_back("nabi");

	return 0;
}

 move 컨스트럭터로 변경된 것을 확인할 수 있다.
이것이 디스트럭터와 move 컨스트럭터, 할당을 정의할 때에 noexcept를 꼭 붙여 주어야 하는 이유다.

물론 가장 좋은 방법은 처음부터 고양이 array를 선언할 때 reserve 메소드를 통해서 미리 공간을 확보해 놓을 수 있는데
그렇게 되면 아주 깔끔하게 단 한번에 전체적인 벡터의 프로세스가 진행되는 것을 확인할 수 있다!

#include <iostream>
#include <vector>

class Cat
{
public:
	explicit Cat(std::string name) : mName{ std::move(name) }
	{
		std::cout << mName << "Cat constructor" << std::endl;
	}
	~Cat() noexcept
	{
		std::cout <<mName<< "~Cat()" << std::endl;
	}
	Cat(const Cat& other) : mName(other.mName)
	{
		std::cout <<mName<< "copy constructor" << std::endl;
	}
	Cat(Cat&& other) noexcept : mName(other.mName)
	{
		std::cout << "move constructor";
	}
	//copy assignment
	//move assignment

private:
	std::string mName;
};

int main()
{
	std::vector<Cat> cats;
	cats.reserve(2);
	cats.emplace_back("kitty");
	cats.emplace_back("nabi");

	return 0;
}

깔끔깔끔

결론

1. vector를 사용할 때는 reserve 메소드를 통해서 capacity를 미리 확보하는 것은 매우 중요하다.

2. 디스트럭터, move 컨스트럭터, 할당을 정의할 때 noexcept 써주기.