C++ - 컨테이너와 반복자 (Container and Iterator)

C, C++ 전체 링크

 

C++의 표준 템플릿 라이브러리 (STL, Standard Template Library)는 아래와 같이 구성된다.

 

- 컨테이너(Container) : 객체를 저장하는 객체, 컬렉션, 자료구조.

- 반복자(Iterator) : 컨테이너의 원소에 접근하여 다음 원소를 가리킨다.

- 알고리즘 : 연산, 검색, 삭제, 정렬 제공.

- 함수 객체(Function Object) : operator의 오버로딩.

- 어댑터(Adapter) : 인터페이스를 변경하여 새로운 인터페이스로 변경.

- 할당기(Allocator) : 메모리 할당에 대한 클래스 객체

---

컨테이너는 같은 타입을 저장하고 관리할 수 있는 클래스이다.

각 컨테이너는 자신만의 삽입순서를 가진다.

 

Sequence Container - vector, list, deque

Associative Container - set, multiset, map, multimap

 

반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 방법을 제공한다.

---

vector는 동적 배열로 볼 수 있기 때문에 index로도 접근 가능하고, 반복자(iterator)로도 접근할 수 있다.

반복자는 포인터와 비슷하게 동작하며 내부 객체에 접근할 때 * 연산이 필요하다.

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	vector<int> vec;
	for (int i = 0; i < 10; i++) vec.push_back(i);

	/* index로 접근 */
	for (int i = 0; i < vec.size(); i++) printf("%d ", vec[i]);
	putchar('\n');
    
	/* 반복자로 접근 */
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) printf("%d ", *it);
	putchar('\n');

	return 0;
}

---

map은 tree의 자료구조를 가진다.

map<key, value>로 자료를 저장하고, key를 이용하여 value에 접근할 수 있다.

key가 int인 mymap1에 값을 넣고 iterator로 접근해보자.

#include <stdio.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(void)
{
	map<int, string> mymap1;

	mymap1[1] = "one"; mymap1[2] = "two"; mymap1[-1] = "minus_one";
	mymap1[10] = "ten"; mymap1[0] = "zero";

	for (map<int, string>::iterator it = mymap1.begin(); it != mymap1.end(); it++)
		printf("key:[%d], value:[%s]\n", it->first, it->second.c_str());

	return 0;
}

key가 작은 순서대로 접근하는 것을 알 수 있다.

즉, key가 작은 순서대로 map이 key를 정렬한다.

 

반대로 key가 string인 경우를 출력하면 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(void)
{
	map<string, int> mymap2;

	mymap2["one"] = 1; mymap2["two"] = 2; mymap2["minus_one"] = -1;
	mymap2["ten"] = 10; mymap2["zero"] = 0;

	for (map<string, int>::iterator it = mymap2.begin(); it != mymap2.end(); it++)
		printf("key:[%s], value:[%d]\n", it->first.c_str(), it->second);

	return 0;
}

key가 사전 순서대로 정렬되어있다. 즉, string은 default로 사전 순으로 정렬한다.

 

하지만 만약 key가 구조체라면 ?

이 경우에는 구조체의 크기를 비교하는 operator < 를  재정의해서 map에 구조체의 비교 방법을 알려줘야 한다.

아래의 경우는 number1이 작을수록, number2는 클수록 정렬되도록 operator를 overloading 하였다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;

typedef struct KEY
{
	int number1;
	int number2;

	bool operator < (const KEY& key) const
	{
		if (number1 < key.number1) return true;
		if (number1 == key.number1 && number2 > key.number2) return true;

		return false;
	}
};

int main(void)
{
	map<KEY, int> mymap3;

	KEY key[10] = { 0 };

	key[0].number1 = 5; key[0].number2 = 1;
	key[1].number1 = 5; key[1].number2 = 2;
	key[2].number1 = -1; key[2].number2 = 3;
	key[3].number1 = -1; key[3].number2 = 4;
	key[4].number1 = 2; key[4].number2 = 5;

	mymap3[key[0]] = 100;
	mymap3[key[1]] = 200;
	mymap3[key[2]] = 300;
	mymap3[key[3]] = 400;
	mymap3[key[4]] = 500;

	for (map<KEY, int>::iterator it = mymap3.begin(); it != mymap3.end(); it++)
		printf("key:[%d/%d], value:[%d]\n", it->first.number1, it->first.number2, it->second);

	return 0;
}

 

따라서 원하는 방법으로 정렬할 수 있도록 operator를 정의하면 된다.

---

만약 operator를 아래와 같이 재정의하면 invalid comparator 에러가 발생한다. (예제 key를 삽입할 경우에 발생)

typedef struct KEY
{
	int number1;
	int number2;

	bool operator < (const KEY& key) const
	{
		if (number1 < key.number1) return true;
		if (number2 > key.number2) return true;

		return false;
	}
};

 

key[2] = (-1, 3) = A, key[4] = (2, 5) = B 라고 하자.

 

A < B는 -1 < 2 == true [number1 비교]로 A < B는 true다.

B < A는 2 < -1 == false [number1 비교]로 다음 비교로 넘어가고 5 > 3 == true [number2 비교]로 true가 된다.

 

따라서 A < B도 true, B > A도 true인 상황 때문에 invalid comparator 에러가 발생하였다.

map이 어떤 key가 큰지 판단할 수 없어서 에러를 발생한다. 그러므로 operator 선언 시 주의해야 한다.

아래와 같이 선언하면 B < A는 number2를 비교하지 않기 때문에 올바른 값인 false를 return한다.

typedef struct KEY
{
	int number1;
	int number2;

	bool operator < (const KEY& key) const
	{
		if (number1 < key.number1) return true;
		
		//if (number2 > key.number2) return true; << 잘못된 정의
		if (number1 == key.number1 && number2 > key.number2) return true;

		return false;
	}
};

 

invalid comparator는 런타임에 발생하기 때문에,

위와 같이 A > B, B < A 모두 true인 경우가 발생하지 않으면 언제 런타임 에러가 발생할 지 알 수가 없다.

 

이러한 상황을 막기 위해 operator를 재정의, 즉 비교 연산을 재 정의할 때 필요한 규칙이 있다.

 

1) comp(A, A)는 거짓이어야 한다.

2) comp(A, B)가 참이면 comp(B, A)는 거짓이어야 한다.

3) comp(A, B)가 참, comp(B, C)가 참이면 comp(A, C)도 참이어야 한다.

4) comp(A, B)가 거짓, comp(B, A)가 거짓일 때,

   comp(B, C)와 comp(C, B)가 거짓이면, comp(A, C)와 comp(C, A)도 거짓이다.

 

위 조건을 모두 만족하면 Strick Weak Ordering을 만족한다고 한다.

 

여기서 재정의한 operator < 도 위 4가지 조건을 만족한다.

따라서 Strick Weak Ordering을 만족하도록 operator를 재정의해야 invalid comparator 에러를 피할 수 있다.