본문 바로가기

STL3

C++ STL List에서 Sorting Intro list container에서 sort는 어떻게 할까? 다행히도? list container안에는 sort라는 함수가 내장되어 있다. default는 ascending sort이다. 이번 posting에서는 정수, 문자열, struct 같은 데이터 타입의 sort를 알아보고자 한다. integer sort sort 함수를 사용하면 된다. 그렇다면, default인 ascending sort 말고 descending sort는 어떻게 할 수 있을까? 먼저, sort 함수가 어떻게 정의되어 있는지를 보는 게 좋다. (C++ template에 익숙하지 않아서, 정확히 이해하지는 못했다.) 정의된 template을 보면, sort함수의 파라미터가 클래스구나. // list.sort()를 하면, def.. 2023. 2. 4.
C++ STL sequence container(vector, deque, list) intro 자료를 linear 하게 보관하고자 할 때, array나 linked list를 사용한다. 직접 구현해도 되지만, C++ STL에서는 이를 제공하고 있다. 이를 sequence container라고 한다. 이번 포스팅에서는 sequence container에는 무엇이 있고, 각 container의 함수의 시간복잡도를 알고자 한다. vector vector container는 동적 배열로, 메모리가 연속적으로 할당된다. 주의할 것은, vector의 back 이외에 insert 하거나 delete 하는 경우, O(n)의 시간복잡도가 소요된다. 위와 같은 경우는, list container가 효율적이다. (list는 어느 위치에 insert나 delete를 하던 상수시간이 소요된다.) 시간복잡도 i.. 2023. 1. 29.
C++ STL ordered associative container(set, map) intro associative란, "연관 있는" 이런 의미이다. 그렇다면, ordered하고 associative 한 객체들은 어떻게 관리할 수 있을까? 이는 linear한 구조보다는 binary tree 구조로 관리하는 게, 삽입, 삭제, 검색의 시간복잡도면에서 유리하다. binary tree는 linear한 구조와 어떻게 다르길래? binary tree binary tree는 최대 2개 이하의 자식 노드를 가지는 tree를 말한다. parent node와 child node 간의 연관관계를 가지고 tree를 구성하면, 삽입, 삭제, 검색을 logN의 시간복잡도로 해결할 수 있다. (N은 node의 개수를 의미한다) 그러나, binary tree가 항상 위의 그림과 같이, 좌-우 balance가 맞는.. 2023. 1. 28.

티스토리툴바