37-2.STL의 구조

일반화 프로그래밍이라는 개념과 STL의 구조는 지금껏 경험해 보지 못한 아주 새로운 이론이다. 이런 생소한 과목을 배울 때는 아무래도 쉬운 순서대로 하나씩 느긋한 자세로 구경하면서 구성 요소를 점진적으로 익히는 것이 효율적이다. 그러나 STL은 이런 방법으로 학습하기는 상당히 어려운 과목인데 왜냐하면 아무리 간단한 예제라도 모든 요소들이 동시에 필요하기 때문이다. 그래서 STL은 처음 배울 때가 조금 어렵다고 하는데 시작만 조금 힘겨울 뿐 개념이 잡히면 레퍼런스만으로도 충분히 활용할 수 있다.

단계적인 학습이 어려우므로 이 장에서는 STL의 구조에 대한 개요를 먼저 소개하는데 주력하기로 한다. 따라서 여러분들도 한꺼번에 STL의 모든 것을 다 알겠다는 맹렬한 자세로 덤비기 보다는 구경해 본다는 가벼운 마음으로 임해 주기 바라며 혹시 좀 어려워진다는 느낌이 들어도 뒤에서 다시 상세하게 설명하므로 일단은 이해된 데까지만 접수하고 세부적인 내용은 잠시 보류해 놓도록 하자. 대충의 큰 구조가 잡히면 그 다음에는 하나씩 완벽하게 각개 격파하면 된다. STL은 다음 여섯 가지의 주요 구성 요소로 이루어져 있다.

컨테이너, 알고리즘, 반복자가 가장 중요한 세 요소이며 STL 학습의 대부분이 이 세 요소에 치중된다. 네 번째 요소인 함수 객체는 알고리즘의 활용성을 높이는 역할을 하며 다섯 번째 요소인 어댑터는 다른 요소들을 약간만 수정하여 형태를 변형한다. 마지막 구성 요소인 할당기는 컨테이너의 메모리를 관리하는 객체인데 디폴트가 잘 작성되어 있으므로 거의 신경쓸 필요가 없다.

37-2-가.컨테이너

컨테이너의 종류

컨테이너(Container)를 뜻 그대로 직역하면 통, 그릇이다. 쌀통에 쌀을 담고 술통에 술을 저장하듯이 컨테이너는 무엇인가를 저장하는 것이다. STL의 컨테이너는 타입이 같은, 즉 동질적인 객체의 집합을 저장하고 관리하는 역할을 하는데 C와 C++에서 배웠던 배열, 연결 리스트, 스택 따위가 컨테이너의 좋은 예이다.

정수나 실수같은 기본형은 물론이고 클래스의 객체나 그 유도형 타입까지도 저장한다. 하옇든 똑같이 생긴 것들을 모아 놓는 장소라고 쉽게 생각할 수 있으며 다른 말로 컬렉션(Collection)이라고도 부른다. STL의 컨테이너는 자료를 저장하는 방식과 삽입, 정렬, 삭제하는 관리 방식에 따라 여러 가지가 있는데 크게 세 가지 부류로 구분된다.

 

시퀀스 컨테이너(Sequence Container) : 자료의 선형적인 집합이며 자료를 저장하는 기본 임무에 충실한 가장 일반적인 컨테이너이다. 삽입된 자료를 무조건 저장하며 입력되는 자료에 특별한 제약이나 관리 규칙은 없다. 사용자는 시퀀스의 임의 위치에 원하는 요소를 마음대로 삽입, 삭제할 수 있다. STL에는 벡터, 리스트, 데크 세 가지의 시퀀스 컨테이너가 제공된다.

연관 컨테이너(Associative Container) : 자료를 무조건 저장하기만 하는 것이 아니라 일정한 규칙에 따라 자료를 조직화하여 관리하는 컨테이너이다. 정렬이나 해시 등의 방법을 통해 삽입되는 자료를 항상 일정한 기준(오름차순, 해시 함수)에 맞는 위치에 저장해 놓으므로 검색 속도가 빠른 것이 장점이다. 표준 STL에는 정렬 연관 컨테이너인 셋, 맵 등의 컨테이너가 제공된다.

어댑터 컨테이너 (Adapter Container) : 시퀀스 컨테이너를 변형하여 자료를 미리 정해진 일정한 방식에 따라 관리하는 것이 특징이다. 스택, 큐, 우선 순위 큐 세 가지가 있는데 스택은 항상 LIFO의 원리로 동작하며 큐는 항상 FIFO의 원리로 동작한다. 자료를 넣고 빼는 순서를 외부에서 마음대로 조작할 수 없으며 컨테이너의 규칙대로 조작해야 한다.

 

세 부류의 컨테이너는 삽입, 삭제 규칙에 있어서 차이가 있다. 시퀀스는 삽입, 삭제에 별 제약이 없지만 연관 컨테이너는 신속한 검색을 위해 찾기 좋은 위치에 자동 삽입되며 어댑터는 FIFO, LIFO 등의 미리 정한 규칙의 통제를 따른다. 그러나 자료의 집합을 저장한다는 기능적인 면에서는 동일하며 그래서 제공하는 함수가 거의 비슷하고 사용 방법도 유사하다.

각 컨테이너들은 고유의 장단점을 가지고 있으며 모든 경우에 최적인 이상적인 컨테이너는 존재하지 않는다. 만약 모든 면에서 우월한 컨테이너가 존재한다면 나머지 컨테이너들은 더 이상 존재할 가치가 없을 것이다. 그러나 특정한 상황에 가장 잘 어울리며 성능상 가장 유리한 컨테이너는 존재할 수 있다. 컨테이너별로 잘난 점과 못난 점이 있다는 얘기다.

개발자는 관리하고자하는 데이터의 특성과 응용 프로그램의 요구에 맞는 컨테이너를 주의 깊게 선정해서 사용해야 하며 그러기 위해서는 각 컨테이너의 자료 저장 방식과 관리 방법에 대해 잘 파악하고 있어야 한다. 예를 들어 리스트는 검색은 느리지만 삽입, 삭제가 빠르므로 수시로 변하는 자료에 적합하고 벡터는 삽입, 삭제가 느리지만 읽기 속도가 빠르므로 대용량의 참조용 자료에 적합하다. 컨테이너 선택이 잘못되면 프로그램의 전체적인 성능은 보장할 수 없으며 안전성에도 많은 차이가 발생한다.

벡터

STL이 제공하는 많은 컨테이너 중에 여기서는 일단 벡터와 리스트를 통해 일반화된 컨테이너 사용 방법을 소개한다. 모든 생성자와 멤버 함수들을 일일이 나열하기보다는 개요 설명을 위한 예제 위주로 살펴볼 것이다. 이 두 컨테이너만 제대로 쓸 수 있다면 나머지 컨테이너들도 거의 유사한 방식으로 사용할 수 있으며 이런 일반성이 바로 STL의 목적이다.

벡터는 쉽게 말해서 동적 배열이라고 생각하면 된다. 요소의 개수에 맞게 자동으로 메모리를 재할당하여 크기를 신축적으로 늘릴 수 있는 배열이다. 단순한 동적 배열에 비해 템플릿 기반이므로 요소의 타입에 무관한 배열을 만들 수 있다는 것이 큰 장점이다. T 타입의 크기 n 배열을 만들려면 다음과 같이 선언한다.

 

vector<T> Name(n);

 

vector가 클래스 템플릿의 이름이므로 vector<T>는 T형 벡터 타입이 된다. T는 템플릿의 인수이므로 임의의 모든 타입을 다 사용할 수 있으며 Name은 명칭이므로 사용자가 원하는 어떤 이름도 지정할 수 있다. T 타입의 vector 객체를 Name이라는 이름으로 생성하되 생성자의 인수로 초기 요소의 개수를 전달한다. 크기 5의 정수형 벡터를 만든다면 다음과 같이 선언한다.

선언문이 조금 복잡한데 vector<int>까지가 하나의 클래스 이름이라는 것만 구분되면 별로 어렵지 않은 문장이다. ar은 지금 선언하고자 하는 객체, 더 쉽게 표현하면 변수의 이름이고 (5)는 이 클래스의 생성자로 전달되는 인수일 뿐이다. 만약 지금 이 선언문이 헷갈린다면 아직 STL을 볼 단계가 아니므로 템플릿부터 다시 공부해야 한다.

생성자의 인수로 크기를 생략하면 요소를 가지지 않는 빈 벡터가 만들어진다. 그러나 벡터는 동적으로 메모리를 관리하므로 실행중에 요소를 얼마든지 더 추가할 수 있다. 벡터는 많은 멤버 함수와 연산자들을 가지고 있다. 배열의 요소를 읽기 위한 [ ] 연산자가 정의되어 있으며 크기를 얻는 함수, 요소를 추가하는 함수, 삭제하는 함수 등도 있고 파괴자는 동적으로 할당된 배열을 자동으로 해제하기도 한다. 벡터가 일반 정적 배열과 다른 점 한 가지를 구경해 보자.

 

: vector

#include <iostream>

#include <vector>

using namespace std;

 

void main()

{

     int num;

     int i;

 

     printf("배열 크기를 입력하시오 : ");

     scanf("%d",&num);

     vector<int> vi(num);

 

     for (i=0;i<num;i++) {

          vi[i]=i*2;

     }

     for (i=0;i<num;i++) {

          printf("vi[%d]=%d\n",i,vi[i]);

     }

     printf("벡터의 크기는 %d입니다.\n",vi.size());

}

 

STL의 구성 요소들은 전부 헤더 파일에 선언되어 있다. 그래서 사용하고자 하는 구성 요소를 정의하는 헤더 파일을 반드시 인클루드해야 한다. 벡터는 vector에 정의되어 있으므로 이 헤더 파일을 인클루드했다. 나머지 구성 요소들도 자신의 이름과 동일한 헤더 파일에 정의되어 있다. 리스트는 list에, 맵은 map에 등 안 외워도 될 정도로 쉽다. 그런데 이 쉬운 걸 깜박 잊어 먹는 경우가 많으므로 에러가 발생하면 헤더 파일부터 제대로 인클루드했는지 점검해 보도록 하자.

정수 하나를 입력받아 벡터의 생성자로 전달했다. 정적 배열의 크기는 반드시 상수로만 지정할 수 있는데 비해 벡터는 실행중에 생성되므로 변수로도 크기를 지정할 수 있다. vi 정수형 벡터를 사용자가 입력한 크기 num으로 생성했다. 그리고 루프를 돌며 벡터의 각 요소에 첨자의 2배값을 넣어 보고 다시 출력했다. 벡터의 요소를 참조할 때는 정적 배열과 마찬가지로 [ ] 연산자와 첨자를 사용하면 된다. 임의 접근이 가능하므로 벡터내의 아무 요소나 읽고 쓸 수 있다. 다음은 4를 입력했을 때의 실행 결과이다.

 

배열 크기를 입력하시오 : 4

vi[0]=0

vi[1]=2

vi[2]=4

vi[3]=6

벡터의 크기는 4입니다.

 

벡터가 제대로 생성되었고 값을 잘 기억하는지만 확인해 본 것이다. 4가 아니라 400이나 1000000을 입력해도 잘 실행된다.

벡터의 할당 크기를 조사하려면 size 멤버 함수를 호출한다. 정적 배열은 일단 선언되면 실행 중에 그 크기를 알 수 없지만 벡터는 내부에서 크기를 관리하므로 size 함수로 현재 크기를 정확하게 조사할 수 있다. 벡터의 크기는 요소의 개수에 따라 신축적으로 관리되므로 초기 할당된 크기보다 더 많은 요소를 삽입해도 된다.

 

: pushback

#include <iostream>

#include <vector>

using namespace std;

 

void main()

{

     int i;

 

     vector<int> vi;

 

     for (i=0;i<10;i++) {

          vi.push_back(i*2);

     }

     for (i=0;i<10;i++) {

          printf("vi[%d]=%d\n",i,vi[i]);

     }

     printf("벡터의 크기는 %d입니다.\n",vi.size());

}

 

디폴트 생성자로 정수형의 빈 벡터 vi를 선언하고 push_back 함수로 뒤쪽에 요소를 10개 추가했다. push_back은 제일 뒤에 새로운 요소 하나를 추가(Append)하며 이 과정에서 벡터의 메모리가 부족하다면 재할당된다. 10개의 값이 제대로 잘 기억되는지만 확인해 보았는데 물론 잘 기억된다. 10개가 아니라 얼마든지 더 많은 요소를 추가하더라도 메모리 남은 용량까지는 기억할 수 있다.

벡터는 요소들을 인접한 메모리 위치에 연속적으로 저장한다. 그래서 단순한 첨자 연산만으로도 원하는 요소를 빠르게 읽고 쓸 수 있으며 임의의 요소로 이동하는 동작도 상수 시간에 수행할 수 있다. 읽기 속도가 빠르므로 정렬이나 이분 검색 등의 알고리즘에 대단히 효율적이다. 그러나 임의 접근이 가능하기 위해서는 요소 인접 조건을 항상 만족해야 하므로 중간에서 삽입 삭제할 때는 메모리를 밀고 당기는 처리를 해야 하며 따라서 삽입, 삭제 속도는 느리다.

리스트

리스트는 이중 연결 리스트로 구현된 컨테이너이다. 리스트의 요소들은 노드라는 구조체로 관리되며 노드끼리는 링크로 서로 연결되어 있어 요소의 논리적인 순서를 기억한다. 노드는 링크에 의해 연결될 뿐이므로 인접한 메모리에 배치되지 않아도 상관없으며 삽입, 삭제할 때도 앞뒤 노드의 링크만 조작하므로 대용량의 메모리를 밀고 당길 필요가 없다. 그래서 삽입, 삭제 속도가 대단히 빠르다. 반면 리스트의 한 요소를 찾으려면 첫 노드부터 순서대로 링크를 따라 이동해야 하므로 읽기 속도는 무척 느리다.

동일한 자료의 집합을 관리한다는 면에서 벡터와 용도는 동일하지만 내부적인 구조가 상이해서 확연히 다른 특징을 가진다. 리스트는 삽입, 삭제에 강하고 벡터는 읽고 쓰기에 강한 컨테이너라고 할 수 있다. 상대방의 장점은 곧 자신의 단점과 같아 이 둘은 서로 대체 가능하면서도 용도가 분명히 구분된다. 리스트의 선언 형식은 다음과 같다.

 

list<T> Name;

 

템플릿 인수로 요소의 타입 T를 전달하며 생성자의 인수는 없다. 리스트는 최초 빈 상태로 만들어도 빠른 속도로 삽입, 삭제를 할 수 있으므로 통상 빈 상태로 생성한다. 리스트에 요소를 삽입, 삭제할 때는 다음 4개의 멤버 함수를 사용한다.

 

멤버 함수

설명

push_front

제일 앞에 요소 추가

push_back

제일 뒤에 요소 추가

pop_front

제일 앞의 요소 삭제

pop_back

제일 뒤의 요소 삭제

 

리스트의 앞, 뒤에서 삽입, 삭제를 자유롭게 그것도 아주 빠른 상수 시간에 할 수 있다. 이에 비해 벡터는 제일 뒤에서만 추가, 제거가 가능하여 push_front, pop_front 함수를 제공하지 않는다.

중간에서 삽입, 삭제할 때는 insert, erase 멤버 함수를 사용하는데 링크만 조작하므로 삽입 위치에 상관없이 항상 상수 시간에 처리된다. 벡터와 동일한 예제를 리스트로 만들어 보자.

 

: list

#include <iostream>

#include <list>

using namespace std;

 

void main()

{

     list<int> li;

     int i;

 

     for (i=0;i<5;i++) {

          li.push_back(i*2);

     }

     list<int>::iterator it;

     for (it=li.begin(),i=0;it!=li.end();it++,i++) {

          printf("%d번째=%d\n",i,*it);

     }

}

 

리스트 컨테이너를 쓰기 위해 list 헤더 파일을 인클루드 하고 있으며 정수형 리스트 li를 선언한 후 다섯 개의 요소를 넣었다가 다시 출력해 보기만 했다.

 

0번째=0

1번째=2

2번째=4

3번째=6

4번째=8

 

리스트는 원래부터 가변적인 크기를 다룰 수 있으므로 초기 할당 크기를 지정할 필요가 없으며 디폴트 생성자로 리스트를 만들기만 했다. 빈 리스트로 생성되더라도 push_back을 호출하면 노드를 위한 메모리를 할당하고 링크를 연결하는 것도 내부에서 알아서 수행한다.

리스트의 노드들은 메모리의 곳곳에 흩어져 존재하여 임의 접근이 불가능하므로 모든 요소를 순회하려면 링크를 따라 순서대로 이동하는 수밖에 없다. 이때는 흔히 노드를 가리키는 포인터가 사용되는데 STL에서는 포인터 대신 반복자라는 특별한 객체를 사용한다. 반복자에 대해서는 잠시 후 소개하되 일단은 포인터처럼 요소를 가리킬 수 있고 증감 연산에 의해 주변 요소로 이동할 수 있는 기능을 가진다고 이해해 두자.

예제 코드의 it가 바로 정수형 리스트의 반복자이다. 리스트의 begin 멤버 함수는 첫 번째 요소, 그러니까 헤더의 위치를 구하며 end는 마지막 요소, 즉 테일의 위치를 구한다. 반복자를 헤더에서 테일 직전까지 순회하면서 반복자가 가리키는 요소인 *it를 읽어 출력하면 리스트의 모든 요소를 순회하면서 그 값을 출력할 수 있다.

맵은 두 개씩 짝을 이루는 데이터를 저장하는 컨테이너이다. 연관 컨테이너의 일종인 맵은 시퀀스와는 달리 아무렇게나 요소를 저장하지 않으며 정렬된 위치에 삽입한다. 항상 정렬된 상태로 관리되므로 이분 검색 기법을 사용할 수 있으며 따라서 요소가 아무리 많아도 굉장히 빠르게 검색할 수 있다. 대량의 데이터를 신속하게 검색해야 할 필요가 있을 때 맵이 주로 사용된다.

다음 예제는 편의점의 상품과 가격 목록을 맵에 저장해 두고 상품명으로 가격을 검색한다. 상품의 이름은 문자열이고 가격은 정수이며 두 개가 한 쌍이 되어 상품 하나의 정보를 표현하므로 이 쌍을 저장하기 위한 컨테이너로는 맵이 가장 적당한다.

 

: map

#include <iostream>

#include <string>

#include <map>

using namespace std;

 

struct SProduct

{

     string Name;

     int Price;

} arPro[]={

     {"맛동산",500},{"박카스",400},{"네스카페",250},{"신라면",450},

     {"88라이트",1900},{"불티나",300},{"스타킹",700},{"김치",2000},

     {"신문",500},{"비타500",500},{"비타1000",1000},{"왕꿈틀이",900},

     {"뽀빠이",200},{"위스퍼",800},{"콘텍600",600},{"페리오치약",2200},

     {"모나미볼펜",90},{"까페라떼",990},{"밧데리",1000},{"쵸코파이",250},

};

 

void main()

{

     map<string,int> mPro;

     map<string,int>::iterator it;

     int i;

     string Name;

 

     for (i=0;i<sizeof(arPro)/sizeof(arPro[0]);i++) {

          mPro[arPro[i].Name]=arPro[i].Price;

     }

 

     for (;;) {

          cout << "상품명을 입력하시오(끝낼때는 '끝'입력) : ";

          cin >> Name;

          if (Name=="끝") break;

          it=mPro.find(Name);

          if (it == mPro.end()) {

              cout << "그런 제품은 없습니다." << endl;

          } else {

              cout << Name << "의 가격은 " << it->second << "입니다." << endl;

          }

     }

}

 

맵을 사용하기 위해 map 헤더 파일을 인클루드했다. 예제의 코드는 굉장히 복잡해 보이는데 다음에 상세하게 알아볼 것이므로 일단 구경만 해 보자. 여기서는 구조체 배열에서 몇 개의 정보를 읽어왔지만 실제 프로그램에서는 DB에 기록된 방대한 레코드를 읽어들여 맵에 저장할 것이다. 실행해 보자.

 

상품명을 입력하시오(끝낼때는 '끝'입력) : 뽀빠이

뽀빠이의 가격은 200입니다.

상품명을 입력하시오(끝낼때는 '끝'입력) : 밧데리

밧데리의 가격은 1000입니다.

상품명을 입력하시오(끝낼때는 '끝'입력) : 끝

 

상품 이름을 입력하면 가격이 바로 바로 조사된다. 맵은 항상 정렬된 상태로 자료를 관리하므로 검색 속도가 빠른 것이 큰 장점이다. 이 정도 예제에서는 상품의 개수가 많지 않아 실용성을 느끼기 어렵지만 수십만종의 상품을 다루는 대규모 할인점에서는 신속한 계산을 위해 가격을 검색하는 속도가 대단히 중요하다.

 

여기서는 대표적이고 실용성이 높은 세 개의 컨테이너만 소개했는데 STL에는 이 외에도 스택, 큐, 데크 같은 잘 알려진 자료 구조들이 컨테이너로 제공된다. 사실 C/C++을 어느 정도 공부한 사람이라면 이런 자료 구조를 직접 만들어 쓰는 정도는 누구나 할 수 있다. 그러나 어렵지는 않지만 일일이 만들어 쓰려면 귀찮고 시간이 많이 걸리며 또 성능 보증이나 안전성을 장담하기도 어렵다.

STL은 누가 만들어도 똑같을 수밖에 없는 컨테이너들을 미리 만들어서 제공하므로 매번 이런 자료 구조를 만들 필요없이 STL의 컨테이너를 쓰는 방법만 익히면 된다. STL 컨테이너는 템플릿 기반이라 임의의 타입에 대해서 동작하며 빠르고 신뢰할만하다. 게다가 언어에 포함된 국제 표준이므로 팀 프로젝트에 유리하며 호환성, 이식성까지 덤으로 확보할 수 있다.