C++ :: STL이란?

STL은 표준 C++ 라이브러리의 일부분으로 Standard Template Library를 의미합니다. STL은 프로그램의 필요한 자료구조와 알고리즘을 템플릿으로 제공합니다. 또한 이들을 반복자라는 구성요소를 통해 연결합니다.

 

다음과 같은 구성요소가 있습니다.

💡 컨테이너(Container): 객체를 저장하는 객체. 컬렉션 혹은 자료구조로 불리기도 한다.

💡 반복자(iterator): 포인터와 비슷한 개념. 컨테이너의 원소를 가리키고 가리키는 원소에 접근하여 다음 원소를 가리킨다.

💡 알고리즘(Algorithm): 정렬, 삭제, 검색, 연산 등을 해결하는 방법을 제공한다.

💡 함수 객체(Function Object): 함수처럼 동작하는 객체. operand() 연산자를 오버로딩한 객체.

💡 어댑터(Adaptor): 구성 요소의 인터페이스를 변경해 새로운 인터페이스를 갖는 구성 요소로 변경한다.

💡 할당기(Allocator): 컨테이너의 메모리 할당 정책을 캡슐화한 클래스의 객체로 모든 컨테이너는 자신만의 기본 할당기를                             가지고 있다.

 

STL의 세 가지 특징은 효율성, 일반화 프로그램(재사용성), 확장성입니다. 

 

 

🌼 컨테이너

컨테이너는 두 가지 종류로 나뉩니다.

💡 표준 시퀀스 컨테이너(standard sequence container): 컨테이너 원소가 자신만의 삽입 위치를 가지는 컨테이너(ex. vector, deque, list : 선형적)
💡 표준 연관 컨테이너(standard associative container): 저장 원소가 삽입 순서와 다르게 특정 기준에 의해 자동 정렬되는 컨테이너(set, multiset, map, multimap : 비선형적)

 

또한 컨테이너는 데이터를 하나의 연속한 메모리 단위로 저장하느냐에 따라 두 가지로 나눌 수 있습니다.

 

💡 배열 기반 컨테이너(array-based container): 데이터 여러 개가 하나의 메모리 단위에 저장(vector, deque) 

💡 노드 기반 컨테이너(node-based container): 데이터 하나를 하나의 메모리 단위에 저장(list, set, multiset, map, multimap)

 

다음은 배열 기반 컨테이너 중 vector의 예제입니다.

 

⭐️ vector 컨테이너

#include <iostream>
#include <vector>
using namespace std;
 
int main(void){
    // int 타입을 저장하는 컨테이터 v
    vector<int> v;
 
    v.push_back(10);    // v에 정수 10 추가
    v.push_back(20);    // v에 정수 20 추가
    v.push_back(30);    // v에 정수 30 추가
    v.push_back(40);    // v에 정수 40 추가
    v.push_back(50);    // v에 정수 50 추가
 
    for(int i = 0 ; i < v.size() ; i++)
        cout << v[i] << endl;
 
    return 0;
}

 

⭐️ vector 컨테이너 실행결과

10
20
30
40
50

 

개인적으로 자바의 vector 클래스와 매우 유사하다는 느낌을 받았습니다. 바뀐 것은 자바의 add 메서드가 push_back으로 바뀐 것 정도라고 생각하면 될 것 같습니다. 

 

 

🌼 반복자

반복자는 포인터와 비슷합니다. 컨테이너에 저장된 원소를 순회하고 접근하는 방법을 제공합니다. 또한 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 합니다. 

STL에서는 컨테이너 원소(객체)의 집합을 순차열(sequence) 라고 합니다. 순차열은 순서가 존재합니다. 멤버 함수 begin()과 end()는 순차열의 시작과 끝을 가리키는 반복자를 반환합니다. 

다음 예제는 vector의 반복자를 사용하여 정수를 출력한 예제입니다.

 

⭐️ vector의 반복자

#include <iostream>
#include <vector>
using namespace std;
 
int main(void){
    vector<int> v;
 
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    vector<int> :: iterator iter;   // 반복자 생성(아직 원소를 가리키지 않음)
    for(iter = v.begin() ; iter != v.end() ; ++ iter)
        cout << *iter << endl;
    return 0;
}

 

⭐️ vector의 반복자 실행결과

10
20
30
40
50

 

여기서 ++iter는 반복자를 다음원소를 가리키도록 이동합니다. *iter는 iter가 가리키는 원소(객체)를 반환합니다. 

 

반복자는 다음과 같이 다섯 범주로 나뉩니다.

💡 입력 반복자(input iterator): 현 위치의 원소를 한 번만 읽을 수 있는 반복자

💡 출력 반복자(output iterator): 현 위치의 원소를 한 번만 쓸 수 있는 반복자

💡 순방향 반복자(forward iterator): 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자

💡 양방향 반복자(bidrectional iterator): 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자

💡 임의 접근 반복자(random access iterator): 양방향 반복자 기능에 +, -, +=, -=, [] 연산이 가능한 반복자

 

모든 컨테이너는 양방향 반복자 이상을 제공합니다.

 

다음은 임의 접근 반복자를 제공하는 vector 반복자 예제입니다.

 

⭐️ vector의 임의 접근 반복자

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    vector<int> :: iterator  iter = v.begin();
    cout << iter[0] << endl;
    cout << iter[1] << endl;
    cout << iter[2] << endl;
    cout << iter[3] << endl;
    cout << iter[4] << endl;
    cout << endl;
 
    iter += 2;          // += 연산
    cout << *iter << endl << endl;
 
    vector<int> :: iterator iter2 = iter + 2;
    cout << *iter2 << endl;
 
    return 0;
}

 

⭐️ vector의 임의 접근 반복자 실행결과

10
20
30
40
50
 
30
 
50

 

 🌼 알고리즘

STL은 순차열의 원소를 조사, 변경, 관리, 처리할 목적으로 알고리즘을 제공합니다. 알고리즘 대부분은 순방향 반복자를 요구하지만, 몇몇 알고리즘은 임의 접근 반복자를 요구합니다. STL 알고리즘은 다음과 같이 일곱 가지로 구분할 수 있습니다.

 

💡 원소를 수정하지 않는 알고리즘(nonmodifying algorithms)

💡 원소를 수정하는 알고리즘(modifying algorithms)

💡 제거 알고리즘(removing algorithms)

💡 변경 알고리즘(mutating algorithms)

💡 정렬 알고리즘(sorting algorithms)

💡 정렬된 범위 알고리즘(sorted range algorithms)

💡 수치 알고리즘(numeric algorithms)

 

자주 사용하는 find 알고리즘을 찾아봅시다

 

⭐️ find 알고리즘

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    vector<int> :: iterator iter;
    iter = find(v.begin(), v.end(), 20);    // [begin, end] 에서 20찾기
    cout << *iter << endl;
 
    iter = find(v.begin(), v.end(), 100);
    if(iter == v.end())
        cout << "100이 없음!" << endl;
    return 0;
}

 

⭐️ find 알고리즘 실행결과

20
100이 없음!

 

순차열을 정렬하는 sort는 임의 접근 반복자를 요구합니다. 다음 예제를 살펴보도록 합시다.

 

⭐️ vector와 list 컨테이너의 반복자와 sort 알고리즘

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
 
int main(){
    vector<int> v.
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    
    list<int> lt;
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);
    
    sort(v.begin(), v.end());
    sort(lt.begin(), lt.end());
    
    return 0;
}

vector는 정렬되지만 list는 정렬되지 않으므로 컴파일러 에러가 발생합니다.

 

 

 🌼 함수 객체

함수객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용됩니다. 다음 예제는 sort 알고리즘에 함수 객체 less와 greater를 적용한 것입니다.

 

⭐️ 함수 객체를 적용한 sort 알고리즘

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v;
    v.push_back(50);
    v.push_back(10);
    v.push_back(20);
    v.push_back(40);
    v.push_back(30);
 
    sort(v.begin(), v.end(), less<int>());
    for(vector<int> :: iterator iter = v.begin() ; iter != v.end() ; ++iter)
        cout<< *iter << " ";
    cout << endl;
 
    sort(v.begin(), v.end(), greater<int> ());
    for(vector<int>::iterator iter = v.begin() ; iter != v.end() ; ++iter)
        cout << *iter << " ";
    cout << endl;
    return 0;
}

 

⭐️ 함수 객체를 적용한 sort 알고리즘 실행결과

10 20 30 40 50 
50 40 30 20 10 

 

 

🌼 어댑터

어댑터는 구성 요소의 인터페이스를 변경합니다. STL 어댑터는 컨테이너 어댑터, 반복자 어댑터, 함수 어댑터가 있습니다. 

 

💡 컨테이너 어댑터(container adaptor): stack, queue, priority_queue

💡 반복자 어댑터(iterator adaptor): reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator

💡 함수 어댑터(function adaptor): 바인더(binder), 부정자(negator), 함수 포인터 어댑터(adaptor for pointers to functions)

 

stack의 입출력 예제는 다음과 같습니다.

 

⭐️ stack 컨테이너

#include <iostream>
#include <stack>
using namespace std;
 
int main(void){
    stack<int> st;
 
    st.push(10);
    st.push(20);
    st.push(30);
 
    cout << st.top() << endl;
    st.pop();
 
    cout << st.top() << endl;
    st.pop();
 
    cout << st.top() << endl;
    st.pop();
    
    if(st.empty())
        cout << "stack에 데이터 없음" << endl;
}

 

⭐️ stack 컨테이너 실행결과

30
20
10
stack에 데이터 없음

 

stack 컨테이너 어댑터의 컨테이너로 vector를 적용한 예제는 다음과 같습니다.

 

⭐️ vector 컨테이너를 적용한 stack 컨테이너

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int main(){
    stack<int, vector<int>> st;
 
    st.push(10);
    st.push(20);
    st.push(30);
 
    cout << st.top() << endl;
    st.pop();
    cout << st.top() << endl;
    st.pop();
    cout << st.top() << endl;
    st.pop();
 
    if(st.empty())
        cout << "stack에 데이터 없음" << endl;
 
    return 0;
}

 

⭐️ vector 컨테이너를 적용한 stack 컨테이너 실행결과

30
20
10
stack에 데이터 없음

 

다음은 반복자 어댑터 reverse_iterator를 이용해 vector의 반복자를 역방향 반복자로 변경한 것입니다.

 

⭐️ 역방향 반복자 reverse_iterator

#include <iostream>
#include <vector>
using namespace std;
 
int main(void){
    vector<int> v;
 
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    for(vector<int> :: iterator iter = v.begin() ; iter != v.end() ; ++iter)
        cout << *iter << " ";
    cout << endl;
 
    // 일반 반복자 iterator를 역방향 반복자 reverse iterator로 변환
    reverse_iterator<vector<int> :: iterator> riter(v.end());
    reverse_iterator<vector<int> :: iterator> end_riter(v.begin());
 
    for( ; riter != end_riter ; ++riter)
        cout << *riter << " ";
    cout << endl;
 
    return 0;
}

 

⭐️ 역방향 반복자 reverse_iterator 실행결과

10 20 30 40 50 
50 40 30 20 10 

 

riter은 iter에 반대되는 개념이라는 것을 알 수 있습니다.

 

다음은 vector의 역방향 반복자를 반환하는 rbegin()과 rend() 멤버 함수 예제입니다.

 

⭐️ vector의 역방향 반복자

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    vector<int> v;
 
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    for(vector<int> :: iterator iter = v.begin() ; iter != v.end() ; ++ iter)
        cout << *iter << " ";
    cout << endl;
 
    // STL 모든 컨테이너는 반복자 어댑터 reverse_iterator를 typedef 타입으로 정의하며
    // rbegin(), rend()로 컨테이너 역방향 반복자를 반환
    vector<int> :: reverse_iterator  riter(v.rbegin());
    for( ; riter != v.rend() ; ++ riter)
        cout << *riter << " ";
    cout << endl;
    
    return 0;
}

 

⭐️ vector의 역방향 반복자 실행결과

10 20 30 40 50 
50 40 30 20 10 

 

 

🌼 할당기

할당기는 컨테이너 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소입니다. 할당기는 템플릿 클래스이며 모든 컨테이너는 기본 할당기를 사용합니다. STL의 할당기는 사용자가 직접 할당기를 정의하고 사용할 수 있습니다.

 

사용자 정의 할당기를 사용하면 어떤 장점이 있을까요? 우선 사용자가 직접 메모리 할당 방식을 제어할 수 있습니다. 

 

다음 예제는 vector와 set 컨테이너에 기본 할당기를 지정한 예제입니다.

 

⭐️ 컨테이너 기본 할당기 allocator<T>

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
int main(void){
    vector<int, allocator<int>> v;
    v.push_back(10);
    cout << *v.begin() << endl;
 
    set<int, less<int>, allocator<int>> s;
    s.insert(10);
    cout << *s.begin() << endl;
 
    return 0;
}

 

⭐️ 컨테이너 기본 할당기 allocator<T> 실행결과 

10
10

 

📚 출처

공동환(2012), 뇌를 자극하는 C++ STL, 한빛미디어.