4. 벡터 루프문 vector array for loop_C++

벡터의 for loop

일반적으로 for loop문을 돌리는 방법에는 3가지가 있다.

1. Index
2. Iterator
3. Ranged based for loop (C++ 11)

 이 세가지 방법 중에서 Iterator와 Ranged based for loop는 비슷한 구조로 돌아간다. 
 결론부터 말하면 ranged based for loop이 가장 안전하고 표준의 방법이다.
하지만 for loop 안에서 Index 정보가 필요하다면 Index를 사용한 for loop문을 사용해야 하는 경우도 있다.

 예제

 "how many elements?" 가 출력된 후에 입력을 받고, 
입력을 받으면 입력된 수 n 개의 숫자 1이 들어가 있는 벡터를 만들어 주었다.
각 elelment에 2를 곱해주는 Index 베이스의 loop문을 만들고,
위에서 언급한 다른 두 가지 방법, iterator 그리고 ranged base for 로 for loop문을 만들어 주는 코드를 짜 보자.

#include <iostream>
#include <vector>

int main()
{
	std::cout << "How many elements?" << std::endl;
	std::size_t n;
	std::cin >> n;

	std::vector<int> numsA(n,1);
	std::vector<int> numsB(n,1);
	std::vector<int> numsC(n,1);

	//index based
	for (std::size_t idx = 0; idx < numsA.size(); idx++)
	{
		numsA[idx] *= 2;
	}

	////iterator based
	for (auto itr = numsB.begin(); itr != numsB.end(); itr++)
	{
		(*itr) *= 2;
	}

	//range based for loop
	for (auto& num : numsC)
	{
		num *= 2;
	}


	return 0;
}

nums 벡터가 스택 위에 있고 힙 위에 n개의 1이 들어가 있는 array를 만든 것이다.
그리고 nums에는 포인터정보, size, capacity가 들어있다.

1. for loop 인덱스
: for loop에 있는 인덱스가 nums의 size와 비교하면서 for loop을 진행할지 말지 결정하고 있는 코드이다.

2. iterator
: iterator가 가장 첫 번째를 가리키는 곳에서 시작하고, numsB.end() 라는 곳 즉 벡터의 마지막 바로 다음 공간을 가리키고 있다. iterator가 순차적으로 증가하다가 이 마지막 end 지점과 같은지 아닌지 체크하면서 for loop을 진행하고 있는 것이다.

3. ranged base for loop
: C++ 17까지의 방식과 C++ 20 이후의 방식이 각각 다 다르기 때문에 cppreference에서 직접 확인해 보는 것이 좋다.
https://en.cppreference.com/w/cpp/language/range-for      

Range-based for loop (since C++11) - cppreference.com

statement 부분을 참고하면 된다.

그렇다면 세 방법의 loop문 중에 어떤 방식이 가장 빠르거나, 또는 어떤 방식이 올바른 방식일까?
그걸 알아보기 위해 프로파일을 찍어보자!

3가지 for loop문 중 어떤 방식이 옳거나, 효율적인 방법인가?

#include <iostream>
#include <vector>
#include <chrono>

int main()
{
	std::cout << "How many elements?" << std::endl;
	std::size_t n;
	std::cin >> n;

	std::vector<int> numsA(n, 1);
	std::vector<int> numsB(n, 1);
	std::vector<int> numsC(n, 1);

	auto start = std::chrono::high_resolution_clock::now();

	//index based
	for (int i = 0; i < 1000; i++)
	{
		for (std::size_t idx = 0; idx < numsA.size(); idx++)
		{
			numsA[idx] *= 2;
		}
	}
	auto end = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double>diff = end - start;
	std::cout << "idx loop: " << diff.count() << "s\n";

	start = std::chrono::high_resolution_clock::now();

	//iterator based
	for (int i = 0; i < 1000; i++)
	{
		for (auto itr = numsB.begin(); itr != numsB.end(); itr++)
		{
			(*itr) *= 2;
		}
	}
	end = std::chrono::high_resolution_clock::now();
	diff = end - start;
	std::cout << "iterator loop: " << diff.count() << "s\n";

	start = std::chrono::high_resolution_clock::now();

	//range based for loop
	for (int i = 0; i < 1000; i++)
	{
		for (auto& num : numsC)
		{
			num *= 2;
		}
	}
	end = std::chrono::high_resolution_clock::now();
	diff = end - start;
	std::cout << "ranged based for loop: " << diff.count() << "s\n";

	return 0;
}

1만개의 element를 갖고 있는 벡터를 만들고 각 루프문의 프로파일을 찍어 보았다.
ranged based for loop문이 가장 빠르다고 나온다!

+GCC랭을 사용한다면, 아마 결과가 Index loop가 가장 빠르다고 나올 수 있다.
그럴 땐 최적화 레벨을 03으로 넣어주고 돌려보고,

아무튼 이 코드를 여러번 돌려보면 언제는 ranged loop이, 어느 때는 index loop이 빠르게 나온다.
즉 for loop을 돌리는 과정 중에 index iterator 등 뭐가 더 좋다라고 말하기엔 애매하다.

 하지만 반드시 index base의 for loop을 돌려야 하는 경우가 있다. 
다음의 경우를 살펴보자,

index base for loop를 사용해야만 하는 경우

#include <iostream>
#include <vector>
#include <chrono>

int main()
{
	std::vector<int> nums{ 0,1,0,1 };

	for (std::size_t idx = 0; idx < nums.size(); idx++)
	{
		if (nums[idx] == 0)
		{
				nums.emplace_back(2);
		}
	}

	for (const int n : nums)
	{
		std::cout << n << " ";
	}
	std::cout << std::endl;


	return 0;
}

if 안에 nums의 인덱스가 0인 경우에 2를 넣어주는 코드를 짰다.
실행 결과를 보면 0 1 0 1 뒤에 2 2 가 들어간 것을 확인할 수 있다.

위 코드를 iterator base loop으로 바꿔보자.

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums{ 0,1,0,1 };

	//iterator based
	for (auto itr = nums.begin(); itr !=nums.end(); itr++)
	{
		if ((*itr) == 0)
		{
			nums.emplace_back(2);
		}
	}

	for (const int n : nums)
	{
		std::cout << n << " ";
	}
	std::cout << std::endl;


}

안 된다.
위와 같이 이터레이터를 사용하면서 벡터에 emplace_back() 등의 수정을 하면 undefined behavior을 일으킨다.
그 이유는 밑에서 설명하겠다. 우선은

위 코드를 ranged for loop문으로도 바꿔보자.

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> nums{ 0,1,0,1 };

	for (auto& num : nums)
	{
		if (num == 0)
		{
			nums.emplace_back(2);
		}
	}

	for (const int n : nums)
	{
		std::cout << n << " ";
	}
	std::cout << std::endl;

}

이번에는 2가 한번 추가된 것을 확인할 수 있다.

그림을 통해서 그 이유를 살펴보자.

: nums가 스택 위에 존재하고, 
이 nums는 힙 안에 4개의 공간을 가지고 있고 0 1 0 1이 그 안에 들어있는 상태이다.

 iterator의 for loop문을 보면 itr은 nums.begin() 부터 시작하고 있다.
그 말은, itr이 그림의 주황색 화살표 부분에서 시작하고 있다는 것이다.
그 이후 iterator가 가리키는 부분이 0이라면 emplace_back(2) 을 통해 벡터의 끝에 2를 넣어주는 동작을 하고 있는 것이다.

 그런데 저번 게시글에서 다뤘듯이,
오른쪽 공간에 무언가(초록색 블록)가 데이터를 차지하고 있어서 이 벡터가 더 커질 수 없다면 
이 벡터 전체가 move된다고 이야기했었다.
iterator가 0을 만나서 마지막 공간에 2를 넣어주려고 했는데 공간이 없기 때문에
전체 벡터가 다른 곳으로 이사를 가게 되는 셈이다.
이렇게 되면 itr은 여전히 원래 공간을 가리키고 있고 (주황색화살표), 
원래 있던 벡터는 오른쪽 공간으로 이사갔으니 nums.end() 즉 벡터의 end는 분홍색 화살표 부분을 가리키고 있는 것이다.
이렇게 되면 for loop를 돌고 있는 기본 단위인 iterator는 의미가 없는 메모리 공간을 보면서 0이 있으면 2를 추가하는 방식으로 루프문이 동작하고 있는 셈이다.

 반면 index based의 루프문의 경우에는 size()와 비교하면서 for loop문을 돌리고 있다.
이렇게 되면 벡터 전체가 이동하더라도 포인터를 따라서 첫 번째 공간에서 몇 번째 떨어져 있는지 확인한 후에 for loop문을 동작시키고 있는 것이다.
그렇기 때문에 벡터 전체가 어디로 이동하더라도 잘못된 공간을 가리킬 수가 없는 것이다.

결론: for loop안에서 벡터의 사이즈가 변경된다면 무조건 index 베이스의 for loop문을 만드는 것이 맞는 방법이다.

+추가로 이해를 돕기 위해 (이건 다른 개발자분께 들은 설명입니다)
트리 기반 map 이나 set 같은 경우를 생각해 보면, 
이터레이터를 쓰고 있는 중에 map에 insert 하면 트리 균형을 잡는 과정에서 현재 이터레이터가 참조하고 있는 위치가 
delete 되었을 수도 있다는 것이다.
Iterator라고 하는건 모든 컨테이너에 대한 추상화인데, 
일반화할 때 보면 안되는 경우가 있으니 그렇게 하면 안된다는 것.
 또한 함수형 프로그래밍의 측면에서도
루프문을 도는 와중에 그 내용을 수정하면 유지보수가 힘들기도 하다.
 

정리

vector for loop의 3 종류

1. index based
: index 정보가 필요할 경우 사용
: for loop안에서 벡터의 사이즈가 변경되는 경우 무조건 index based 사용

2. iterator

3. range based
: 가장 안전하고 가독성 좋음.