책정리/혼자 연구하는 C,C++ 2

37장 STL 개요

GONII 2015. 3. 12. 09:41

37.1 STL 소개

37.1.1 일반화 프로그래밍

프로그램은 자료 구조와 알고리즘으로 구성된다. 자료구조는 처리하고자 하는 데이터를 표현하는 방법이고 알고리즘은 이 자료들을 가공하여 유용한 정보를 생산하는 기법이다. 좋은 프로그램을 만들려면 이 두 가지가 모두 필요하며 어느 한 쪽이 허술하면 전체적인 프로그램의 질이 떨어진다.

어떤 자료구조를 사용할 것인가는 프로그램의 특수한 상황에 따라 달라진다. 각 자료 구조마다 고유한 특징과 장단점이 있어서 모든 형태의 데이터에 다 어울리는 이상적인 자료구조는 없으며 상황에 따라 가장 효율적인 자료구조를 선택해야 한다.

OOP 이후의 또다른 시도인 STL은 일반화 프로그래밍 기법이라는 좀 더 발전된 개념의 재사용성을 제공한다. 일반화(Generic)는 객체 지향의 다음 세대라고 일컫어지는데 두 가지 측면에서 일반성을 제공한다.

  1. 임의 타입에 사용할 수 있는 자료구조를 만들 수 있다. 정수, 실수 등의 기본 타입은 물론이고 사용자 정의형 타입과 그 유도형까지도 관리할 수 있는 자료 구조를 정의할 수 있다. 자료구조의 일반성을 구현하기 위해 인수로 전달된 타입으로 클래스를 정의하는 C++의 템플릿 문법이다.
  2. 자료 구조의 형태나 내부 구조에 상관없이 임의의 데이터 집합에 적용할 수 있는 일반화된 알고리즘을 제공한다. 자료 구조에 상관없이 사용 방법이 동일하므로 어떠한 형태의 데이터에 대해서도 적용할 수 있다. 논리적으로 비슷한 작업은 같은 방법으로 수행할 수 있으며 이를 위해 반복자리는 일반화된 포인터를 사용한다.

STL은 Standard Template Library의 약자이다. 일단은 라이브러리이되 템플릿의 집합을 제공하는 라이브러리이며 현재 C++의 표준으로 채택되어 있다. C언어가 printf, strcpy, atoi 등의 함수 수준의 라이브러리를 제공하는데 비해 C++은 템플릿 수준의 훨씬 더 범용적인 라이브러리를 제공

37.1.2 STL의 특징

STL 특징, 장점

  1. 가장 큰 특징은 역시 이름이 의미하듯이 일반화를 지원한다는 점이다. 하나의 단일 알고리즘으로 복수 개의 컨테이너에 동일한 작업을 똑같은 방법으로 수행할 수 있다. 아직 일반화의 의미를 직감적으로 파악하기는 어렵겠지만 자료 구조마다 조작 방법이 특수한 기법과 반대의 의미라고 생각하면 된다.
  2. 컴파일 타임 메커니즘을 사용하기 때문에 실행시의 효율 저하가 거의 없다. STL을 쓰지 않았을 때의 코드에 비해 현격한 속도 차이가 없으며 어떤 경우는 오히려 더 빠르기도 하다. 그러나 고수준 라이브러리의 특성상 제대로 쓸 때만 이상적인 효율이 발휘된다는 제약도 존재한다.
  3. 객체 지향적이지 않다. 객체를 이용하기는 하지만 STL 자체가 객체를 반드시 요구하는 것은 아니다. 알고리즘 함수들은 대부분 전역 함수이며 멤버 함수로 제공되는 경우는 상대적으로 드물다. 상속의 개념도 많이 사용하지 않으며 동적 결합하는 가상 함수는 느리다는 이유로 사용하지 않는다. 모든 선택은 컴파일 중에 정적으로 결정된다.
  4. 표준이므로 이식성이 당연히 확보된다. STL로 작성한 코드는 표준을 준수하는 어떠한 컴파일러로도 문제없이 컴파일 할 수 있다. 아직까지 모든 컴파일러들이 표준을 제대로 지키지 않으므로 일시적인 이식성의 문제가 있기는 하지만 모든 컴파일러가 표준을 완벽히 준수하는 미래에는 완전한 이식성이 확보될 것이다.
  5. 확장 가능하다. 소스가 공개되어 있으므로 STL 라이브러리를 분석하여 원하는 컨테이너와 알고리즘을 직접 작성하여 사용할 수 있다. 표준에 없는 요소들이 제 3자에 의해 확장된 예는 아주 많으며 이 중 일부는 성능이 우수해서 다음 표준에 채택될 가능성이 높다.

       

STL 단점

  1. 템플릿에 기반하기 때문에 타입마다 함수와 클래스가 매번 구체화되어 코드가 비대해지는 고질적인 문제가 있다. 완전히 똑같은 컨테이너라도 타입이 바뀌면 두 벌의 거대한 코드 집합이 따로 생성된다. 물론 요즘같이 풍부한 메모리 환경에서 이는 별 문제가 안될 수도 있지만 낭비의 정도가 좀 심한 편이다. 극단적으로 표현하자면 약간의 속도 향상을 위해 크기는 아예 포기한 셈이다.
  2. STL로 작성한 코드는 가독성이 심하게 떨어진다. 템플릿 자체가 익숙치 않은 문법인데다 템플릿 클래스의 타입명이 길어 얼른 의미를 파악하기 어렵다. 게다가 이중 삼중으로 템플릿이 중첩되면 만든 사람조차도 거의 해석 불가능할 정도다. 소스의 가독성도 문제지만 에러 메시지도 의미를 해석하기 쉽지 않다. 소스가 난해하기 때문에 팀 프로젝트에 불리하며 디버깅도 어렵고 유지보수 비용이 증가한다.
  3. 배우기에 결코 쉽지 않다. C++ 문법을 어느 정도 터득한 사람이라면 STL의 전체 개요를 보는데 일주일이면 족하다. 그러나 단순히 아는 정도가 아니라 익숙하게 사용하려면 반년 정도가 소요된다. 구조에 대한 전반적인 이해가 필요하며 최소한 한 번씩은 사용해 봐야 자신감이 붙는다. 게다가 함정도 많고 잘못 이해하면 안정성까지 위협하므로 배우려면 확실히 정석대로 배워야 한다. 익숙해지면 생산성 향상에는 크게 기여하지만 쉽게 배워서 금방 활용할 수 있는 라이브러리는 아니다.

   

게다가 템플릿은 C++의 예외 처리와 잘 맞지 않아 이 둘을 같이 사용하는 것은 대단히 어렵다. 하지만 STL에 이미 구현되어 있는 컨테이너와 알고리즘은 개발자로서 탐을 내지 않을 수 없을 정도로 매력적이며 일단 익숙해지면 생산성이 눈에 띄게 증가하는 것은 분명한 사실이다.

37.2 STL의 구조

STL의 주요 구성 요소

컨테이너, 알고리즘, 반복자가 가장 중요한 세 요소

함수 객체는 알고리즘의 활용성을 높이는 역할

어댑터는 다른 요소들을 약간만 수정하여 형태를 변형

할당기는 컨테이너의 메모리를 관리하는 객체인데 디폴트가 작 되있어 거의 신경쓰지 않는다.

   

37.2.1 컨테이너

:: 컨테이너의 종류

컨테이너(Container)를 직역하면 통, 그릇이다. 어떤 것들을 담고 저장하듯이 컨테이너는 무엇인가를 저장하는 것이다.

STL의 컨테이너는 타입이 같은, 즉 동질적인 객체의 집합을 저장하고 관리하는 역할

ex) 배열, 연결 리스트, 스택

컨테이너는 자료를 저장하는 방식과 삽입, 정렬, 삭제하는 관레 방식에 따라 세 가지 부류로 구분

  1. 시퀀스 컨테이너(Sequence Container)

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

  2. 연관 컨테이너(Associative Container)

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

  3. 어댑터 컨테이너(Adapter Container)

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

       

세 부류의 컨테이너는 삽입, 삭제 규칙에 있어서 차이가 있다. 각 컨테이너들은 고유의 장단점을 가지고 있으며 모든 경우에 최적인 이상적인 컨테이너는 존재하지 않는다. 그러나 특정한 상황에 가장 잘 어울리며 성능상 가장 유리한 컨테이너는 존재할 수 있다.

개발자는 관리하고자 하는 데이터의 특성과 응용 프로그램의 요구에 맞는 컨테이너를 주의 깊게 선정해서 사용해야 하며 그러기 위해서는 각 컨테이너의 자료 저장 방식과 관리 방법에 대해 잘 파악하고 있어야 한다.

   

:: 벡터

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

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

   

  • 예제 vector

#include <iostream>

#include <vector>

using namespace std ;

   

void main ( void )

{

int                num ;

int                i ;

   

cout << "배열 크기를 입력하시오 : " ;

cin >> num ;

vector<int>                vi(num) ;

   

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

{

vi[i] = i*2 ;

}

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

{

cout << "vi[" << i << "] = " << vi[i] << endl ;

}

   

cout << "벡터의 크기는 " << vi.size() << endl ;

}

벡터는 동적으로 메모리를 관리하므로 실행 중에 요소를 얼마든지 더 추가할 수 있다. 벡터는 많은 멤버 함수와 연산자들을 가지고 있다. 배열의 요소를 읽기 위한 [ ] 연산자가 정의되어 있으며 크기를 얻는 함수, 요소를 추가하는 함수, 삭제하는 함수 등도 있고 파괴자는 동적으로 할당된 배열을 자동으로 해제하기도 한다.

   

정수 하나를 입력받아 벡터의 생성자로 전달했다. 정적 배열의 크기는 반드시 상수로만 지정할 수 있는데 비해 벡터는 실행 중에 생성되므로 변수로도 크기를 지정할 수 있다.

   

벡터의 크기는 요소의 개수에 따라 신축적으로 관리되므로 초기 할당된 크기보다 더 많은 요소를 삽입해도 된다.

STL의 구성 요소들은 전부 헤더 파일에 선언되어 있다. 그래서 사용하고자 하는 구성 요소를 정의하는 헤더 파일을 반드시 인클루드해야 한다.

  • 예제 pushback

#include <iostream>

#include <vector>

using namespace std ;

   

void main ( void )

{

int                i ;

   

vector<int>                vi ;

   

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

{

vi.push_back(i*2) ;

}

   

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

{

cout << "vi[" << i << "] = " << vi[i] << endl ;

}

   

cout << "벡터의 크기는 " << vi.size() << endl ;

}

디폴트 생성자로 정수형의 빈 벡터vi 생성

push_back 함수로 뒤쪽에 요소를 10개 추가

   

:: 리스트

리스트는 이중 연결 리스트로 구현된 컨테이너이다. 리스트의 요소들은 노드라는 구조체로 관리되며 노드끼리는 링크로 서로 연결되어 있어 요소의 논리적인 순서를 기억한다.

노드는 링크에 의해 연결될 뿐이므로 인접한 메모리에 배치되지 않아도 상관없으며 삽입, 삭제할 때도 앞뒤 노드의 링크만 조작하므로 대용량의 메모리를 밀고 당길 필요가 없다.

그래서 삽입, 삭제 속도가 대단히 빠르다. 반면 리스트의 한 요소를 찾으려면 첫 노드부터 순서대로 링크를 따라 이동해야 하므로 읽기 속도는 무척 느리다.

리스트는 최초 빈 상태로 만들어도 빠른 속도로 삽입, 삭제를 할 수 있으므로 통산 빈 상태로 생성한다. 리스트에 요소를 삽입, 삭제할 때는 다음 4개의 멤버 함수를 사용한다.

멤버 함수

설명

push_front

제일 앞에 요소 추가

push_back

제일 뒤에 요소 추가

pop_front

제일 앞에 요소 삭제

pop_back

제일 뒤에 요소 삭제

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

  • 예제 list

#include <iostream>

#include <list>

using namespace std ;

   

void main ( void )

{

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++ )

{

cout << i << "번째 = " << *it << endl ;

}

}

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

   

리스트의 노드들은 메모리의 곳곳에 흩어져 존재하여 임의 접근이 불가능하므로 모든 요소를 순회하려면 링크를 따라 순서대로 이동하는 수밖에 없다.

   

예제 코드의 it가 바로 정수형 리스트의 반복자이다. 리스트의 begin 멤버 함수는 첫 번째 요소, 그러니까 헤더의 위치를 구하며, end는 마지막 요소, 테일의 위치를 구한다.

   

:: 맵

맵은 두 개씩 짝을 이루는 데이터를 저장하는 컨테이너이다. 연관 컨테이너의 일종인 맵은 시퀀스와는 달리 아무렇게나 요소를 저장하지 않으며 정렬된 위치에 삽입한다.

항상 정렬된 상태로 관리되므로 이분 검색 기법을 사용할 수 있으며 따라서 요소가 아무리 많아도 굉장히 빠르게 검색할 수 있다. 대량의 데이터를 신속하게 검색해야 할 필요가 있을 때 맵이 주로 사용된다.

  • 예제 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 ( void )

{

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 ;

}

}

}

실제 프로그램에서는 DB에 기록된 방대한 레코드를 읽어 들여 맵에 저장할 것이다.

   

상품 이름을 입력하면 가격이 바로 바로 조사된다. 맵은 항상 정렬된 상태로 자료를 관리하므로 검색 속도가 빠른 것이 장점이다.

   

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

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

   

37.2.2 반복자

STL의 핵심 요소 = 반복자

반복자는 포인터와 하는 역할이나 사용 방법이 비슷하되 훨씬 더 일반화되어 있어 임의의 컨테이너와 함께 사용 가능

   

  • 컨테이너를 순회하는 방법

    컨테이너는 복수 개의 자료를 저장하는 집합소이므로 컨테이너에 대해 출력, 검색, 정렬, 대체 등의 연산을 하려면 먼저 각 요소를 순서대로 액세스 하는 순회가 필요함 배열의 각 요소를 출력하려면 요소들을 모두 방문하면서 그 값을 읽어야 한다. 요소들을 순서대로 방문 하는 것이 곧 순회이다.

       

  • 배열의 순회 방법

void print( int *ar, int num )

{

int i;

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

{

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

}

}

배열은 임의 접근이 가능하므로 0부터 배열의 크기 직전까지 첨자를 증가시키면서 [ ] 연산자로 첨자 위치의 요소를 출력

   

  • 연결 리스트의 순회 방법

void print( NODE *head )

{

NODE *now ;

for ( now = head->next ; now != tail ; now = now->next )

{

printf("%d\n", now->value) ;

}

}

노드를 가리키는 포인터 now를 선언하고 최초 head에서 시작하여 다음 노드를 검색하기를 tail에 이를 때까지 반복하면서 now가 가리키는 노드의 값을 출력

지원하는 컨테이너의 종류가 C개이고 구현하고 싶은 알고리즘이 A개일 때 모든 컨테이너에 대해 알고리즘 함수를 일일이 만들어야 하므로 결국 C*A 개의 함수를 각각 따로 만들어야 한다. 어떻게 하든 순회 방법을 일반화시켜 내부 구조 구조에 상관없이 동일한 방법으로 순회할 수 있다면 일고리즘의 일반성이 확보되어 모든 컨테이너에 슬 수 있는 범용 알고리즘을 만들 수 있을 것이다.

순회 방법을 일반화하기 위해 STL에서 사용하는 개념이 바로 반복자이다.

   

  • 반복자가 가지는 기능 (종류에 따라 일부 제외)
    • 컨테이너의 요소 하나를 가리키는 기본적인 역할을 한다.
    • 가리키는 지점의 요소를 읽고 쓸 수 있다. 내용을 읽는 *연산자가 정의된다.
    • 증감에 의해 주변 요소로 이동할 수 있다. ++, -- 등의 연산자가 정의된다.
    • 반복자끼리 대입, 비교 가능해야 한다. 대입, 비교 연산자가 정의된다.

       

    포인터는 위 4가지 기능 모두 가능 STL 알고리즘에 포인터를 사용할 수 있다.

    반복자를 사용하면 C의 포인터가 하는 동작을 일반화할 수 있으며 그래서 반복자를 포인터의 일반화라고 함

    모든 컨테이너는 시작점과 끝다음점을 조사하는 begin, end 멤버 함수를 제공

    반복자와 컨테이너의 begin, end 함수를 사용하면 모든 컨테이너를 동일한 방법으로 순회 할 수 있음

       

  • 예제 iterarray

#include <iostream>

using namespace std ;

   

void main ( void )

{

int ari[] = { 1, 2, 3, 4, 5 } ;

   

int *it ;

for ( it = &ari[0] ; it != &ari[5] ; it++ )

{

printf("%d\n", *it) ;

}

}

C의 정적 배열은 동일 타입의 변수 집합이므로 그 자체로 이미 컨테이너

정수형 배열을 가리키는 포인터 it를 선언하고 배열 첫 번째 요소의 번지에서 시작하여 끝다음점 요소 직전까지 순회하면서 *it를 출력하면 배열 요소 전체가 출력됨

   

여기서 사용된 it 포인터는 배열의 한 요소를 가리키며 증가하고 비교되며 *연산자로 읽기도 하므로 반복자의 요구 조건을 모두 만족

   

  • 예제 itervector

#include <iostream>

#include <vector>

   

using namespace std ;

   

void main ( void )

{

int ari[] = { 1, 2, 3, 4, 5 } ;

vector<int>                vi( &ari[0], &ari[5] ) ;

   

vector<int>::iterator it ;

for ( it = vi.begin() ; it != vi.end() ; it++ )

{

printf("%d\n", *it) ;

}

}

벡터의 한 요소를 가리키는 반복자 선언

vector<T>::iterator it ;

   

반복자를 begin으로 초기화하고 end 직전까지 반복자를 증가시키며 벡터의 매 요소를 순회하였다.

   

  • 예제 iterlist

#include <iostream>

#include <list>

using namespace std ;

   

void main ( void )

{

int ari[] = { 1, 2, 3, 4, 5 } ;

list<int>        li( &ari[0], &ari[5] ) ;

   

list<int>::iterator it ;

for ( it = li.begin() ; it != li.end() ; it++ )

{

printf("%d\n", *it) ;

}

}

   

begin ~ end 사이를 반복자가 순회하여 *it 표현시으로 순회 중의 요소를 액세스

벡터나 리스트 외의 다른 컨테이너들도 순회하는 방법은 동일

각 컨테이너의 내부 구조는 상당히 다르지만 반복자를 사용하면 똑같은 방법으로 순회할 수 있음

반복자는 컨테이너를 순회하는 방법과 컨테이너의 한 요소를 참조하는 방법을 획일화함으로써 알고리즘들이 컨테이너의 내부 구조에 대해 독립성을 가지도록 한다. 순회 방법이 일정하다면 하나의 함수로 임의의 컨테이너를 지원하는 알고리즘을 구현할 수 있다.

   

  • 예제 itergeneric

#include <iostream>

#include <vector>

#include <list>

using namespace std ;

   

template <typename IT>

void print(IT s, IT e)

{

IT it ;

for ( it = s ; it != e ; it++ )

{

printf("%d\n", *it) ;

}

}

   

void main ( void )

{

int ari[] = { 1, 2, 3, 4, 5 } ;

vector<int>                vi( &ari[0], &ari[5] ) ;

list<int>                li( &ari[0], &ari[5] ) ;

   

print( &ari[0], &ari[5] ) ;

print( vi.begin(), vi.end() ) ;

print( li.begin(), li.end() ) ;

}

print는 반복자 타입을 인수로 받아들이는 함수 템플릿으로 정의되어 있어 임의의 반복자 타입으로 구체화될 수 있다.

print의 본체는 IT 타입의 지역변수 it를 선언하고 인수로 전달된 범위 s~e 사이를 순회하며 *it로 반복자가 가리키는 값을 읽어 출력했다.

   

main에서는 정적 배열, 벡터, 리스트 세 컨테이너에 대해 print 함수를 호출하여 컨테이너 전체를 출력했다.

컨테이너에 요소를 삽입, 삭제할 때 도는 검색한 결과를 리턴할 때도 반복자가 필요

STL의 모든 함수들은 컨테이너내의 위치를 칭할 때 반복자를 사용하며 검색 결과를 보고 할 때도 반복자를 사용한다.

반복자는 임의의 컨테이너와 알고리즘이 서로를 몰라도 같이 동작 할 수 있도록 이어주는 매개체 역할

37.2.3 알고리즘

STL의 알고리즘 함수들은 대부분 전역함수로 작성되어 있음

STL은 일반화된 알고리즘을 제공하기 위해 캡슐화를 적극적으로 사용하지 않음

알고리즘 함수들은 대부분 algorithm 헤더 파일에 정의 되어 있음

find의 원형은 다음과 같다

template<typename InIt, class T>

InIt find(InIt first, InIt last, const T& value);

  • 예제 find

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

using namespace std ;

   

void main ( void )

{

int ari[] = { 1, 2, 3, 4, 5 } ;

vector<int>                vi( &ari[0], &ari[5] ) ;

list<int>                li( &ari[0], &ari[5] ) ;

   

puts(find(vi.begin(), vi.end(), 4) == vi.end() ? "없다" : "있다") ;

puts(find(li.begin(), li.end(), 8) == li.end() ? "없다" : "있다") ;

puts(find(&ari[0], &ari[5], 3) == &ari[5] ? "없다" : "있다") ;

}

find는 first ~ last 사이의 반복자 구간에서 T형의 값 val이 있는지 검사한다. 발견되면 해당 위치의 반복자가 리턴되며 발견되지 않을 경우 컨테이너 전체를 순회만 하고 종료되므로 구간의 끝인 last가 리턴된다.

   

자료를 일정한 기준에 따라 재배치하는 정렬

void sort( RanIt first, RanIt last ) ;

이 함수는 인수로 주어진 first ~ last 사이의 모든 요소를 정렬한다.

정렬을 하기 위해서는 객체들을 비교해야 하는데 sort 함수는 정렬 중에 < 연산자로 요소의 순위를 판단한다. 따라서 정렬 ㅈ대상 요소들은 < 연산자를 반드시 정의해야 한다. 정수, 실수 등의 기본 타입은 < 연산자로 비교할 수 있으므로 항상 정렬 가능하며 사용자가 정의한 클래스라도 < 연산자가 오버로딩되어 있으면 이 함수로 정렬 가능하다.

  • 예제 sort

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

   

void main()

{

int ar[] = {43,23,12,59,20};

vector<int> vi(&ar[0], &ar[5]);

   

sort(vi.begin(), vi.end());

   

vector<int>::iterator it;

for( it = vi.begin(); it != vi.end() ; it++ )

{

printf("%d\n", *it);

}

}

   

void reverse( BiIt first, BiIt last ) ;

reverse 함수는 이름대로 지정한 구간의 요소들 순서를 반대로 뒤집는다.

  • 예제 reverse

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

   

void main()

{

int ar[] = {1,2,3,4,5,6,7,8,9};

int i;

   

for( i = 0 ; i < 9 ; i++ ) printf("%d ", ar[i]); puts("");

reverse(&ar[2], &ar[6]);

for( i = 0 ; i < 9 ; i++ ) printf("%d ", ar[i]); puts("");

}

   

void random_shuiffle( RanIt first, RanIt last ) ;

구간 내 요소를 무작위로 마구 섞는다.

  • 예제 shuffle

#include <iostream>

#include <vector>

#include <algorithm>

#include <time.h>

using namespace std;

   

void main()

{

int i;

vector<int> vi(20);

vector<int>::iterator it;

   

for( i = 0 ; i < 20 ; i++ ) vi[i] = i;

srand(time(NULL));

random_shuffle(vi.begin(), vi.end());

   

for( it = vi.begin() ; it != vi.end() ; it++ )

{

cout << *it << ' ' ;

}

cout << endl;

}

   

   

반응형

'책정리 > 혼자 연구하는 C,C++ 2' 카테고리의 다른 글

39장 반복자  (0) 2015.03.14
38장 함수 객체  (0) 2015.03.13
36장 표준 라이브러리  (0) 2015.03.11
34장 네임 스페이스  (0) 2015.03.10
33장 타입 정보  (0) 2015.03.09

'책정리/혼자 연구하는 C,C++ 2'의 다른글

  • 현재글37장 STL 개요

관련글

댓글

티스토리툴바