STL (Standard Templete Library) - (1)

--------------------------------------------------------------------------------
STL (Standard Templete Library)

part-1

Yonghan, Yoon
yonghany@orgio.net
--------------------------------------------------------------------------------
                               THE WAITE GROUP"s
                       Object-Oriented Programming in C++
                                Third Edition
                             Robert Lafore(Author)
                               SAMS(Publisher)
란 책에서 STL부분만 번역한 겁니다.
--------------------------------------------------------------------------------


0. 개요
STL에서 중요한 세가지 엔티티는 containers, algorithms, iteraters이다.

containers:
메모리에 구조화된 데이터가 저장되는 방법을 말한다. template class로
구현되어 있기 때문에 다른 타입의 데이터를 저장할 수 있게 쉽게 커스터마이징 할 수
있다.

algorithms:
  -containers가 가진 데이터를 다양한 방법으로 처리하는 프로시져다.
    (예, sort, copy, search, merge)
  - template class로 구현됨(하지만 container의멤버는 아님)

iterators:
  - 포인터 개념을 일반화 시킨것.
  - 콘테이너의 데이터를 가리킨다.
  - 포인터를 증가시키듯이 iterator를 증가시킬 수 있다. 따라서 iterator는
    콘테이너의 다음 데이터를 가리키게 된다.
  - iterator는 콘테이너를 가지고 알고리즘을 연결하기 때문에 STL에서 핵심 부분이
다.



1.콘테이너
콘테이너는 클래스 오브젝트나 int, float같은 built-in 데이터들을 저장하는 방법을
말한다. STL은 7가지 basic type이 사용가능할 뿐만 아니라, basic type에서 상속된
3가지 타입이 더 있다. 그리고 basic type에서 상속 받는 자신만의 콘테이너를 만들
수도 있다.
모든 데이터를 저장할때 왜 C++ 배열을 사용하지 않는 거쥐? 이쯤에서 왜 그렇게 많은
콘테이너가 필요한지 궁금할 것이다.
배열은 다루기 힘들고 어떤 상황에선 느리다.

STL에서 콘테이너는 sequence, associative의 2가지 메인 카테고리로 요약된다.
sequence 콘테이너는 vector, list, deque로 분류되고
associative 콘테이너는 set, multiset, map, multimap으로 분류된다.
여기에 추가로 sequence 콘테이너를 상속받은 몇개의 특수한 콘테이너들이 있다.
(stack, queue, priority_queue)

그럼 다음에 차례로 이 카테고리들에 대해서 살펴보기로 하자.


1.1 sequence containers
sequence 콘테이너는 거리에 늘어선 집들처럼 line으로 시각화 할수 있는 요소들의
집합을 저장한다. 각 요소들은 선을 따라서 다른 요소들과 연결되어 있다.
끝요소를 제외한 각 요소들은 어떤 요소들의 앞에 있을 수 있고 뒤에 있을 수도 있다.
일반적인 C++ 배열이 sequence 콘테이너의 예라 할 수 있다.
C++ 배열의 한가지 문제점은 compile-time에 반드시 크기를 결정해야 한다는 것이다.
그러나 일반적으로 배열에 얼마나 많은 데이터가 저장될지는 알 수 없는 일이다.
그래서 데이터의 최대갯수를 추측하여 충분히 크게 설정하게 된다. 결과적으로
프로그램이 실행되었을 때 사용되지 않는 배열 공간이 낭비되고 또는 실행 공간 부족
에러를 도출해 낸다(심지어는 프로그램이 멈춰버리기 까지 한다). vector 콘테이너는
이러한 복잡성을 피할 수 있는 길을 제공한다.
배열의 또다른 문제점은 employee 레코드를 저장하고 이를 employee이 이름으로 정렬
하라고 한다면 이름이 L로 시작하는 employee를 삽입하려 할때 M부터 Z까지 모든
employee 레코드를 이동시켜야만 한다. 이 작업은 많은 시간이 소요될 것이다.
STL은 이 문제를 풀기 위해 링크드 리스트 개념에 기초한 list 콘테이너를 제공한다.
세번째 sequence container는 stack과 queue를 조합한 것이라 생각할 수 있는 deque
이다.
stack은 last-in-first-out 개념이고, queue는 first-in-first-out개념이다.
따라서 dequeu는 양끝에서 데이터를 추가 삭제를 할 수 있다. deque라는 단어는
Double-Ended-QUEeue를 조합한 것이다. 융통성 있는 메카니즘으로써 deque자체로도
유용할뿐만 아니라 stack과 queue로도 사용할 수 있다.

테이블 1.1 Basic sequence Container
================================================================================
                     특징                     장단점
================================================================================
일반 C++ 배열        고정크기                 인덱스 번호를 통한 빠른 액세스
                                              중간값의 추가 삭제 느림.
                                              run-time시에 크기를 변경할 수 없
다.
--------------------------------------------------------------------------------
vector               재배치,확장배열          인덱스 번호를 통한 빠른 액세스
                                              중간값 추가 삭제 느림
                                              끝에 값 추가 삭제는 빠름.
--------------------------------------------------------------------------------
list                 Doubly linked list       어떤 위치에서건 추가 삭제 빠름.
                                              양끝에서부터 액세스 빠름.
                                              임의 접근 느림
--------------------------------------------------------------------------------
deque                vector와 유사,           빠른 임의접근(인덱스번호 이용)
                     그러나 양끝에서          중간값 추가삭제 느림
                     액세스 가능              양끝에서 빠른 추가삭제(push & pop)
================================================================================

STL을 생성하기는 쉽지만 반드시 헤더를 include해야 한다.
예)
vector< <FONT COLOR=#0000FF>int> aVect; // ints 벡터 생성
또는
list< airtime> depature_list; // airtime 리스트 생성

예제에서 주목할 것은 STL 콘테이너의 크기를 지정하지 않는 다는 것이다. 콘테이너는
스스로 메모리를 할당하게 된다.

to be continued...