[C++]STL 표준 C++ 라이브러리

STL은 표준 C++ 라이브러리의 일부분으로 Standard Template Library의 약자 입니다.
STL은 사람마다 조금씩 다른 정의를 내립니다. C++권위자인 Scott Meyers는 STL을 "반봅자를 가지고 동장하는 C++ 표준 라이브러리의 일부분"이라고 정의했습니다
STL은 우리가 C++프로그래밍에서 만들어야 하는 여러가지 자료구조 클래스와 알고리즘 등을 미리 만들어 놓은 라이브러리로 반복자라는 놈을 통해서 동작하는 라이브러리입니다.

STL의 주요 구성요소

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

1. 컨테이너

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

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

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

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

컨테이너의 종류는 상당히 중요합니다. 종류에 따라 여러가지 특징(성능, 무효화, 알고리즘 사용)이 달라지기 때문입니다.

대표적인 컨테이너가 vector입니다.
간단한 vector 예제 입니다.

#include <iostream>
#include <vector>
using namespace std;
void main( )
{
    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) : 입력, 출력 반복자 기능 + 순방향으로 이동 가능한 반복자
• 양방향 반복자(bidrectional iterator) : 순방향 반복자 기능 + 역방향으로 이동 가능한 반복자
• 임의 접근 반복자(random access iterator) : 양방향 반복자 기능 + 반복자의 산술 연산이 가능한 반복자

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

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

void main( )
{
    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;
void main( )
{
    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;
void Print(const int& n)
{
    cout << n <<' ';
}
void main( )
{
    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()는 아래와 비슷하게 정의되어 있습니다.

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()를 가지고 있기 때문에 객체를 함수처럼 사용할 수 있습니다.

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

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

void Print(const int& n)
{
    cout << n <<' ';
}
void main( )
{
    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{  
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left > _Right);
    }
};
template<class _Ty>
struct less
{
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left < _Right);
    }
};