[42서울] ft_containers[0] - 과제 정리

서론

과제를 시작하고 2주넘게 코드를 한줄도 못쓰고 나니까 뭘 만들어야하는지를 먼저 확실하게 정리하지못하면 계속 이 상태일거라는 생각이 들었다. 그래서 우선 과제의 내용을 적어서 정리해두고 그 다음에 어떤 순서로 만들어나갈지를 생각한 다음에 하나씩 구현해나갈 예정이다.

 

서브젝트 내용

이 과제에서는 C++의 STL 중 몇가지 컨테이너를 구현한다. 레퍼런스를 참조해서 구현해야하며, 그 안에 Orthodox Canonical form이 누락되어있으면 구현하지 않아야한다.

 

C++98 표준을 준수해야하므로 이후 기능은 구현하지 않아야하며, 당시 기능은 deprecated 된것도 구현해야한다.

 

container.hpp 안에 다음의 컨테이너를 구현하고 필요한 기능들을 넣어라

 

vector - vector<bool> 을 따로 구현할 필요는 없다

map

stack - 내 벡터 클래스를 기본 컨테이너로 사용하되 STL의 다른 컨테이너와도 여전히 호환이 되어야한다.

 

다음의 내용도 구현하라

• iterators_traits
• reverse_iterator
• enable_if 이건 C++11이지만 98에서도 구현할 방법이 없는건 아니다. 이걸 보면서 SFINAE를 발견할수있다.
• is_integral
• equal and/or lexicographical_compare
• std::pair
• std::make_pair

namespace는 ft여야만 한다.

 

컨테이너에서 사용되는 자료구조는 정당해야한다(즉, map에 단순 배열을 사용하는것은 허용되지 않는다)

 

표준 컨테이너에서 제공되는 public 함수보다 더 많은걸 구현해서는 안된다. 다른걸 넣으려면 private 혹은 protected로 구현해야 한다.

 

당연히 모든 public 함수는 정당해야한다.

 

표준 컨테이너의 모든 멤버 함수, 비멤버 함수와 오버로딩을 만들어야 한다.

 

원래 이름을 철저히 따라야 한다. 디테일에 신경쓸 것.

 

컨테이너가 iterator 를 가지고 있다면 구현해야 한다.

 

std::allocator 를 사용해야한다.

 

비멤버 오버로딩에서는 friend 키워드가 허용된다. 당연히 모든 friend의 사용은 정당해야한다. 평가중 확인 할것임.

 

당연한 얘기지만, map::value_compare 를 구현할때에는 friend를 사용할수있다..

 

https://www.cplusplus.com/ 와 https://cppreference.com/ 를 레퍼런스로 사용할수있다.

 

과제에서 제공되는 main.cpp를 사용해서 테스트를 하되, 평가에서는 이것보다 더 많은 것을 보여줘야 한다.

 

내 컨테이너와 STL 컨테이너를 비교해서 실행하고 실행 속도를 확인해야한다(20배 보다만 덜 차이나면 됨)

 

ft::container 로 내 컨테이너를 테스트해볼수있다.

 

• 보너스

셋(set)을 구현해라. 단, 이번에는 반드시 레드-블랙 트리로 구현해야한다.

 

 

생각한 구현 방법

해당 과제를 여러차례 평가를 하면서 들은 생각은 굳이 벡터를 먼저 구현할 필요가 없을것 같았다. cpp 05 / ex02 때 처럼, 가장 쉬운게 가장 나중에 적혀있으니, 쉬운걸 먼저 구현한 다음 감을 잡고 나머지를 마저 구현하는게 더 쉽게 시작할수있는 방법인것 같다.

 

그래서 가장 먼저 스택을 구현할 것이다. 서브젝트에서는 내가 만든 벡터를 이용해서 구현하라고 했는데, 어짜피 std의 다른 컨테이너에서도 동일하게 동작해야한다고 했으니, std의 벡터를 이용해서 구현한 다음 나중에 내가 만든 벡터를 넣어서 테스트를 하면 될것같았다.

 

스택 다음에는 벡터를 구현하고, 테스터기를 사용하여 내 벡터와 스택에서 생기는 문제들을 해결한다.

 

그 다음에는 레드-블랙 트리를 구현한다. 보너스를 안할 생각이었으면 조금 더 사용하기 쉬운 트리를 만들어서 맵에 넣고 끝낼 생각이었는데, 컴파일러들의 STL을 열어보니 레드-블랙 트리로 구현되어있고, 그걸 보고 이해한다면 셋도 어렵지않게 구현할수있을것 같았다.

 

레드-블랙 트리를 다른 컨테이너에서 사용할수있게 구현한 다음, 그걸 사용해서 맵과 셋을 각각 구현하고, 구현 한 다음 바로 테스터기를 사용해서 문제점들을 해결한다.

 

스택, 벡터, 레드-블랙 트리, 맵, 셋 순서대로 만들고 만들자마자 바로 블로그에 글을 남길 생각이다. 평가를 가서 보니 구현해야하는 내용이 워낙 많아서 어짜피 글 하나에서 전부 정리할수는 없을것 같고, 구현을 마무리 하자마자 바로 글을 남겨야 이전 몇몇 과제들처럼 나중에 '뭐가 문제였더라...' 하면서 적을건 많은데 글에 적은건 별로없는 불상사를 피할수있겠다는 생각이 들었다.

 

참고 자료

과제를 하면서 계속 추가할 예정

 

https://en.cppreference.com/w/

cppreference.com

https://cplusplus.com/

https://cplusplus.com/

https://www.hanbit.co.kr/store/books/look.php?p_code=E6410226806

Thinking About: C++ STL 프로그래밍

https://github.com/microsoft/STL

GitHub - microsoft/STL: MSVC's implementation of the C++ Standard Library.

https://github.com/llvm/llvm-project/blob/main/libcxx/include

GitHub - llvm/llvm-project: The LLVM Project is a collection of modular and reusable compiler and toolchain technologies. Note:

https://web.archive.org/web/20160731195009/http://www.stepanovpapers.com/butler.hpl.hp/stl/stl

Index of /butler.hpl.hp/stl/stl

http://stepanovpapers.com/butler.hpl.hp/stl/stl/

Directory Tree

 

 

https://wikidocs.net/419 - type in class

https://modoocode.com/253 - explicit