둘 다 iterator가 존재하는 컨테이너에 사용할 수 있다. (vector, array...)

find는 원소를 비교할 때 operator==를 사용한다. 즉, operator==가 존재하지 않는 pair의 경우 컴파일 에러가 나온다.

이럴때는 find_if를 통해 찾으려는 값 대신 custom method를 넘겨줄 수 있다.

// t가 pair인 경우 컴파일 에러 발생
auto iter = find_if(v.begin(), v.end(), t);

auto iter = find_if(v.begin(), v.end(), [&t](const pair<int, int>& elem) { return elem.first == t; });

next_permutation

현재 나와있는 수열에서 다음 순열을 구하고 true를 반환. 다음 순열이 없다면 false를 반환.

prev_permutation

현재 나와있는 수열에서 이전 순열을 구하고 true를 반환. 이전 순열이 없다면 false를 반환.

배열의 경우 시작인덱스와 끝 인덱스, 벡터의 경우 iterator를 인자로 넘겨주면 된다.

	int a[3] = { 1, 2, 3 };

	do {
		for (int i = 0; i < 3; ++i)
			cout << a[i];
		cout << '\n';
	} while (next_permutation(a, a + 3));

	/*
	123
	132
	213
	231
	312
	321
	*/

// 4개의 수 중에서 2개를 순서없이 뽑는 조합
// n개의 수 중에서 m개의 수로 조합을 뽑는 경우라면 원소의 개수를 n, 0을 m개만큼 넣어두면 된다
int a[4] = { 0, 0, 1, 1 };

	do {
		for (int i = 0; i < 4; ++i) {
			if (a[i] == 0)
				cout << i + 1;
		}
		cout << '\n';
	} while (next_permutation(a, a + 4));

	/*
	12
	13
	14
	23
	24
	34
	*/

교집합 : set_intersection

합집합 : set_union

차집합 : set_difference

집합을 수행할 두개의 컨테이너는 정렬이 되어있어야 한다.

정렬이 되어있지 않은 상태에서 수행시 Sequence not oredered 런타임 오류를 뱉는다.

두 집합의 결과를 저장할 컨테이너의 크기가 미리 확보되어 있어야 한다.

두 집합이 수행된 끝의 다음 iterator가 반환되는데 이걸로 남는 공간을 지워주면 된다.

auto iter = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
v3.erase(iter, v3.end());

unordered_map (=hash_map), unordered_set (=hash_set)

연관 컨테이너이다.

괄호안의 이름 그대로 해시를 이용한다. 다만 hash_map과 hash_set 사용 시 더이상 사용되지 않으며 곧 삭제될테니 unordered_map, unordered_set을 사용하라는 컴파일러의 에러메시지가 출력된다.

hash_ 는 비표준 컨테이너, unordered_ 는 표준 컨테이너이다.. 기능은 거의 유사하다.

unordered가 붙고 안붙고의 차이는 이름 그대로 정렬여부이다.

map, set은 레드블랙 트리 기반으로 구현되어 있어서 데이터가 정렬되어 저장되며 O(logN)의 시간 복잡도를 가진다.

unordered_map, unordered_set은 정렬이 되어있지 않고 hash 값으로 탐색하기 때문에 O(1)의 시간 복잡도를 가진다.

unordered_map을 일반적인 hash table로 사용한다.

공통점은 중복값을 허용하지 않는다는 것이다. unordered_map을 hash table로 사용시 해시 충돌이 발생하지 않도록 주의 해야하고 해시 충돌을 허용하려면 unordered_multimap을 사용해야 한다.

map과 set의 차이는 value가 있느냐 없느냐이다.

set은 key와 value가 같은 map이라고 생각해도 된다.

unordered_map<string, int> hash_table;

// 모두 동일한 기능
hash_table.insert(make_pair("first", 1));
hash_table.insert({"second", 2});
hash_table["third"] = 3; // key에 third가 있는지 검사후 없으면 insert

key로 value에 접는하는것은 operator[] 또는 at을 이용하면 되지만 value로 key에 접근하는것은 모든 원소를 순회해서 찾아야 해서 비효율적이다.

그렇기 때문에 value를 key로 찾아야하는 일이 발생하면 key-value의 타입을 서로 바꾼 inverse map/set을 하나 더 생성해서 관리하면 된다.

value가 단순 인덱스의 역할을 한다면 inverse map/set 대신 vector 등의 배열을 이용하여 사용할 수도 있다.

+

BOJ 10816 (숫자 카드 2) 를 풀면서 나온 결과인데, unordered_set과 count를 이용하니 시간초과가 나오지만 vector를 한번 정렬시킨 후 이진탐색으로 개수를 찾아나가는건 정답처리가 되었다.

아무래도 값을 삽입하는 과정에서 해시충돌이 일어날 때 시간초과의 원인이 되는 것 같다.

값을 찾으면 해당 값의 iterator를 반환해준다.

해당 값의 인덱스를 알고싶다면 begin을 빼주면 된다.

만약 값을 찾지 못하면 end가 반환된다.

find(iter_begin, iter_end, target) // 찾은 값의 iterator 반환

find(iter_begin, iter_end, target) - iter_begin; // 찾은 값의 index