본문 바로가기

프로그래밍

[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로 바꾼 다음 정상적으로 동작하는지를 확인하면 될 거라고 생각했다. 이게 가장 쉽기도 하지만 구현 내용 자체가 많지 않고, 서브젝트상 추가로 구현해야 하는 내용이 없어서 가장 마음 편하게 접근할 수 있을 거라고 생각한다. 아래 기능을 지원하는 컨테이.. 더보기
[42서울] ft_containers[0] - 과제 정리 서론 과제를 시작하고 2주넘게 코드를 한줄도 못쓰고 나니까 뭘 만들어야하는지를 먼저 확실하게 정리하지못하면 계속 이 상태일거라는 생각이 들었다. 그래서 우선 과제의 내용을 적어서 정리해두고 그 다음에 어떤 순서로 만들어나갈지를 생각한 다음에 하나씩 구현해나갈 예정이다. 서브젝트 내용 이 과제에서는 C++의 STL 중 몇가지 컨테이너를 구현한다. 레퍼런스를 참조해서 구현해야하며, 그 안에 Orthodox Canonical form이 누락되어있으면 구현하지 않아야한다. C++98 표준을 준수해야하므로 이후 기능은 구현하지 않아야하며, 당시 기능은 deprecated 된것도 구현해야한다. container.hpp 안에 다음의 컨테이너를 구현하고 필요한 기능들을 넣어라 vector - vector 을 따로 구현.. 더보기
[42서울] CPP Module 08 - STL 서론 당연히 STL 없이도 구현할 수 있지만 그걸 사용하는 것이 과제의 목적이므로 가능한 한 많이 사용하려고 노력할 것. 템플릿을 헤더 파일에 정의해도 되고 tpp파일에 정의해도 됨. 모든 경우에 tpp는 옵션, hpp는 필수 파일임 표준 템플릿 라이브러리(STL)는 컨테이너, 이터레이터, 함수 객체, 알고리즘을 나타내는 템플릿들의 집합…. 컨테이너는, 배열과 같이, 여러 개의 값을 저장할 수 있는 구성단위… 알고리즘은 배열을 소트 하거나 리스트에서 특정 값을 검색하는 것과 같은 특별한 작업들을 사용하기 위해 상용하는 방법… 이터레이터는 배열 안에서 포인터를 사용하여 위치를 옮기듯이, 컨테이너 안에서 위치를 옮길 수 있도록 도와주는 객체들이다. 즉, 이터레이터는 포인터의 일반화이다. - [C++ 기초 플.. 더보기
[42서울] CPP Module 07 - 템플릿 서론 함수 템플릿과 클래스 템플릿을 구현해보는 과제이다. 템플릿에 대해 이해하기만 하면 구현은 별로 어려울 것이 없는 과제이다. https://modoocode.com/219 씹어먹는 C++ - modoocode.com https://www.hanbit.co.kr/store/books/look.php?p_code=E6410226806 Thinking About: C++ STL 프로그래밍 C++의 기초적인 내용은 알지만, STL에 대한 경험이 없는 사람이 기본적인 개념을 이해하고 기초적인 사용법을 아는 데 중점을 두고 설명했다. 함수 템플릿과 클래스 템플릿의 개념을 설명하고 이 www.hanbit.co.kr ex00 다음의 함수 템플릿을 만들어라 swap : 2개의 arg를 받아서 서로의 값을 바꾼다. 아.. 더보기
[42서울] CPP Module 06 - 형변환 서론 말그대로 C++의 방식대로 형변환을 해보는 과제이다 추가 룰로 각 ex마다 풀기 위해 특정한 하나의 형 변환을 사용해야 하는데 그 선택이 defense에 담겨있어야 한다. ex00 string을 일반적인 자료형으로 명시적으로 변환하여 출력하는 프로그램을 만들어라. 일반적인 자료형이란 char, int, float, double을 의미한다. char 예시 : ‘c’, ‘a’ … 출력할 수 없는 문자열이라면 출력하려 하지 말고 해당 정보를 알려주면 된다. int 예시 : 0 -42 42 … float 예시 : 0.0f, -4.2f, 4.2f … 추가로 -inff, +inff, nanf 도 받을 수 있어야 한다. double 예시 : 0.0, -4.2, 4.2 … 추가로 -inf, +inf, nan 도 .. 더보기

티스토리툴바