STL : vector & iterator

vector 는 배열과 비슷하다고 보면 된다.

배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(sequence container)에 해당이 된다. 

벡터는 가변길이 배열이라고도 할 수 있으며, 메모리상에서 순차적으로 저장되어 있고, 이에 따라 

임의 위치에 있는 원소에 접근하는것에 용이함.

 맨뒤에 원소를 추가하거나 제거하는것은 O(1) 의 시간복잡도를 가지나, 

임의의 위치에 원소를 추가하거나 제거하는 것은 O(n)으로 느리다. 

이유는 어떤 자리에 새로운 원소를 추가하거나 뺄 경우 그 뒤에 오는 원소들을 한칸씩 이동시켜줘야하기에,

n번의 복사가 필요하기 때문이다.

 

(사용)

- 임의 원소에 접근하는 것은 [ ], at 함수를 이용하여 접근 가능 

 

- 맨뒤에 원소를 추가하거나 제거하기 위해선 push_back, pop_back 함수를 사용하면 된다.

 

- 임의의 위치 원소 추가 및 제거(insert, erase)

 

예제) 

 

#include <iostream> 
#include <vector>

using namespace std;

int main() { 
	vector<int> vec; 
    vec.push_back(10); // 맨 뒤에 10 추가 
    vec.push_back(20); // 맨 뒤에 20 추가 
    vec.push_back(30); // 맨 뒤에 30 추가 
    vec.push_back(40); // 맨 뒤에 40 추가
    
	for (vector<int>::size_type i = 0; i < vec.size(); i++) { 
    cout << "vec 의 " << i + 1 << " 번째 원소 :: " << vec[i] << endl; 
    }
    return 0;
}

(출력 결과)

 

이러한 vector 컨테이너 (컨테이너는 담는 공간이라고 생각하면 된다) 에 접근하기 위해 Iterator(반복자) 개념이 필요.

iterator 는 컨테이너 원소에 접근할 수 있는 포인터와 같은 객체라고 볼수 있다. 

vector의 경우 begin(), end() 함수를 이용하여 반복자를 얻을수 있다. 

 

- begin() : vector의 첫번째 원소

 

- end() : vector의 마지막 원소 다음 위치 (이를 통해 빈벡터 표현 가능 / end() 가 마지막 원소 가리킨다면 원소 없는 빈 벡터라는 뜻)

 

// 반복자 사용 예시 
#include <iostream> 
#include <vector>

using namespace std;

int main() {
	vector<int> vec; 
	vec.push_back(10);
	vec.push_back(20); 
	vec.push_back(30); 
	vec.push_back(40);
	// 전체 벡터를 출력하기 
	for (vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) { 
		cout << *itr << endl; 
	}
	//배열로 따지면 아래와 같은 개념
	// int arr[4] = {10, 20, 30, 40} 
	// *(arr + 2) == arr[2] == 30; 
	// *(itr + 2) == vec[2] == 30;
	vector<int>::iterator itr = vec.begin() + 2; 
	cout << "3 번째 원소 :: " << *itr << std::endl;
	
	return 0;
}

(출력결과)

 

코드를 보면 반복자 타입은 위처럼 vector<타입>::iterator 멤버 타입으로 정의되어 있고, vec.begin(), vec.end() 함수가 이를 리턴하는 모습을 볼수 있다. end()가 vector의 마지막 원소 바로 뒤를 가리키기 때문에 for 문에서 vector 전체 원소를 보고 싶다면 vec.end()가 아닐때까지 반복하면 된다. 

앞서 반복자를 포인터처럼 사용한다고 했는데, 실제로 현재 반복자가 가리키는 원소의 값을 보려면 

cout << *itr << endl;

* 연산자를 이용해 itr 이 가리키는 원소를 볼 수 있다. 

itr은 실제 포인터가 아니고 *연산자를 오버로딩해서 마치 포인터처럼 동작하게 만든것이다. 

* 연산자는 itr이 가리키는 원소의 레퍼런스를 리턴한다. 

vector<int>::iterator itr = vec.begin() + 2; 
cout << "3 번째 원소 :: " << *itr << endl;

 또한 반복자 역시 +연산자를 통해 그 만큼 떨어져 있는 원소를 가리키게 할수도 있다. 

배열을 가리키는 포인터와 똑같이 동작한다고 보면 됨.

반복자를 이용하여 아래 예와 같은 insert, erase 함수도 사용할 수 있다.

#include <iostream> 
#include <vector>

using namespace std;

template <typename T>
void print_vector(vector<T>& vec) {
	// 전체 벡터를 출력하기 
	for (typename vector<T>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
		cout << *itr << endl;
	}
}
int main() {
	vector<int> vec;
	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(30);
	vec.push_back(40);
	cout << "처음 벡터 상태" << endl;
	print_vector(vec);
	cout << "----------------------------" << endl;
	// vec[2] 앞에 15 추가 
	vec.insert(vec.begin() + 2, 15);
	print_vector(vec);
	cout << "----------------------------" << endl;
	// vec[3] 제거 
	vec.erase(vec.begin() + 3);
	print_vector(vec);

	return 0;
}

 

(출력결과)

 

예제 실행으로 위와 같은 결과가 나오는 것을 볼수 있다. 

참고로 템플릿 버젼의 경우 

for (typename vector<T>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {

 

 

위와 같이 typename을 붙여야 하며, 이는 iterator가 vector<T>의 의존 타입이기 때문이다. 

 

// vec[2] 앞에 15 추가 
vec.insert(vec.begin() + 2, 15);

insert 함수의 경우 위처럼, 인자로 반복자를 받고, 그 반복자 앞에 원소를 추가해 준다. 

위 경우, vec.begin() + 2 앞에 15를 추가하므로 10, 20, 30, 40 에서 10, 20, 15 30 40 이 된다.

 

vec.erase(vec.begin() + 3); 
print_vector(vec);

 erase 역시 인자로 반복자를 받고, 그 반복자가 가리키는 원소를 제거한다.

위 경우 4번째 원소인 30이 지워진다. 

 

참고로 vector에서 반복자로 erase나 insert함수를 사용시 주의할점이 있다.

다음 예제를 보자.

#include <iostream> 
#include <vector>

using namespace std;

template <typename T> 
void print_vector(vector<T>& vec) { 
	// 전체 벡터를 출력하기 
	cout << "[ "; 
	for (typename vector<T>::iterator itr = vec.begin(); itr != vec.end(); ++itr) { 
		cout << *itr << " "; 
	} 
	cout << "]"; 
} 
int main() { 
	vector<int> vec; 
	vec.push_back(10); 
	vec.push_back(20); 
	vec.push_back(30);
	vec.push_back(40);
	vec.push_back(20);
	cout << "처음 벡터 상태" << endl; 
	print_vector(vec);
	vector<int>::iterator itr = vec.begin(); 
	vector<int>::iterator end_itr = vec.end();
	for (; itr != end_itr; ++itr) { 
		if (*itr == 20) { 
			vec.erase(itr);
		} 
	}
	cout << "값이 20 인 원소를 지운다!" << endl;
	print_vector(vec);

	return 0;
}

위 예제를 실행시키면 오류가 발생할것이다. 

이 오류가 발생하는 이유는 

for (; itr != end_itr; itr++) { 
	if (*itr == 20) { 
		vec.erase(itr); 
    } 
}

위 코드에서 발생한다. 

컨테이너에 원소를 추가하거나 제거하게 되면 기존에 사용하였던 모든 반복자들을 사용할 수 없게 된다.

다시말해 위 경우, vec.erase(itr)을 수행하게 되면 더이상 itr은 유효한 반복자가 아니게 된다.

또한 end_itr 역시 무효화 된다. 

따라서 itr != end_itr이 영원히 성립되어 무한 루프에 빠지므로, 위같은 에러가 발생한다.

 

위 코드를 아래와 같이 고치면 해결될까?

vector<int>::iterator itr = vec.begin(); 
for (; itr != vec.end(); itr++) { 
	if (*itr == 20) { 
    	vec.erase(itr); 
    } 
}

실행해보면 여전히 같은 오류가 발생한다. 

이유는 itr이 유효한 반복자가 아니기 때문에 vec.end() 로 올바른 end 반복자값을 매번 갖고 와도

for 문이 끝나지 않게 되기 때문이다. 결과적으로 코드를 제대로 고치려면 아래와 같이 해야한다.

 

vector<int>::iterator itr = vec.begin();
for (; itr != vec.end(); ++itr) { 
	if (*itr == 20) { 
    	vec.erase(itr); 
        itr = vec.begin(); 
    } 
}

 

성공적으로 실행하면 위와같이 나온다.

그러나 위 코드는 꽤 비효율적이다. 20인 원소를 지우고 다시 처음으로 가서 원소를 찾기 때문이다.

바로 20인 원소 바로 다음 위치부터 찾아가면 더 효율적일것이다.

 

for (vector<int>::size_type i = 0; i != vec.size(); i++) { 
	if (vec[i] == 20) { 
    	vec.erase(vec.begin() + i); 
        i--; 
    } 
}

위 코드와 같이 굳이 반복자를 쓰지 않고 erase 함수에만 반복자를 만들어서 전달하면 된다

vec.erase(vec.begin() + i)

이렇게 하면 vec[i]를 가리키는 반복자를 erase에 전달할 수 있다. 

하지만 위 방법은 그리 권장하지 않는다. 

위 방법은 원소 접근하는 방식을 iterator(반복자)를 사용하는것으로 정한것을 쓰지 않고, 기존 배열처럼 정수형 변수 i로 원소에 접근하는것이기 때문이다. 

 

vector 에서 지원하는 반복자로 const_iterator가 있다. 이는 마치 const 포인터라 생각하면 된다. 

즉 const_iterator의 경우 가리키고 잇는 원소의 값을 바꿀수 있다. 

아래 코드를 보자. 

 

#include <iostream> 
#include <vector>
using namespace std;

template <typename T> 

void print_vector(vector<T>& vec) { 
	// 전체 벡터를 출력하기 
	for (typename vector<T>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
		cout << *itr << endl; 
	} 
} 
int main() { 
	vector<int> vec; 
	vec.push_back(10); 
	vec.push_back(20); 
	vec.push_back(30); 
	vec.push_back(40);
	cout << "초기 vec 상태" << endl; 
	print_vector(vec);
	// itr 은 vec[2] 를 가리킨다. 
	vector<int>::iterator itr = vec.begin() + 2;
	// vec[2] 의 값을 50으로 바꾼다. 
	*itr = 50;
	cout << "---------------" << endl; 
	print_vector(vec);
	vector<int>::const_iterator citr = vec.cbegin() + 2;
	// 상수 반복자가 가리키는 값은 바꿀수 없다. 불가능! 
	*citr = 30;

	return 0;
}

 위 코드의 경우 const 반복자가 가리키고 있는 값은 바꿀 수 없다고 오류가 뜰것이다. 

const 반복자의 경우

vector<int>::const_iterator citr = vec.cbegin() + 2;

 위와 같이 cbegin과 cend 함수를 이용하여 얻을 수 있다. 

많은 경우 반복자의 값을 바꾸지 않고 참조만 하는 경우가 많으므로, const iterator를 적절히 이용하는것 좋다.

 

vector에서 지원하는 반복자는 마지막으로 역반복자 (reverse iterator)가 있다. 

이는 반복자와 똑같지만, 벡터 뒤에서부터 앞으로 거꾸로 간다는 특징이 있다. 

아래 코드를 보자.

 

#include <iostream> 
#include <vector>

using namespace std;

template <typename T> 
void print_vector(vector<T>& vec) { 
	// 전체 벡터를 출력하기 
	for (typename vector<T>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
		cout << *itr << endl; 
	} 
}
int main() { 
	vector<int> vec; 
	vec.push_back(10); 
	vec.push_back(20); 
	vec.push_back(30); 
	vec.push_back(40);
	cout << "초기 vec 상태" << endl;
	print_vector(vec);
	cout << "역으로 vec 출력하기!" << endl; 
	// itr 은 vec[2] 를 가리킨다. 
	vector<int>::reverse_iterator r_iter = vec.rbegin(); 
	for (; r_iter != vec.rend(); r_iter++) { 
		cout << *r_iter << endl; 
	}
	return 0;
}

 

실행을 해보면 위와 같이 벡터의 원소들을 역으로 출력할 수 있다.

이전에 반복자의 end()가 맨 마지막 원소의 바로 뒤를 가리켰던 처럼, 역 반복자의 rend()역시 맨앞 원소의 바로 앞을 가리키게 된다. 또한 반복자의 경우 값이 증가하면 뒤쪽 원소로 가는것처럼, 역반복자의 경우 값이 증가하면 앞쪽원소로 가게된다. 

또 반복자가 상수 반복자가 있는 것처럼 역반복자 역시 상수 역반복자가 있다. 그 타입은 const_reverse_iterator 타입이고, crbegin(), crend()로 얻을 수 있다.

역반복자를 사용하는 것은 매우 중요하다. 

 

아래 코드를 보자

#include <iostream> 
#include <vector>

using namespace std;

int main() {
	vector<int> vec; 
	vec.push_back(1); 
	vec.push_back(2); 
	vec.push_back(3);
	// 끝에서 부터 출력하기 
	for (vector<int>::size_type i = vec.size() - 1; i >= 0; i--) { 
		cout << vec[i] << endl; 
	}
	return 0;
}

 위 코드를 실행하면 에러가 발생한다. 

맨 뒤의 원소부터 제대로 출력하는 코드같지만, 위는 vector의 index를 담당하는 타입이 부호없는 정수이기 때문에 타입이 안맞아서 문제가 발생한다. 

따라서 i가 0일때, i--를 하면 -1 되는것이 아니라 해당 타입에서 가장 큰 정수가 되버린다.

따라서 for문을 영원히 종료할 수 없다.

이 문제를 해결하기 위해선 부호있는 정수로 선언해야 하는데, 이 경우 vector의 index타입과 일치하지 않아서 타입 캐스팅을 해야 한다는 문제가 발생한다.

따라서 역으로 원소를 참조하고 싶다면 역반복자를 사용하는것이 가장 좋다.