Computing

이전 글[STL] Set, Map Custom Sort 구현 방법 (Red-black tree) 이전 글에서 Set을 이용한 Custom Sort 구현 방법에 대해서 소개하였다. 윗 포스터와 같이 std::set은 Balanced Binary Tree (i.e. Red-Black Tree)를 기반으로 구현[1]되었기에 내부적으로 데이터들을 정렬하여 저장한다. 따라서 std::set을 정렬을 위한 용도로 사용할 수 있다.   std::set의 또다른 기능 : Duplicate 테스트 및 중복 제거std::set은 정렬 용도 말고도 중복된 요소 제거를 위해 사용될 수 있다. 이는 Set 자료구조의 기본 특성인, std::set 내 저장된 데이터는 고유의 Key 값을 가져야 한다는 특성[2] 덕분이다. 즉 s..

Red-Black Tree를 통해 구조화된 자료구조: std::set, std::map 이전 글에서 std::set과 std::map은 Associative Container 중 하나들로, Key 기반으로 데이터(value)에 빠르게 접근할 수 있도록 쌍이 저장된다고 정리하였다. 이때 std::set은 key 자체를 데이터(value)로 보아 key 접근만을 빠르게 하도록 구현된다. std::set과 std::map은 컨테이너 내 데이터 관련 연산(데이터 추가, 읽기, 삭제, 존재 여부 등)을 O(log(N))의 time complexity로 수행가능하도록 구현되었다. 이러한 Key 기반 빠른 탐색이 가능하도록 하기 위해 std::set과 std::map은 self-balancing binary sear..