STL 반복자와 연산 그리고 <algorithm> 헤더

STL에서 반복자를 통해 각 원소(element)에 접근 할 수 있다. 이는 반복문에서 사용하기 편하다.

포인터 타입으로 생각하면 간단하다. STL의 모든 자료 구조는 내부 원소 순회를 위한 반복자를 제공한다.

각 템플릿마다 iterator 타입은 각각 따로 존재한다.

vector<int>::iterator vectorIntIt;
vector<float>::iterator vectorFloatIt;
list<string>::iterator listStringIt;
unordered_map<unsigned int, vector<string>>::iterator uMapIt;
set<long>::iterator longSetIt;

 

 

 

순회 방식에 따라 3가지로 나뉜다.

		사용 가능 연산자
순방향	++로 다음 반복자 이동	*, ++, ==, !=
양방향	++로 다음 반복자 이동 및 --로 이전 반복자 이동	*, ++, --, ==, !=
임의 접근	순방향 + 양방향 + 임의 접근 (Random Access Iterator)	*, ++, --, +, -, +=, -=, ==, !=, <, >, <=, >=

양방향 접근 반복자는 next()와 prev()로 이전/다음 반복자를 가져올 수 있다.

임의 접근 반복자는 next/prev도 사용할 수 있고 직접 연산 (+, -)를 통해 반복자를 증감 시킬 수 있다.

ex) vector<int>::iterator it; it += 3;

 

사용 시에는 다음을 주의하자.

1. end() 반복자는 마지막 요소를 가리키지 않는다.

2.반복자로 반복문을 돌 때 꼭 마지막 요소를 확인하고 시작 반복자를 너무 크게 증가해서 마지막 요소를 건너뛰는 일이 없도록 하자.

---

1. 반복문 사용

 

단순히 auto를 사용하면 값 수정이 가능한 iterator로 된다는 것에 주의하자.

값 변경을 막고 싶은 const로 선언하려면 아래 예시를 확인하자.

using namespace std;

int main()
{
	vector<int> v{ 1, 2, 3, 4, 5 };

	for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
	{
		// *it 값 변경 가능
		*it *= *it;
		cout << *it << ' ';
	}
	cout << endl;

	for (auto it = v.begin(); it != v.end(); ++it)
	{
		// *it 값 변경 가능
		*it *= *it;
		cout << *it << ' ';
	}
	cout << endl;

	for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it)
	{
		// *it 값 변경 불가
		cout << *it << ' ';
	}
	cout << endl;

	for (auto it = begin(const_cast<const vector<int>&>(v)); it != v.end(); ++it)
	{
		// *it 값 변경 불가
		cout << *it << ' ';
	}
	cout << endl;

	// cbegin, cend C++14 이상
	for (auto it = v.cbegin(); it != v.cend(); ++it)
	{
		// *it 값 변경 불가
		cout << *it << ' ';
	}
	cout << endl;

	// as_const C++17 이상
	for (auto it = begin(as_const(v)); it != v.end(); ++it)
	{
		// *it 값 변경 불가
		cout << *it << ' ';
	}
	cout << endl;
}

// output
1 4 9 16 25
1 16 81 256 625
1 16 81 256 625
1 16 81 256 625
1 16 81 256 625
1 16 81 256 625

 

2. 단순한 반복문

 

첫번째 루프에서 값이 복사되었기 때문에 내부에서 vv 값을 변경해도 v의 실제 원소에는 영향이 없다는 것을 확인하자.

using namespace std;

int main()
{
	vector<int> v{ 1, 2, 3, 4, 5 };

	for (auto vv : v)
	{
		// v의 값이 복사되어서 사용
		vv *= vv;
		cout << vv << ' ';
	}
	cout << endl;

	for (auto& vv : v)
	{
		// v의 값이 참조로 사용
		vv *= 2;
		cout << vv << ' ';
	}
	cout << endl;

	for (const auto vv : v)
	{
		// v의 값이 복사되고 값 변경 불가
		cout << vv << ' ';
	}
	cout << endl;

	for (const auto& vv : v)
	{
		// v의 값 상수 참조
		cout << vv << ' ';
	}
	cout << endl;
}

// output
1 4 9 16 25
2 4 6 8 10
2 4 6 8 10
2 4 6 8 10

 

3. distance

 

두 반복자간의 거리를 계산

using namespace std;

int main()
{
	vector<int> v{ 1, 3, 5, 7, 9 };

	auto it = lower_bound(v.begin(), v.end(), 8);

	auto dist = distance(v.begin(), it); // (index = 4)

	cout << "v.begin(): " << *v.begin() << endl;
	cout << "lower_bound(8): " << *it << endl;
	cout << "dist: " << dist << endl; // 4 - 0
}

// output
v.begin(): 1
lower_bound(8): 9
dist: 4

 

4. advance

 

반복자를 n번 증가

(반복자 += n 과 비슷하며 반복자 값 자체를 바꿈)

using namespace std;

int main()
{
	vector<int> v{ 1, 3, 5, 7, 9 };

	auto it = v.begin();
	cout << *it << endl;

	advance(it, 2);
	cout << *it << endl;
}

// output
1
5

 

5. 반복자를 사용하는 <algorithm> 헤더의 함수들

 

** 범위는 [first, last)로, first 요소는 포함하고 last 요소는 포함하지 않는다.

find (first, last, value)	검색 구간에서 해당 값과 일치하는 첫번째 요소의 반복자를 반환; 찾지 못하였으면 last 반환	순차적으로 확인 (순방향) 컨테이너 변경 없음
find_if(first, last, predicate)	검색 구간에서 술어(predicate)에 따라 검색을 수행; 조건에 맞는 첫번째 값을 찾지 못하였으면 last 반환	순차적으로 확인 (순방향) 컨테이너 변경 없음 람다식 사용 가능
count(first, last, value)	검색 구간 내에서 해당 값과 일치하는 요소의 개수를 반환	순차적으로 확인 (순방향) 컨테이너 변경 없음
count_if(first, last, predicate)	검색 구간에서 술어(predicate)에 따라 검색을 수행하고 조건에 맞는 요소의 개수 반환	순차적으로 확인 (순방향) 컨테이너 변경 없음 람다식 사용 가능
copy (first, last, begin)	검색 구간(first ~ last)의 값을 begin에 복사	복사할 크기만 큼 미리 공간을 확보해야한다. (공간이 부족한 컨테이너에 값을 복사하려고 하면 에러가 나타날 것이다.)
unique (first, last)	구간(first ~ last)에서 중복된 요소들을 뒤로 보낸다. 중복되어서 뒤로 보내졌던 첫번째 중복된 요소를 가리키는 반복자를 반환	순차적으로 확인 (순방향)
sort(first, last, comp)	구간의 요소들을 오름차순 정렬 (정렬 방법은 comp에 따라 달라짐; default: 오름차순)	컨테이너 수정 일어남 보통 quick_sort로 정렬

 

Sample Code

using namespace std;

void print(vector<int>::iterator first, vector<int>::iterator last)
{
	for (auto it = first; it != last; ++it) cout << *it << '\t';
	cout << endl;
}

int main()
{
	vector<int> v{ -3, -1, 5, -9, 7, -1, 5, -3, -1 };

	// 처음으로 양수가 나오는 반복자 반환
	auto f = find_if(v.begin(), v.end(), [](int a) { return a > 0; });
	cout << *f << endl; // 

	// (3, 10) 내의 요소 개수 반환
	auto c = count_if(v.begin(), v.end(), [](int a) { return a > 3 && a < 10; });
	cout << c << endl; // 

	vector<int> vv(v.size()); // 공간 확보
	copy(v.begin(), v.end(), vv.begin());

	print(vv.begin(), vv.end());

	// 내림차순 정렬
	sort(vv.begin(), vv.end(), greater<int>());
	print(vv.begin(), vv.end());

	// 중복된 요소 뒤로 보내기
	auto unique_it = unique(vv.begin(), vv.end());
	print(vv.begin(), vv.end());

	// 중복된 요소를 뒤로 보낸 후에 resize를 통하여 중복 요소 제거
	vv.resize(distance(vv.begin(), unique_it));
	print(vv.begin(), vv.end());

	// 절대값으로 오름차순 정렬
	sort(vv.begin(), vv.end(), [](int a, int b) { return abs(a) < abs(b); });
	print(vv.begin(), vv.end());

}

// output
처음으로 양수가 나오는 요소
5

(3, 10) 구간에 해당하는 요소의 개수
3

복사 후의 vv 벡터 요소
-3      -1      5       -9      7       -1      5       -3      -1

내림차순 정렬
7       5       5       -1      -1      -1      -3      -3      -9

unique 결과
7       5       -1      -3      -9      -1      -3      -3      -9

resize 결과 (중복 요소 제거)
7       5       -1      -3      -9

절댓값으로 오름차순 정렬
-1      -3      5       7       -9

---

알고리즘 문제를 풀 때, 반복자를 잘 활용하면 유용할 것이다.