on
STL 컨테이너 클론코딩 해보기 (ft_containers)
STL 컨테이너 클론코딩 해보기 (ft_containers)
C++98 표준 기반으로 STL 컨테이너의 자료구조를 직접 만들어 본다.
규칙
템플릿을 제외하고 헤더파일에 함수를 구현하지 말것
헤더 보호 (#ifndef ~ #define ~ #endif)
허용되지 않은 함수 사용하지 말기
따로 언급하지 않으면 using namespace , friend 사용 금지 이 문제에서 friend 키워드는 non-member overloads에 대해서만 허용된다.
, 사용 금지 clang++으로 컴파일해야 하며 -Wall -Wextra -Werror -std=c++98 플래그로 컴파일이 되어야 함
플래그로 컴파일이 되어야 함 네임스페이스는 ft 로 지정해야 하며 테스트는 ft::(컨테이너명) 으로 할것이다.
로 지정해야 하며 테스트는 ft::(컨테이너명) 으로 할것이다. 제출하는 파일명은 (컨테이너명).hpp로 짓는다.
테스트에 사용할 main.cpp를 제공해야 한다. (문제에서 제공하는 테스트 코드 이외로 별도로 만들어야 함)
컨테이너에 대한 멤버 함수, 비멤버 함수, 오버로드를 구현해야 한다.
코플리언 폼이 적용되어야 한다.
할당자는 std::allocator 를 사용한다.
를 사용한다. 이 항목들은 재구현되어야 한다. iterator_traits reverse_iterator enable_if is_integral equal lexicographical_compare pair make_pair
컨테이너는 다음을 구현해야 한다 std::vector std::map std::stack
학습해야 하는 내용
C++의 네임스페이스
std::allocator
SFINAE과 부분 템플릿 특수화
반복자 std::iterator_traits
STL 컨테이너의 구조 vector map BST stack
C++의 네임스페이스
프로그래밍을 하다 보면 변수명이나 함수명이 겹치는 일이 많다. 원인 중 하나가 예를 들면 C에서 독자적으로 printf 라는 함수를 만든다고 생각해보자. 근데 이 printf라는 함수는 C 표준 라이브러리에 있는 printf와 이름이 겹친다. 내가 만든 printf 라는 함수를 라이브러리화 해서 여기저기서 가져다 쓰고 싶은데 표준 함수와 이름이 겹친다. 그래서 기존엔 함수명에 정체성을 나타내는 식으로 명명하는 식으로 하곤 한다. 예를 들면 my_printf 와 같은 식으로 짓거나 할 수 있다.
근데 내가 만든 printf라는 함수를 다른 프로젝트에서 쓰고자 할때 기존 프로젝트의 printf로 사용된 함수명을 my_printf로 뜯어 고치고는 해야 한다. 이런 작업은 매우 비효율적이다.
C++에는 네임스페이스라는 개념이 있다. 네임스페이스를 직역하면 "이름공간" 이고 뭔가 어색하지만 "고유한 함수나 변수 등을 가리킬 수 있는 공간"의 의미로 풀어볼 수 있다.
"네임스페이스" 라는 개념은 C++에 종속적인것도 아니고 컴퓨터 관련해서 광범위하게 사용되는 개념이다. C++의 네임스페이스는 함수나 변수, 클래스를 네임스페이스라는 공간에서 구분되는 것는 것을 의미한다.
예를 들어 C++의 표준 클래스나 객체에 접근할 때를 생각해 보자. 표준 클래스나 객체를 사용하기 위해 여러 헤더를 include 하기만 한다고 그 클래스나 객체들을 바로 사용할 수 없다. 표준 라이브러리는 std 라는 네임스페이스 내에 정의되어 있다.
그래서 표준 클래스나 객체를 사용하려면 범위 지정 연산자 :: 를 사용해서 std라는 네임스페이스에 속해 있는 것을 가져다 사용한다라고 명시해 주거나 using namespace std 키워드를 이용해 현재 코드에서 std 라이브러리 내부에 있는 것들을 전역적으로 사용할 수 있도록 해야 한다.
C++ 네임스페이스 사용법
네임스페이스 안에 넣고자 하는 클래스, 함수, 변수를 넣으면 된다. 네임스페이스를 별도로 지정하지 않으면 그 클래스, 함수, 변수는 전역 네임스페이스 소속이 된다.
#include namespace ns { // 네임스페이스 ns 지정 (정수 1개, 클래스 1개) int i; } namespace ns { class test { private: int val; public: test(int arg) : val(arg) {}; int getval(void) {return(val);} }; } int i; int main(void) { ::i = 10; // 전역 네임스페이스 ns::i = 20; // 네임스페이스 ns ns::test t(30); // 네임스페이스 ns std::cout << ::i << std::endl; std::cout << ns::i << std::endl; std::cout << t.getval() << std::endl; return (0); }
std::allocator
allocator 템플릿은 STL 내에서 메모리를 동적으로 할당하는 데 사용되는 템플릿이다.
STL에서 사용자가 원하는데로 메모리를 할당하고자 하면 다른 할당자 템플릿을 가져다 써도 되지만 기본으로는 이 템플릿이 사용된다.
new 키워드와 delete 키워드를 사용하지 않고 allocator 템플릿을 사용하는 이유는 new, delete 키워드를 사용해 메모리를 할당하면 상세한 컨트롤이 불가능하기 때문이다.
예를 들어 new 클래스() 와 같이 메모리를 동적으로 할당하면 메모리 할당 외에도 클래스 내 생성자 호출까지 하기 때문에 오버헤드가 생긴다.
템플릿에서는 메모리를 동적으로 할당만 해놓고 값은 추후에 대입하는 경우가 많다.
allocator 템플릿은 내에 들어있다.
멤버 변수
value_type T : 할당한 데이터 타입을 의미한다.
: 할당한 데이터 타입을 의미한다. pointer T* : 데이터 타입의 포인터형이다.
: 데이터 타입의 포인터형이다. const_pointer const T* : 데이터 타입의 상수 포인터형이다.
: 데이터 타입의 상수 포인터형이다. reference T& : 데이터 타입의 레퍼런스이다.
: 데이터 타입의 레퍼런스이다. const_reference const T& : 데이터 타입의 상수 레퍼런스이다.
: 데이터 타입의 상수 레퍼런스이다. size_type std::size_t : 할당할 데이터의 개수를 의미한다.
: 할당할 데이터의 개수를 의미한다. difference_type std::ptrdiff_t : 두 포인터 간 차이를 의미한다.
: 두 포인터 간 차이를 의미한다. rebind "template struct rebind"
멤버 함수
생성자
파괴자
address()
allocate() : 인수 n만큼의 메모리를 할당하고 첫번째 요소의 포인터를 반환한다. 성능 향상을 위해 인수 hint를 집어넣을 수 있다.
deallocate()
max_size() : 할당 가능한 최대 크기를 의미한다.
construct()
destroy()
예제
#include #include class Test { private: int data; public: Test(int data); ~Test(); }; Test::Test(int data) { std::cout << "생성자 호출됨" << std::endl; this->data = data; } Test::~Test() { std::cout << "파괴자 호출됨" << std::endl; } int main(void) { { // 정수형 할당자 선언 std::allocator alloc_int; // int형을 위한 공간(크기 : 2)을 힙에 별도로 할당 int* p = alloc_int.allocate(2); p[0] = 123; p[1] = 456; std::cout << "p[0] : " << p[0] << ", p[1] : " << p[1] << std::endl; // 파괴자 호출 alloc_int.deallocate(p, 2); } { // 임의의 클래스형의 할당자 선언 std::allocator alloc_test; // Test 인스턴스 힙에 할당 Test* test = alloc_test.allocate(1); // 할당 후 생성자 별도로 호출 alloc_test.construct(test, 1234); // 할당 해제 전 파괴자 별도로 호출 alloc_test.destroy(test); // 파괴자 호출 alloc_test.deallocate(test, 1); } return (0); }
SFINAE과 부분 템플릿 특수화
SFINAE
SFINAE는 C++ 표준에서 등장하는 개념이며 Substitution failure is not an error (대체 실패는 오류가 아니다)의 약자이다.
간단하게 설명하면 템플릿에 인자를 대입할 때 유효하지 않은 상황이라면 컴파일 에러가 발생하지 않을 수도 있다는 것이다.
예를 들면 동일한 이름을 가진 템플릿이 여러 개 있을 수 있는데 이 중 유효한 템플릿에 대해서만 적용되거나 더 명확한 템플릿에 대해서 적용되거나가 가능하다.
자세한 내용은 C++ 표준문서나 https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error 를 참조하자.
부분 템플릿 특수화
부분 템플릿 특수화는 템플릿 특수화 기법 중 하나이며 여러개의 동일한 이름의 템플릿이 있을 때 최적의 템플릿을 선택할 수 있도록 명시적으로 템플릿에 대해 특수화를 하는 것이다.
자세한 내용은 C++ 표준문서나 https://en.wikipedia.org/wiki/Partial_template_specialization 를 참조하자.
SFINAE과 템플릿 특수화를 확인하기 좋은 예가 std::enable_if이다. enable_if 템플릿은 다음과 같이 정의되어 있다.
template struct enable_if {}; template struct enable_if { typedef T type; };
위 두가지 템플릿에서 첫번째 템플릿 인자는 bool 타입이 올 수 있으므로 true나 false가 올 수 있다.
만약 첫번째 템플릿에 false가 온다면 enable_if라는 내부에 아무것도 없는 클래스를 의미한다. 하지만 두번째 템플릿에서 첫번째 인자에 true가 온 경우 enable_if 클래스는 내부에 타입 T인 type을 가진다.
예를 들면
std::enable_if::type i = 10; // i는 int형 변수가 된다. std::enable_if::type i = 10; // enable_if 내에 type가 존재하지 않으므로 컴파일이 실패한다.
이런 식으로 사용할 수 있다.
반복자
반복자란 객체지향 프로그래밍에서 사용하는 디자인 패턴 중 하나이다. 여러 종류의 데이터 컬렉션에서 동일한 인터페이스로 데이터에 접근하기 위해 고안된 패턴으로 배열이나 트리, 링크드 리스트 등에 반복자가 구현되어 있다면 내부 구현은 전혀 다르지만 반복자를 이용해 데이터에 접근할 수 있다.
std::iterator_traits
C++ 표준헤더 내에 구현된 템플릿 클래스이다. trait은 특성이란 의미이며 C++에서 지원하는 반복자 타입을 받아 반복자가 가지고 있는 특성(반복자가 어느 카테고리에 속하는지, 값 타입은 무엇인지 등)을 가져올 때 사용한다.
포인터와 상수 포인터는 반복자 특성을 가지므로 iterator_traits 템플릿 클래스는 포인터에 대해 템플릿 특수화가 되어있다.
iterator_traits 템플릿 클래스를 사용하면 이터레이터를 받아서 무엇인가를 하는 함수나 클래스를 디자인할 때 서로 다른 반복자마자 특성화를 할 필요 없이 동일한 하나의 코드로 사용할 수 있다.
STL 컨테이너의 구조
STL 컨테이너의 내부 구조는 STL 라이브러리를 만든곳마다 조금씩 다르지만 기본적인 시놉시스는 동일하므로 적당히 찾아보면 된다.
vector
벡터 컨테이너는 내부적으로 배열을 사용하는 것으로 구현되어 있다. 그래서 벡터와 벡터의 이터레이터는 배열 형태로 데이터를 할당하고 접근하고 추가하는 방식을 연상해 구현하면 된다.
map
맵은 STL에선 트리 구조로 데이터들을 관리한다. 맵은 키-값 구조로 이루어져 있는데 키에 대한 값을 빠르게 찾는 이점 (균형잡힌 이진트리의 경우 탐색의 시간복잡도가 ln(N) 이다.) 등이 있으므로 균형잡힌 BST를 사용한다.
균형잡힌 BST엔 AVL Tree와 RB Tree가 있는데 구현 방식은 AVL Tree가 더 단순하다. 하지만 대부분의 STL 라이브러리는 내부적으로 RB Tree를 사용한다. 하지만 데이터 탐색 속도는 동일하므로 본인의 판단에 맞게 채택한다.
맵의 이터레이터는 트리의 특정 노드에서 이전 노드나 다음 노드로 순회할 수 있어야 하므로 이를 고려하여 이터레이터 및 트리를 설계한다. (트리의 간선을 이중 연결 구조를 가지게 설계한다던지)
stack
스택은 덱 (std::deque)을 내부에서 인스턴스화 한 다음 덱의 멤버함수를 호출하는 식으로 동작되므로 구현이 매우 간단하다. 덱뿐만이 아니라 벡터로도 구현이 가능하다.
from http://profq.tistory.com/61 by ccl(A) rewrite - 2021-12-14 22:01:49