STL :: 표준 C++ 라이브러리

STL 표준 C++ 라이브러리

출처 : http://blog.daum.net/coolprogramming/77

STL은 표준 C++ 라이브러리의 일부분으로 Standard Template Library의 약자입니다.

STL은 사람마다 조금씩 다른 정의를 내립니다. C++의 권위자인 Scott Meyers는 STL을 "반복자를 가지고 동작하는 C++ 표준 라이브러리의 일부분"이라고 정의했습니다.

STL은 우리가 C++프로그래밍에서 만들어야 하는 여러 가지 자료구조 클래스와 알고리즘 등을 미리 만들어 놓은 라이브러리로 반복자라는 놈을 통해서 동작하는 라이브러리입니다.

 

STL의 주요 구성 요소로 컨테이너, 반복자, 알고리즘, 함수자가 있습니다.

• 컨테이너(Container) : 객체들을 저장하는 객체 혹은 클래스(vector, list, string, map 등)
• 반복자(iterator) : 컨테이너에 저장된 요소를 순회하고 접근하는 객체 혹은 클래스(추상화)
• 알고리즘(Algorithm) : 데이터를 다루기위한 일련의 함수(find, short, search 등)
• 함수자(Functor) : 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 클래스의 객체

 

그림으로 간단하게..

 

 

1, 컨테이너

컨테이너는 동일한 타입의 객체를 저장, 관리할 목적으로 만들어 놓은(추상화한) 클래스입니다.(혹은 그 컨테이너 클래스에 의해 만들어진 객체를 컨테이너라고도 합니다.)

컨테이너는 크게 두 가지로 나뉩니다.

• 표준  시퀀스 컨테이너(standard sequence container) : vector, string, deque, list인 선형방식의 컨테이너
• 표준 연관 컨테이너(standard associative container) : set, multiset, map, multimap인 비선형방식의 컨테이너

 

그림으로 간단하게..

 

 

또 컨테이너는 데이터를 하나의 메모리 단위로 저장하느냐에 따라 두 가지로 나뉩니다.

• 연속 메모리 기반 컨테이너(contiquous-memory) : 보통 데이터 여러개가 하나의 메모리 단위에 저장합니다. 배열 기반 컨테이너(array-based container)라고도 합니다.
• 노드 기반 컨테이너(node-based) : 데이터 하나를 하나의 메모리 단위에 저장합니다.

 

그림으로 간단하게..

 

 위 두 그림을 꼭 기억하세요.

컨테이너의 종류는 상당히 중요합니다. 종류에 따라 여러 가지 특징(성능, 무효화, 알고리즘 사용)이 달라지기 때문입니다. 자세한 내용은 다음에 하나하나 공부하도록 하겠습니다.

 

대표적인 컨테이너가 vector입니다.

간단한 vector 예제입니다.

#include<iostream>
#include<vector>
using namespace std;
voidmain( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    for(int i = 0 ; i < v.size() ; i++)

        cout << v[i] << endl;

}


1. 10
2. 20
3. 30

 vector<int> 클래스와 이 클래스로 생성한 객체 v가를 컨테이너입니다. push_back()과 size()는 멤버 함수입니다. v[i]는 operator[]() 멤버 함수인 연산자 중복 함수입니다. 컨테이너 v는 int형 객체(정수) 10, 20, 30을 저장합니다.

 

2, 반복자

반복자는 포인터와 비슷한 놈이라고 알아두시면 되겠습니다. 단 반복자는 컨테이너에 저장된 객체들에 접근하고 순회하는 일반화된 방법을 제공합니다.

그래서 반복자는 몇 가지 특징을 가져야 합니다.

• 컨테이너 내부의 객체를 가리키고 접근할 수 있어야 한다.
• 컨테이너 내부의 모든 객체를 순회할 수 있어야 한다.

STL의 모든 컨테이너는 자신만의 반복자를 제공합니다.

 

반복자는 조작 방법에 따라 다섯 가지로 나뉩니다.

• 입력 반복자(input iterator) : 현 위치의 데이터를 읽기만 가능한 반복자
• 출력 반복자(output iterator) : 현 위치에 데이터를 쓰기만 가능한 반복자
• 순방향 반복자(forward iterator) : 입력, 출력 반복자 기능 +  순방향으로 이동 가능한 반복자
• 양반향 반복자(bidirectional iterator) :  순방향 반복자 기능 + 역방향으로 이동 가능한 반복자
• 임의 접근 반복자(random access iterator) : 양방향 반복자 기능 + 반복자의 산술 연산이 가능한 반복자

 

임의 접근 반복자를 예로 보겠습니다. vector는 임의 접근 반복자를 제공합니다.

#include<iostream>
#include<vector>
using namespace std;

voidmain( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    vector<int>::iterator iter;
    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter << endl;

    iter = v.begin()+2;
    cout << *iter << endl;
}



1. 10
   20
   30
2. 30

 vector<int>::iterator처럼 반복자 클래스는 vector 클래스의 내포 클래스로 정의되어 있습니다. begin() 멤버 함수는 컨테이너 v에 저장된 첫 번째 객체를 가리키는 반복자를 반환합니다. end() 멤버 함수는 저장 객체의 끝을 의미하는 반복자를 리턴합니다. 또 임의 접근 반복자는 v.begin()+2처럼 반복자에 산술 연산이 가능합니다.

반복자는 뒤에서 다시 공부합니다.

 

3, 알고리즘

일반적인 용어의 알고리즘은 어떤 문제를 해결하기 수행 절차나 방법을 의미합니다. 만약 '정렬'이라는 문제가 주어진다면 정렬이라는 문제를 해결하는 방법(알고리즘)은 무수히 많습니다. 또 검색, 삭제, 복사 등의 문제도 모두 수많은 해결 방법이 존재합니다. 이런 해결 방법의 절차를 알고리즘이라 합니다.

 

 STL은 프로그램에서 반복되는 여러 가지 문제들의 해결 방법(알고리즘)을 일반화된 함수(템플릿 함수)로 제공합니다.

 

대표적인 정렬 알고리즘입니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
voidmain( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    vector<int>::iterator iter;
    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter <<' ';
    cout << endl;

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

    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter <<' ';
    cout << endl;
}


1. 10 80 30 20 50
   10 20 30 50 80

 모든 알고리즘은 반복자로 동작합니다. sort()는 v의 첫 번째 객체를 가리키는 반복자와 마지막을 의미하는 반복자를 인자로 받아 정렬합니다.

 

for 루프도 for_each()알고리즘을 사용하여 작성할 수 있습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
voidPrint(constint& n)
{
    cout << n <<' ';
}
voidmain( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    for_each(v.begin(), v.end(), Print);
    cout << endl;

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

    for_each(v.begin(), v.end(), Print);
    cout << endl;
}


1. 10 80 30 20 50
   10 20 30 50 80

 for_each()는 v.begin() 반복자부터 v.end()반복자까지 v 컨테이너에 저장된 모든 객체를 인자로 Print함수를 호출합니다. for_each() 알고리즘은 QuicStart2의 '함수 포인터와 함수자3'를 참고하세요.

알고리즘은 뒤에서 다시 공부합니다.

 

for_each()는 아래와 비슷하게 정의되어 있습니다.

template<class _InIt,class _Fn1>
inline  _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{  
    for (; _First != _Last; ++_First)
        _Func(*_First);
    return (_Func);
}


 

 4, 함수자

함수자는 함수처럼 사용할 수 있는 객체입니다. 함수자는 멤버 함수 operator()를 가지고 있기 때문에 객체를 함수처럼 사용할 수 있습니다.

 함수자는 QuickStart2의 '함수 포인터와 함수자2'를 참고하세요.

 

대표적인 함수자 클래스가 less<>와 greater<> 입니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

voidPrint(constint& n)
{
    cout << n <<' ';
}
voidmain( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    for_each(v.begin(), v.end(), Print);
    cout << endl;

    sort(v.begin(), v.end(), less<int>() );

    for_each(v.begin(), v.end(), Print);
    cout << endl;

    sort(v.begin(), v.end(), greater<int>() );

    for_each(v.begin(), v.end(), Print);
    cout << endl;
}


1. 10 80 30 20 50
   10 20 30 50 80
   80 50 30 20 10

  sort()함수의 세 번째 인자로 비교 함수자(predicate)를 전달하면 이 비교 함수자를 이용하여 정렬 객체를 비교합니다.

 

함수자 greater<>와 less는 아래와 비슷하게 정의되어 있습니다.

template<class _Ty>
struct greater{  
    booloperator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left > _Right);
    }
};
template<class _Ty>
struct less
{
    booloperator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left < _Right);
    }
};


 

 

수고하셨습니다. ~

 

 

 

 

.....

출처 : http://blog.daum.net/coolprogramming/77