나의 기술부채 청산일지

본문 바로가기

최신글

[42서울] ft_containers[4] - 맵 구현 서론 key-value의 형태의 pair를 정렬된 순서로 저장하는 컨테이너. 각 key는 전부 고유한 값을 가지며, 검색과 삽입 삭제가 전부 O(log n)으로 효율적이다. 내부의 자료구조가 tree(주로 rbtree)로 구현되어있다. 서브젝트에서 얘기하듯이 배열 같은 ‘적합하지 않은’ 자료구조로 구현해서는 안되며, 20배 이상 차이가 나면 안 된다고 되어있기 때문에 BST 같은 지나치게 단순한 tree를 선택해도 안되고 자체적으로 밸런싱 기능이 있는 tree를 자료구조로 사용해야 한다. 맵의 항목들을 보면서 필요한 함수들을 트리에 구현하면 조금 더 편하다. 들어가야 하는 구성요소 Member types key_type: 맵의 키(Key) 유형 mapped_type: 맵의 값(Value) 유형 value.. 더보기
[42서울] ft_containers[3] - 트리 구현 서론 원래 rbtree를 이용해서 구현하고 싶었는데, 제대로 이해하지 못한 상태로 대충 구현하고 나서 테스트를 해보니 map의 테스트에서 일부분 문제가 생겼다.(어느 부분인지는 map에서 설명) 내가 그걸 못고치는걸 보면서 이건 내가 이해한게 아니라고 생각해서 다른 bst를 찾아봤는데, splay tree라고 하는 간단하게 밸런싱을 하는 트리를 발견해서 그걸로 구현했더니 역시 문제가 생겼다. splay tree는 선형 체인에서 O(n)이어서 30만 개 선형 체인 테스트를 std::map보다 20배 이상 느려져서 통과하지 못했다. 그래서 그냥 힙스터 기질은 접고 다른 사람들처럼 avl tree로 구현하게 되었다. https://www.cs.usfca.edu/~galles/visualization/AVLtr.. 더보기
[42서울] ft_containers[2] - 벡터 구현 서론 https://jhnyang.tistory.com/230 [자료구조STL vector 1탄]벡터란? 배열 vs 벡터 비교/장단점/ 특징, 다양한 백터 선언 및 초기화 방법, 안녕하세요 오늘은 C++ 자료구조 컨테이너 중 하나인 vector 라이브러리에 대해 살펴봅시다. [1탄 목차] 1. 벡터란 무엇인가? 2. 벡터의 구조와 특징 (장단점) 3. 언제 벡터를 사용하는가 4. 벡터를 사 jhnyang.tistory.com 동적 배열구조 클래스. 배열이지만 크기를 자유자재로 수정할 수 있는 배열이라고 생각하면 된다. 동적으로 메모리를 늘려주기 때문에 편해서 배열보다 더 자주 쓰인다. 각각의 원소를 [] 연산자를 통해 쉽게 접근할수있고, 임의의 순서로 메모리에 접근가능하다. 단점은 중간에 많은 데이터를 .. 더보기
[42서울] ft_containers[1] - 스택 구현 서론 스택이란 LIFO(last-in first-out 후입선출)로 동작하는 자료구조로, cpp module에서(그리고 조금 다르지만 푸시스왑에서) 이미 가볍게 다뤄봤듯이 컨테이너의 한쪽 끝에서만 입력하고 출력하는 자료구조이다. 다른 컨테이너를 가져와서 그 컨테이너 위에서 동작하도록(캡슐화) 되어 있는데, 이 과제에서는 내가 만든 벡터를 이용하여 구현해야 한다. 하지만 우선 std::vector를 사용하여 구현을 먼저 하고 나중에 내가 만든 ft::vector로 바꾼 다음 정상적으로 동작하는지를 확인하면 될 거라고 생각했다. 이게 가장 쉽기도 하지만 구현 내용 자체가 많지 않고, 서브젝트상 추가로 구현해야 하는 내용이 없어서 가장 마음 편하게 접근할 수 있을 거라고 생각한다. 아래 기능을 지원하는 컨테이.. 더보기

인기글

티스토리툴바