[C/C++] 표준 템플릿 라이브러리(STL) - (2)

C++ STL

• 연관 컨테이너

-  시퀀스 컨테이너와는 다르게 키(key) - 값(value) 구조를 가진다.

=>  특정한 키를 넣으면 이에 대응되는 값을 돌려준다.
==>  템플릿 라이브러리 이기 때문에 키와 값 모두 임의의 타입의 객체가 될 수 있다.

-  특정 키가 연관 컨테이너에 존재하는지 유무를 처리할 수 있는 것은 셋(set)과 멀티셋(multiset)

-  특정 키에 대응되는 값이 무엇인지에 대한 처리는 맵(map)과 멀티맵(multimap)

-  맵과 멀티맵을 셋 처럼 사용할 수도 있다.

=>  맵의 경우 셋 보다 사용하는 메모리가 크기 때문에 키의 존재 유무만 궁금하다면 셋을 사용하는 것이 좋다.

 

• 셋(set)

-  insert 함수

=>  셋에 원소를 추가한다.
==>  시퀀스 컨테이너와 달리 '어디에' 추가할지에 대한 정보는 없다.
==>  셋은 집합안에 원소가 '있냐/없냐'만을 따진다.

-  셋에 원소를 추가/제거하는 작업은 O(logN)

=>  시퀀스 컨테이너의 경우 임의의 원소를 지우는 작업이 O(N)
==>  셋이 훨씬 빠르다.

-  반복자를 제공한다.

=>  BidirectionalIterator
==>  임의의 위치에 있는 원소에 접근하는 것은 불가능하고 순차적으로 하나씩 접근해야 한다.

-  셋의 경우 내부에 원소를 추가할 때 정렬된 상태를 유지하며 추가한다.

ex)  10 - 50 - 20 순서로 값을 추가해도 출력에서 나오는 순서는 10 - 20 - 50 이다.
=>  시퀀스 컨테이너와는 다르게 원소를 추가하는 작업이 O(logN)으로 진행된다.

-  find 함수

=>  셋에 원소가 존재하는지 아닌지 확인할 때 사용한다.
==>  원소가 존재한다면 이를 가리키는 반복자를 리턴하고 존재하지 않는다면 set.end()를 리턴한다.
=>  vector였다면 원소 존재 유무를 확인하기 위해 처음부터 끝까지 순회해야 했을 것. ( vector에서 find는 O(N))
=>  셋의 경우 find는 O(logN)이다.
==>  셋 내부적으로 원소들이 정렬된 상태를 유지하기 때문(내부적으로 트리 구조로 구성되어 있다)

-  셋 안에는 중복된 원소들이 없다.

ex) 10 - 20 - 20 - 30 을 추가해도 나오는 출력값은 10 - 20 - 30 뿐이다.

=>  셋 자체적으로 내부에 같은 원소가 있다면 insert 하지 않는다.

 

• 임의의 클래스 객체를 셋에 추가할 때

-  operator < 를 정의해야 한다.

=>  셋은 원소들을 지정할 때 내부적으로 정렬된 상태를 유지하기 때문. (정렬을 위해서는 원소 간의 비교를 수행해야 한다)

-  셋 내부에서 두 원소가 같냐 다르냐를 판별하는 방법

=>  A, B가 셋 내부에 있다면 A < B 와 B < A 가 모두 false일 때 두 원소가 같다고 판단함.
==>  A == B 를 사용하는 것이 아님.

-  operator< 를 설계할 때 반드시 다른 객체는 operator< 상에서도 구분될 수 있도록 만들어야 한다.

operator<  는 다음과 같은 조건들을 만족해야 합니다. (출처 : 씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map> (modoocode.com))

=>  위와 같은 조건을 만족하는 < 연산자는 strict weak ordering을 만족한다고 한다.

=>  조건 중 하나라도 맞지 않는다면 set이 제대로 동작하지 않는다.
==>  컴파일 타임에는 오류가 발생하지 않고, 런타임 상에서 오류가 발생하여 디버깅이 매우 힘들어진다.

-  operator< 를 정의하지 않고 셋을 사용하는 방법

=>  셋 내부에서 비교를 수행할 함수 객체를 만들고 셋을 호출할 때 템플릿 인자의 두번째 인자로 넘겨준다.
ex)  std::set<Test, TestCmp> tests;

-  결과적으로 셋은 원소의 삽입과 삭제, 탐색을 O(logN)에 수행하는 자료 구조이다.

 

• 맵(map)

-  셋과 거의 똑같음.

=>  셋은 키만 보관했지만 맵의 경우 키에 대응되는 값(value)까지도 같이 보관한다.

-  맵의 경우 템플릿 인자로 2개를 가진다. 첫번째는 키 타입, 두번째는 값의 타입

-  insert 함수

=>  맵에 원소를 넣기 위해서는 반드시 std::pair 객체를 전달해야 한다.
=>  맵의 경우 operator[] 를 이용해서 새로운 원소를 추가할 수도 있다.
==>  해당하는 키가 맵에 없다면 추가되는 것이고, 이미 있다면 값이 대체된다.

 

※ std::pair 객체는 아래처럼 생긴 단순히 2개의 객체를 맴버로 가지는 객체이다.
template <class T1, class T2>
struct std::pair {
  T1 first;
  T2 second;
};

※  std::make_pair 함수
=>  std::pair 객체를 사용할 때마다 템플릿 인자를 초기화 해야하는 것이 불편해서 제공되는 함수
ex) std::pair<std::string, double>("홍길동", 3.14);  =>  std::make_pair("홍길동", 3.14);
=>  인자로 들어오는 객체를 보고 타입을 추측해서 알아서 std::pair 객체를 만들어서 리턴해준다.

-  맵의 경우도 셋과 마찬가지로 반복자를 이용해서 순차적으로 맵에 저장되어 있는 원소들을 탐색할 수 있다.

=>  셋의 경우 *itr가 저장된 원소를 바로 가리킨 반면, 맵의 경우 반복자가 맵에 저장되어 있는 std::pair 객체를 가리킨다.
==>  itr->first 를 하면 해당 원소의 키를, itr->second를 하면 해당 원소의 값을 알 수 있다.

-  범위 기반 for문으로도 사용할 수 있다.

=>  반복자를 사용한 형태보다 더 간단하므로 권장된다.
ex) for(const auto& kv : m) {...}  kv에는 맵의 key와 value가 std::pair로 들어간다.
kv. first, kv.second를 이용해서 참조할 수 있다.

-  맵에 저장된 값을 찾을 때는 [] 연산자 이용.

ex) m["홍길동"] 과 같이 사용하면 홍길동 키에 대응되는 값을 찾을 수 있다.

-  [] 연산자는 맵에 없는 키를 참조하게 되면 자동으로 값의 티폴트 생성자를 호출해서 원소를 추가해버린다.

=>  find 함수로 원소의 키 존재 유무를 먼저 확인한 후 값을 참조하는 것이 좋다.
==>  set의 find 함수와 사용법은 동일하다.

-  맵 역시 셋처럼 중복된 원소를 허락하지 않는다.

=>  중복된 원소의 insert는 무시된다.
==>  여기서 중복이란 키의 중복을 의미한다.
==>  특정 키에 대응되는 값을 변경하려면 [] 연산자를 사용하면 된다.

-  맵 또한 내부적으로 정렬되어서 저장된다.

• 멀티셋(multiset)과 멀티맵(multimap)

-  멀티셋과 멀티맵은 중복된 원소를 허락한다.

=>  기존의 셋과 맵은 중복된 원소를 허락하지 않았다.

-  멀티맵의 경우 [] 연산자를 사용할 수 없다.

=>  한 개의 키에 여러개의 값이 대응될 수 있기 때문

-  또한, 중복된 원소를 find 함수를 이용해서 찾을 경우 무엇을 리턴할지 정해지지 않았다.

=>  라이브러리에 따라, 컴파일러에 따라 다른 값이 나올 수도 있다. 유의해야함.

-  equal_range 함수

=>  멀티맵의 키를 받은 뒤에, 해당 키에 대응되는 원소들의 반복자들 중에서 시작과 끝 바로 다음을 가리키는 반복자를 std::pair 객체로 만들어서 리턴한다.

 

• 정렬되지 않은 셋과 맵(unordered_set, unordered_map)

-  이름에서도 알 수 있듯이 원소들이 정렬되어 있지 않다.

=>  들어간 순서대로 저장되는 것이 아니라 말 그대로 랜덤한 순서로 저장되어 있음.
==>  출력해보면 랜덤한 순서대로 출력되는 것을 알 수 있다.

-  unordered_set의 insert, erase, find 모두가 O(1)으로 수행된다.

=>  셋이나 맵의 경우 O(logN) 이었지만, unordered_set, unordered_map 의 경우 상수 시간에 원소를 삽입, 검색할 수 있다.

 

※  해시 함수(Hash function)
-  unordered_set, unordered_map은 원소의 삽입, 검색을 위해 먼저 해시 함수라는 것을 사용한다.

-  해시 함수란 임의의 크기의 데이터를 고정된 크기의 데이터로 대응시켜주는 함수다.
=>  보통 고정된 크기의 데이터란 일정 범위의 정수값을 의미한다.

-  "같은 원소를 해시 함수에 전달한다면 같은 해시값을 리턴한다."
=>  원소의 탐색을 빠르게 수행할 수 있다.

-  서로 다른 원소임에도 불구하고 같은 해시값을 갖는 경우를 "해시 충돌(hash collision)"이라 한다.

-  해시 함수는 최대한 1부터 N(상자 개수)까지 고른 값을 반환해야 하며, 상자의 수도 충분히 많아야 상수 시간 탐색을 보장할 수 있다.

-  unordered_set과 unordered_map의 경우 평균적으로 O(1) 시간으로 원소의 삽입/탐색을 수행 가능하지만 최악의 경우 O(N)이 될 수 있다.
=>  최악의 경우 모든 원소가 하나의 해시값에 할당되면 탐색은 O(N) 시간이 소요된다.
=>  일반적인 set과 맵은 평균, 최악 모든 경우에 O(logN) 시간이다.

-  일반적인 경우 맵이나 셋을 사용하고, 최적화가 매우 중요한 작업일 경우 해시 함수를 잘 설계해서 unordered_set과 unordered_map을 사용한다.

-  메모리 낭비 방지를 위해 상자(해시 값)의 개수는 삽입되는 원소가 많아짐에 따라 점진적으로 늘어난다.
=>  상자의 개수가 늘어나면 해시 함수를 바꿔야 하므로(더 많은 값들을 해시값으로 변환 가능하도록) 모든 원소들을 처음부터 끝까지 다시 insert 해야한다.
==>  이를 rehash라 하며 O(N) 시간이 소요된다.

 

-  unordered_set과 unordered_map 모두 find 함수를 지원한다.

=>  사용법은 일반적인 셋과 동일하다.

=>  원소를 제거하고 싶다면 find 함수로 원소를 가리키는 반복자를 찾은 후 이를 전달해서 바로 삭제하면 된다.

 

• custom 클래스를 'unordered_set/unordered_map'의 원소로 넣고 싶을 때

-  내 클래스의 객체를 위한 '해시 함수'를 직접 만들어야 한다.

=>  일반적인 셋과 맵의 경우보다 훨씬 어렵다.
==>  셋과 맵을 사용하는 것을 권장하는 이유이다.

-  operator== 가 필요하다.

=>  해시 충돌 발생 시에 상자안에 있는 원소들과 비교를 해야한다.
=>  정렬이 필요하지 않으므로 operator< 는 필요하지 않다.

-  C++에서 기본적인 타입들에 대한 해시 함수를 제공한다.

-  해시 함수 계산을 위해 hash 함수 객체를 사용한다.

-  좋은 해시 함수를 제작하는 일은 어렵다.

=>  해시 함수의 성능을 정확히 검증할 수 없다면, map이나 set을 사용하는 것이 낫다.

 

• 어떤 컨테이너를 사용할지?

-  데이터의 존재 유무만 궁금하다 : set

-  중복 데이터를 허락한다 : multiset

=>  insert, erase, find 모두(평균, 최악 모두), O(logN)

 

-  데이터에 대응되는 데이터를 저장하고 싶은 경우 : map

 

-  중복 키를 허락할 경우 : multimap

=>  insert, erase, find 모두(평균, 최악 모두) O(logN)

 

-  속도가 매우매우 중요해서 최적화를 해야하는 경우 : unordered_set, unordered_map

=>  (insert, erase, find 모두 평균 O(1), 최악의 경우 O(N)

==>  해시 함수와 상자의 개수를 잘 설정해야함

 

 

 

 

---

 

 

 

 

틀린 부분이나 이상한 부분이 있으면 댓글로 편하게 지적해주세요!

감사합니다!

 

 

참고

씹어먹는 C++ - <10 - 2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map> (modoocode.com)