Computing

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..

이전 글 [STL] [1] 순차 컨테이너 정리 (Sequence Container, std::array, std::vector, std::list, std::deque) [STL] [2] 연관 컨테이너 정리 (Associative Container, std::set, std::map) 이전 글에서 STL container 개념과 Sequence container, Associative container에 대해서 정리하였다. 오늘은 앞서 소개한 STL container들을 이용하여 개발된 Container adapter에 대해서 정리하고자 한다. Container Adapter Container adapter는 기존 컨테이너를 변경(modify, adapt)하여 특정 인터페이스(기능)만을 제공하도록 만든 ..

이전 글 [STL] [1] 순차 컨테이너 정리 (Sequence Container, std::array, std::vector, std::list, std::deque) 이전 글에서 STL container 개념과 그 중 하나인 Sequence Container에 대해서 정리하였다. 오늘은 STL container 중 Associative container (연관 컨테이너)에 대해서 정리하고자 한다. Associative Container Associative Container (연관 컨테이너는)는 컨테이너 내 저장된 데이터를 key 기반으로 빠르게 접근할 수 있는 컨테이너를 의미하며, 컨테이너 내 저장된 데이터는 정렬되어 있다[1]. An AssociativeContainer is an ordered ..

STL과 Sequence Container C++ Standard Template Library (표준 템플릿 라이브러리, STL)은 미리 구현된 임의 타입(Template) 자료구조와 알고리즘을 제공하는 라이브러리이다. 오랜 역사를 거쳐 최적화되었기에 성능과 정확성이 보장된다고 하는데, 따라서 C++ 개발 시 필수로 사용되는 라이브러리이다. (개인이 직접 작성한 알고리즘과 자료구조보다 거의 무조건 더 낫다고 생각하고 꼭 쓰자) STL은 알고리즘, 컨테이너, 함수자, 반복자라는 크게 4가지 구성 요소를 제공한다[1]. STL 컨테이너는 데이터를 저장하는 객체(정확히는 class template)를 의미한다. 좀더 쉽게 표현하면 STL 컨테이너는 데이터를 효과적으로 저장하기 위한 다양한 자료구조 구현체를 ..