1.1 자료구조와 STL

자료구조는 자료를 메모리에 표현하는 구조를 말하며 크게 선형 자료구조와 비 선형 자료구조로 나눠요.

“자료구조는

자료를 메모리에

표현하는 구조”

선형 자료구조에는 같은 종류의 자료를 연속적인 메모리에 관리하는 배열과 데이터와 링크로 구성하는 노드들의 선형 집합인 연결리스트가 있어요. 그리고 임시적으로 자료를 보관하는 버퍼로 가장 최근에 보관한 자료를 꺼내주는 스택(Last In First Out)과 가장 먼저 보관한 자료를 꺼내주는 큐(First In First Out)도 선형 자료구조인 배열이나 연결리스트를 이용한 잘 알려진 버퍼입니다.

“스택(Stack)은

Last In First Out

큐(Queue)는

First In First Out”

비 선형 자료구조에는 나무의 뿌리처럼 자료를 보관하는 모습을 계층적으로 표현할 수 있는 트리와 정점과 간선으로 표현하는 그래프 등이 있어요.

“트리는

계층적으로

자료를 보관하는

비선형 자료구조”

이 책에서는 이러한 자료구조들을 소개하고 표준 템플릿 라이브러리인 STL을 모델 삼아 구현해 볼거예요.

배열, 연결리스트, 트리, 그래프

STL(Standard Template Library, 표준 템플릿 라이브러리)은 개체들을 보관하기 위한 다양한 자료구조와 이들 자료구조에 보관된 개체들을 반복적으로 순회할 수 있게 해 주는 반복자, 사용자에서 정의한 코드를 입력 인자로 전달받아 처리할 수 있게 추상화한 함수 개체, 다양한 문제 해결 방법이 구현된 함수들로 구성된 알고리즘 등으로 구성되어 있어요.

이 책에서는 STL에 제공되는 일부 자료구조와 반복자, 함수 개체 및 알고리즘을 소개할게요. 사용 방법을 다루는 동시에 STL에 정의한 형식을 모델 삼아 직접 만들어 보는 실습도 할 거예요.

자료구조를 다루는 수많은 책에서는 기본 형식의 자료를 보관하는 형태의 예를 들거나 추상적인 설명을 하는 것과 다르게 이 책에서는 STL에 제공하는 것처럼 설계와 구현을 함으로써 어떠한 형식이라도 보관할 수 있게 할게요.

이를 통해 여러분은 자료구조뿐만 아니라 C++의 템플릿에 관한 문법을 비교적 충분히 학습할 수 있을 거예요. 그리고 자료구조와 STL의 내부를 이해하고 사용방법을 익힐 수 있을 거예요.

STL에서 제공하는 자료구조 종류에는 선형 자료구조인 vector와 list, 선형 자료구조를 특정 목적에 맞게 변형한 stack, queue, priority_queue 등이 있으며 비선형 자료구조는 set, multiset, map, multimap, hash_map 을 제공하고 기타 컨테이너로 bitset, valarray 등을 제공하고 있어요. 이 외에도 map이나 multimap에서 사용되는 단순히 키와 값의 쌍으로 구성된 pair를 제공해요.

STL에서 제공되는 자료구조는 템플릿으로 정의하고 있으며 클래스 이름과 같은 이름의 파일에 정의하고 있어요. 다음은 선형 자료구조인 vector를 사용하기 위해 포함문과 using 문을 표현한 것입니다.

#include <vector>
using std::vector;

#include <list>
using std::list;

STL에서는  제공하는 반복자는 컨테이너의 종류에 상관없이 컨테이너의 특정 구간에 보관된 개체들에 대해 차례대로 같은 방법으로 작업할 때 사용합니다. 실제 각 컨테이너의 자료를 보관하는 구조에 따라 각 반복자의 구현은 다르게 정의되어 있지만 같은 방법으로 사용할 수 있어요. 그리고 반복자에 간접 연산으로 보관한 데이터를 얻을 수 있습니다.

vector<int> vi;
... 중략...
vector<int>::iterator seek = vi.begin();
vector<int>::iterator end = vi.end();
for(  ; seek != end ; ++seek)
{
    cout<<*seek<<endl;
}

list<int> li;
... 중략...
list <int>::iterator seek = li.begin();
list<int>::iterator end = li.end();
for(  ; seek != end ; ++seek)
{
    cout<<*seek<<endl; 
}

STL에서는 다양한 알고리즘을 템플릿 함수로 제공하고 있어요. 그리고 일부 함수에서는 사용하는 곳에서 일부 알고리즘을 정의하여 인자로 전달합니다. 이 때 전달할 알고리즘의 추상적인 모습은 STL에서 사용하는 것에 맞게 구현해야 하는데 이를 함수 개체라고 부릅니다.

예를 들어 학생 관리 프로그램에서 학생 이름순으로 정렬할 것인지 번호 순으로 정렬할 것인지에 따라 비교하는 구문은 달라질 수 있겠죠. 이 때 사용하는 곳에서는 비교 알고리즘을 정의하여 정렬 기능에 입력 인자로 전달합니다.

bool Compare(Stu *s,Stu *b)
{
    return s->GetNum()<b->GetNum();
}
vector<Stu *> stues(100);
sort(stues.begin(), stues.end(),Compare);

이 책에서는 STL에서 제공하는 다양한 자료구조를 사용하는 방법을 살펴볼 거예요. 그리고 STL에서 제공하는 자료구조를 모델삼아 직접 만들어보는 실습도 할 거예요. 이 과정에서 반복자와 일부 알고리즘, 함수 개체도 사용법도 다룰 거예요.

자료구조와 알고리즘 with C++