Ft_container
- container ( vector / stack / map / set)
- iterator (random_access / reverse / bidirectional)
- allocator
컨테이너를 시작하기전 iterator, vector, allocator etc...
1. 컨테이너
모두의 코드에서 STL(Standard Template Library) 컨테이너를 찾아보면 컨테이너(Container)는 다른 객체들을 보관하는 하나의 커다란 보관소 라고 정의하고있다.
여태까지 c 언어 프로젝트를 수행하면서 훑어 보았던 linked list 또는 array형태의 자료구조(?)가 클래스 템플릿의 형태로 구현되어있기 때문에 관리하고자 하는 방법에따라 데이터를 효율적으로 저장 및 관리할수있다.
대용량 자료를 빠르게 읽어야 하는 상황에서는 단순 배열 자료구조가 효율이 좋지만, 지속적으로 새로운 자료들을 기존에 있는 자료 사이사이에 삽입하거나 삭제하는 일이 필요한 경우에는 연결리스트가 배열보다 유리하다.
예를 들어 cpp00의 전화번호부를 만들때, 저장되는 순서대로 index 가 늘어나는 단순 구조는 배열이 효율적이다. 하지만 이 전화번호부가 알파벳순으로 정렬되어져야 한다면 저장할때마다 메모리 동적할당이 이루어지거나, 정렬알고리즘이 필요한 배열구조 보다는 원하는 위치에 바로 삽입과 삭제가 가능한 연결리스트 구조가 훨씬 더 프로그램을 만들기에 편리할 것이다.
한번 만든 자료구조를 수정없이 사용하기위해 만들어진 프로그래밍 방법중 하나가 객체지향 프로그래밍(OOP) 방법인데 각각의 부품들을 만들어두고 이 부품들을 필요에 따라서 조립하여 하나의 물건(객체)를 만들어내는 방법이다.
Stl 에서는 이보다 조금 더 발전된 개념의 재사용성을 제공하는데, cpp-module 후반부에서 보았던 Generic(일반화) 프로그래밍이라는 방식이다. Generic Programming은 두가지 측면에서 일반성을 제공하는데
-
임의 타입에 사용할 수 있는 자료 구조를 만들 수 있다. Int, char, double뿐 아니라 사용자 정의 자료형에 대해서도 c++ 템플릿 문법을 사용하여 다양한 자료형에 대응할수있다.
-
자료 구조(배열, 리스트 등등)에 상관없이 사용할 수 있는 일반화된 알고리즘 함수들을 제공한다. 이는 반복자(iterator)를 이용해 사용할 수 있다.
이런 일반화의 개넘에 의해 만들어진 커다란 보관소가 STL이다. 앞으로 우리는 여태까지의 과제처럼 한땀 한땀 자료구조를 만들어서 사용하는 것이 아니라.
문명인답게 이미 만들어진 자료구조와 알고리즘을 필요에따라 사용할 수 있다.
(물론 이 과제 이후 부터 가능하다.)
1.1 컨테이너의 종류
과제에서는 기본적으로 vector, stack, map 세가지 종류의 컨테이너를 구현하라고 요구하는데, 이 세가지의 컨테이너는 각각 다른 종류로 분류 되어있다.
-
Sequence Container : vector 그리고 list deque가 STL에 구현되어있는데 삽입된 요소가 순서대로 유지되어지는 기본적인 선형구조 컨테이너이다.
-
Assosiative Container : map set 등이 구현되어있고 Sequence 컨테이너와는 다르게 자료를 단순히 저장만 하는것이 아니라, 일정한 기준에 따라 자료를 정렬하여 저장하는 방법으로 검색속도가 빠른것이 장점이다.
-
Adapter Container : 어댑터란 이미 구현된 기능은 그대로 활용하고, 인터페이스만 바꿔서 변형시킨것인데 stack과 queue가 여기에 속하고 추가로 이후에 보게될 reverse_iterator나 binary_function이 어댑터라고 불려진다.
vector, map, stack, iterator 등등 생소한 단어들이 나와서 혼란스럽겠지만,
단순하게 생각하면 컨테이너는 여태까지 우리가 사용해왔던 배열구조, 리스트구조를
좀 더 이용하기 편하게 구현해 둔것이라 생각하고, iterator는 뒤에서 보겠지만 배열과 리스트에서 자료를 읽어내기위해 선언했던, 포인터 i 라 생각하면 마음이 편하다.
int i = 0; // i는 iterator
while ( i< end_of_array)
array[i++] // array는 container이렇게 보면 Stl 은 여태까지 과제에서 만들어서 사용했던 방법과 크게 다를것이 없다(?).
단순히 이것이 내가 아닌 똑똑한 사람에 의해 정교하게 만들어진, 그리고 생소한 cpp언어로 구현되어 있기 때문에 어려워 보이는것일 뿐이다.
2. 반복자
! 반복자 이해를 쉽게 시작하기 위해 포인터라고 예를 들었을 뿐
실제로 반복자 == 포인터 는 아니다!
Ft_container subject를 읽고난뒤에 cplusplus.com에 iterator를 검색해보면 다양한 종류의 iterator_tag 를 볼 수 있다. input, output, forward etc...
처음 보는 단어들이 생소해 멘붕이 올 수도 있다.
겁먹지말고 단순하게 생각 해보자.
우리가 c언어 배열에서 각각에 index 에 자료를 저장하고 그 자료에 접근하기 위해 사용한 int i 는 " i++ // i-- array[i] " 등등의 방법으로 배열 index에 접근하여 자료를 불러올 수 있다.
그렇다면 list 에서는 자료에 접근 할 때는 어떤 방법을 썻는가? i 를 사용할 수 있을까? " i++//i-- " 는 사용이 가능하지만 ( ->next // ->prev ) list[i] 는 불가능 하다는 것을 우리는 이미 인지하고있다. (물론 짜는 방식에 따라서 list[i]도 가능하지만 일반적으로...) list 자료에 접근하기 위해서는 첫번째 노드부터
while (list->next != NULL)
list = list->next;로 또는 minishell을 트리 구조로 구성했다면 node left/right를 이용해서 자료에 접근하는 방법을 사용했을 것이다.
자료에 접근하기 위해 사용한 두가지 방법에 대해 생각해보자.
왜 배열에서는 int i 를 선언해서 자료에 접근했고,
list 에서는 list ->next, list->prev를 이용하여 자료에 접근했는가?
STL 컨테이너에서 각각의 자료구조는 자료를 효율적으로 정리하기 위해 크게는 선형//비선형 구조로 구성되어져있다. 만약 우리가 하나의 형태의 반복자로 각각의 자료구조(vector, map, set, stack, list)에 공통적으로 접근하려 한다면 어떠한 컨테이너에서는 지원하지 기능이 생길 수도 있다 ex) list 에서 [i]. 그렇기에 반복자는 컨테이너에 따라 알맞게 만들어져있는 것이고 이러한 기능들을 크게 크게 나누어둔 것이 iterator_tag이다.
정말 단순하게 설명한 것이고 구글링을 해보면 나오겠지만, 연산자기능 등등도 지원한다.
다시 배열과 list로 돌아가 반복자(포인터i )의 관계에 대해 생각해보자, 배열에서 사용한 i는 ++/-- 뿐만아니라 [i]의 기능도 추가로 사용이 가능하다. 하지만 리스트에서의 i는 next// prev의 ++// --의 기능은 제공하지만 [i]의 기능은 제공하지 않는다.
포인터에 c++의 상속관계를 여기에 적용해보면 배열[i]는 list[i]를 상속받았다 라고 말할 수 있다. 부모 포인터 list[i]가 제공하는 ++/--의 기능을 상속받고 추가로 자식 포인터 배열[i]가 array[i]기능의 메소드를 추가 한 것이다.
포인터가 제공하는 기능,
주소에 접근하여 자료를 입력하는 input : *i = 10;
주소에 접근하여 자료를 출력하는 output : std::cout << *i << std::endl;
다음 주소에 접근하는 기능 forward : i++;
이전 주소에도 접근가능 하는 기능 bidirectional : i--, i++;
index 에 직접 접근이 가능한 기능 random_access : array[i];
자료에 접근하는 방법을 기준으로 하여 상속관계 (직접 상속 관계는 아니다) 를 갖고 있는 것이 바로 iterator_tag 종류의 정체이다.
추가로 STL iterator 에서는 iterator 끼리 연산이 가능한 i == j // i != j // cont i == j 등등의 연산자 기능도 포함하고 있다.
여기에 앞에서 공부했던 Generic Programming 을 한 스푼 추가하면
여러가지 자료형에 사용이 가능한 포인터인데, 내가 원하는 자료구조에 알맞게 만들어졌고, 포인터끼리 <=, >, == 등등의 연산자 기능도 수행 할 수 있는 아주 편리한 녀석을 STL Iterator라고 한다.
또한 STL의 알고리즘 함수들은 iterator 만을 받아서 동작하고 그 iterator 가 사용되는 컨테이너(자료구조)는 신경쓰지 않는다. vscode에서 알고리즘 헤더를 하나씩 뜯어보면 iterator 만 받아서 작동하는것을 볼 수 있다.
