19. STL 컨테이너(STL Container)

1. 키워드

STL 컨테이너(STL Container)
컨테이너(Container)
시퀀스 컨테이너(Sequence Container)
vector, deque, list, forward_list 컨테이너
연관 컨테이너(Associative Container)
set, multiset, map, multimap 컨테이너
순서가 지정되지 않은(Unordered) 연관 컨테이너
unordered_set, unordered_multiset, unordered_map, unordered_multimap
컨테이너 어댑터(Container Adapter)
stack, queue, priority_queue

2. 컨테이너

STL에서 컨테이너는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있다.
컨테이너는 클래스 템플릿으로, 컨테이너 변수를 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있다.
컨테이너에는 복사 생성과 대입을 할 수 있는 타입의 객체만을 저장할 수 있다.
또한, 컨테이너는 요소의 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 멤버 함수를 포함하고 있다.
참고로 컨테이너의 각 요소에는 반복자를 사용하여 접근할 수 있다.

1) 컨테이너의 종류

STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있다.
STL 컨테이너는 크게 다음과 같이 세 가지 유형으로 구분된다.

1] 시퀀스 컨테이너

2] 연관 컨테이너

3] 컨테이너 어댑터

컨테이너 종류	설명	컨테이너
시퀀스 컨테이너	데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너	`vector`, `deque`, `list`, `forwad_list`
연관 컨테이너	데이터를 일정 규칙에 따라 조직화하여 저장하고 관리하는 컨테이너	`set`, `multiset`, `map`, `multimap`
컨테이너 어댑터	간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없음	`stack`, `queue`, `priority_queue`

3. 시퀀스 컨테이너

시퀀스 컨테이너는 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너이다.
시퀀스 컨테이너에서는 삽입된 요소의 순서가 그대로 유지된다.

1) 시퀀스 컨테이너의 요구 사항

STL에서 시퀀스 컨테이너는 기본 컨테이너의 개념에 다음과 같은 요구 사항을 추가하여 정의한다.

1] 모든 요소가 직선 순서대로 배치되어 있어야 하는 즉, 첫 번째 요소와 마지막 요소를 제외한 나머지 요소들은 반드시 앞뒤로 인접한 요소를 하나씩 가지고 있어야 한다.

2] 반복자가 최소한 순방향 반복자 이상이어야 하는데, 이것은 반복자가 이동할 때마다 요소들의 순서가 변하지 않음을 보장해 주는 것이다.

3] 시퀀스 컨테이너의 요소들은 명확한 순서를 가지므로, 특정 위치를 참조하는 연산이 가능해야 한다.

2) 시퀀스 컨테이너의 종류

STL에서는 시퀀스 컨테이너로 다음과 같은 클래스 템플릿을 제공한다.

1] vector

2] deque

3] list

4] forward_list

(1) `vector`

vector 컨테이너는 동적 배열의 클래스 템플릿 표현이라 할 수 있다.
vector 객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경한다.
이 컨테이너는 vector 헤더 파일에 정의되어 있으며, 임의 접근을 제공하는 가장 간단한 시퀀스 컨테이너이다.

vector 컨테이너는 다음과 같이 선언한다.

vector<템플릿인수> 객체이름(생성자인수);

템플릿 인수로는 vector 컨테이너에 저장될 요소의 타입을 전달한다.
생성자 인수로는 vector 컨테이너의 초기 크기를 전달하며, 생략하면 요소를 가지지 않는 빈 vector를 생성한다.

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

int main(void) {
    vector<int> vc = {10, 20, 30};  // vector 객체의 선언 및 초기화
    cout << "현재 벡터의 크기는 " << vc.size() << "입니다." << endl;

    vc.push_back(40);  // vector 요소의 추가
    cout << "현재 벡터의 크기는 " << vc.size() << "입니다." << endl;
    cout << "현재 벡터의 네 번째 요소는 " << vc[3] << "입니다." << endl;

    cout << "현재 벡터의 모든 요소는 다음과 같습니다:" << endl;
    copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 현재 벡터의 크기는 3입니다.
// 현재 벡터의 크기는 4입니다.
// 현재 벡터의 네 번째 요소는 40입니다.
// 현재 벡터의 모든 요소는 다음과 같습니다:
// 10 20 30 40

위의 코드에서 사용된 STL 함수는 다음과 같다.

1] size()

컨테이너에 저장된 요소의 개수를 반환함

2] push_back()

컨테이너의 마지막 요소로 해당 데이터를 추가함

3] begin()

컨테이너의 첫 번째 요소를 가리키는 반복자를 반환함

4] end()

컨테이너의 마지막 요소 바로 다음을 가리키는 반복자를 반환함

(2) `deque`

deque 컨테이너는 양쪽에 끝이 있는 큐이다.
이 컨테이너는 컨테이너의 양 끝에서 빠르게 요소를 삽입하거나 삭제할 수 있다.
deque 컨테이너는 deque 헤더 파일에 정의되어 있다.

deque 객체는 vector 객체와 마찬가지로 임의 접근과 동적 크기의 장점을 가지며, vector로는 할 수 없는 전방 삽입과 전방 삭제도 빠르게 수행할 수 있다.

#include <deque>
#include <iostream>
#include <iterator>
using namespace std;

int main(void) {
    deque<int> dq = {20};  // deque 객체의 선언 및 초기화
    dq.push_back(30);      // 요소의 후방 삽입
    dq.push_front(10);     // 요소의 전방 삽입

    cout << "현재 데큐의 모든 요소는 다음과 같습니다:" << endl;
    copy(dq.begin(), dq.end(), ostream_iterator<int>(cout, " "));
    cout << endl
         << "현재 데큐의 첫 번째 요소는 " << dq.front() << "입니다." << endl;

    dq.pop_front();  // 요소의 전방 삭제
    cout << "현재 데큐의 모든 요소는 다음과 같습니다:" << endl;
    copy(dq.begin(), dq.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 현재 데큐의 모든 요소는 다음과 같습니다:
// 10 20 30
// 현재 데큐의 첫 번째 요소는 10입니다.
// 현재 데큐의 모든 요소는 다음과 같습니다:
// 20 30

위의 코드에서 사용된 STL 함수는 다음과 같다.

1] push_front()

컨테이너의 첫 번째 요소로 해당 데이터를 추가함

2] front()

컨테이너의 첫 번째 요소를 반환함

3] pop_front()

컨테이너의 첫 번째 요소를 삭제함

(3) `list`

list 컨테이너는 이중 연결 리스트(Doubly Linked List)의 클래스 템플릿 표현이라 할 수 있다.
이 컨테이너는 컨테이너의 모든 요소에서 양방향 접근, 빠른 삽입과 삭제를 할 수 있지만, 임의 접근은 할 수는 없다.
list 컨테이너는 list 헤더 파일에 정의되어 있다.

vector 객체는 임의 접근을 통한 빠른 접근이 장점이며, list 객체는 요소들의 빠른 삽입과 삭제가 장점이다.
또한, list를 구성하는 링크는 포인터이므로, 다음과 같은 특정 작업을 링크만 재배치하는 것으로 아주 빠르게 수행할 수 있다.

1] swap()

두 요소의 위치를 서로 바꿈

2] reverse()

list 전체의 요소의 위치를 역순으로 변경함

3] sort()

list 전체의 요소를 정렬함

4] unique()

같은 값이 인접해 있을 경우, 그 값들을 하나로 단일화함

5] merge()

두 정렬된 list를 합병함

6] splice()

두 list를 연결하거나, 한 쪽 list로 이동시킴

다음의 코드는 unique() 함수를 사용하여 list에서 서로 인접한 위치에 있는 동일한 값들을 제거하는 것이다.

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main(void) {
    list<int> ls = {1, 2, 2, 3, 4, 3, 5, 5};  // list 객체의 선언 및 초기화
    // ls.sort(); // 1, 2, 3, 4, 5
    ls.unique();  // 1, 2, 3, 4, 3, 5
    cout << "현재 리스트의 모든 요소는 다음과 같습니다:" << endl;
    copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 현재 리스트의 모든 요소는 다음과 같습니다:
// 1 2 3 4 3 5

위의 코드에서 unique() 함수만을 사용하면, 서로 인접해 있지 않은 두 개의 3은 제거되지 않는다.
따라서 unique() 함수를 사용하기 전에 sort() 함수를 먼저 사용하여 정렬하면, list 내의 모든 중복값을 제거할 수 있다.

(4) `forward_list`

forward_list 컨테이너는 단방향 연결 리스트(Singly Linked List)의 클래스 템플릿 표현이라 할 수 있다.
C++11부터 추가된 이 컨테이너는 모든 요소에서 순방향으로 접근할 수는 있지만, 역방향으로 접근할 수는 없다.
따라서 forward_list 컨테이너에서는 오직 순방향 반복자만을 사용한다.

list 객체와 비교하면 forward_list 객체는 더 적은 메모리를 가지고 간편하게 사용할 수 있는 장점이 있다.

#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;

int main(void) {
    forward_list<int> fls01 = {10, 20, 400, 30};  // forward_list 객체의 선언 및 초기화
    forward_list<int> fls02 = {40, 50};
    forward_list<int>::iterator itr;

    fls01.remove(400);  // 값이 400인 모든 요소를 삭제함.
    cout << "현재 순방향 리스트의 모든 요소는 다음과 같습니다:" << endl;
    copy(fls01.begin(), fls01.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    itr = fls01.begin();             // fls01의 첫 번째 요소를 가리키도록 반복자를 초기화함
    fls01.splice_after(itr, fls02);  // fls02의 모든 요소를 fls01의 첫 번째 요소 다음에 삽입함
    cout << "fls01: ";
    copy(fls01.begin(), fls01.end(), ostream_iterator<int>(cout, " "));
    cout << endl
         << "fls02: ";
    copy(fls02.begin(), fls02.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 현재 순방향 리스트의 모든 요소는 다음과 같습니다:
// 10 20 30
// fls01: 10 40 50 20 30
// fls02:

위의 코드에서 사용된 STL 함수는 다음과 같다.

1] remove()

전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함

2] splice_after()

해당 요소를 원본 forward_list에서 삭제하고, 대상 forward_list의 지정된 위치에 삽입함

따라서 위의 코드에서 splice_after() 함수가 호출된 후에 fls02에는 어떠한 요소도 저장되어 있지 않게 된다.

4. 연관 컨테이너

연관 컨테이너는 키(Key)와 값(Value)처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너이다.
키와 값을 이용한 연관 컨테이너는 요소들에 대한 빠른 접근을 제공해 준다.
하지만 연관 컨테이너는 삽입되는 요소의 위치를 지정할 수는 없다.
이러한 연관 컨테이너는 보통 균형 잡힌 이진 탐색 트리(Balanced Binary Search Table)나 해시 테이블(Hash Table)을 이용하여 구현한다.

1) 연관 컨테이너의 종류

STL에서는 연관 컨테이너로 다음과 같은 클래스 템플릿을 제공한다.

1] set

2] multiset

3] map

4] multimap

(1) `set`과 `multiset`

set 컨테이너는 저장하는 데이터 그 자체를 키로 사용하는 가장 단순한 연관 컨테이너이다.
이 컨테이너는 vector와 달리 오름차순으로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠르다.

set에서는 키는 유일해야 하므로, 키의 중복을 허용하지 않는다.
하지만 multiset은 키의 중복을 허용하므로, 같은 값을 여러 번 저장할 수 있다.
이 두 컨테이너는 모두 set 헤더 파일에 정의되어 있다.

set 컨테이너는 다음과 같이 선언한다.

set<템플릿인수> 객체이름;

템플릿 인수로는 set 컨테이너에 저장될 키의 타입을 전달한다.

다음의 코드는 반복자의 범위를 매개변수로 사용하는 set 컨테이너의 생성자를 사용하는 것이다.

#include <iostream>
#include <iterator>
#include <set>
using namespace std;

int main(void) {
    int arr[5] = {10, 20, 30, 40, 50};  // 배열 생성 및 초기화
    set<int> st(arr, arr + 3);          // 배열의 일부 요소를 가지고 set 컨테이너를 생성함
    cout << "현재 집합의 모든 요소는 다음과 같습니다." << endl;
    copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    st.insert(60);  // 요소의 추가
    st.insert(70);  // 요소의 추가
    st.erase(20);   // 요소의 삭제
    cout << "현재 집합의 모든 요소는 다음과 같습니다." << endl;
    copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

// 현재 집합의 모든 요소는 다음과 같습니다.
// 10 20 30
// 현재 집합의 모든 요소는 다음과 같습니다.
// 10 30 60 70

위의 코드에서 사용된 STL 함수는 다음과 같다.

1] insert()

컨테이너에 해당 데이터를 추가함

2] erase()

전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함

(2) `map`과 `multimap`

map 컨테이너는 키와 값의 쌍으로 데이터를 관리하는 진정한 연관 컨테이너이다.
이 컨테이너는 set 컨테이너와 마찬가지로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠르다.

map에서는 키는 유일해야 하므로, 키의 중복을 허용하지 않는다.
따라서 하나의 키에 하나의 값만이 연결될 수 있다.
하지만 multimap은 값의 중복을 허용하므로, 하나의 키가 여러 개의 값과 연결될 수 있다.
이 두 컨테이너는 모두 map 헤더 파일에 정의되어 있다.

map 컨테이너는 다음과 같이 선언한다.

map<템플릿인수> 객체이름;

템플릿 인수로는 map 컨테이너에 저장될 키의 타입과 값의 타입을 전달한다.

다음의 코드는 map 컨테이너에 요소를 추가하는 방법을 알려주는 것이다.

#include <iostream>
#include <iterator>
#include <map>
using namespace std;

int main(void) {
    map<string, int> mp;
    mp.insert(pair<string, int>("국어", 80));  // 익명의 pair 객체를 생성하여 추가함
    mp["수학"] = 100;                          // 첨자 연산자를 이용하여 추가함

    cout << "현재 맵의 모든 요소는 다음과 같습니다." << endl;
    map<string, int>::iterator it;
    for (it = mp.begin(); it != mp.end(); it++) {
        cout << it->first << ": " << it->second << endl;
    }
    return 0;
}

// 현재 맵의 모든 요소는 다음과 같습니다.
// 국어: 80
// 수학: 100

map 컨테이너 요소의 키는 first라는 멤버 변수에, 값은 second라는 멤버 변수에 각각 저장되어 있다.

2) 순서가 지정되지 않은 연관 컨테이너

순서가 지정되지 않은 연관 컨테이너는 순서가 지정된 기존의 연관 컨테이너와 같은 동작을 한다.
기존의 연관 컨테이너는 트리 구조를 기반으로 동작하지만, C++11부터 추가된 이 컨테이너는 해시 테이블을 기반으로 동작하게 된다.
따라서 요소의 추가, 삭제 속도가 빨라졌으며, 다양한 검색 알고리즘을 사용할 수 있게 되었다.
순서가 지정된 연관 컨테이너는 양방향 반복자를 지원하지만, 이 컨테이너는 순방향 반복자만을 지원한다.
C++11부터 추가된 순서가 지정되지 않은 연관 컨테이너는 다음과 같다.

1] unordered_set

2] unordered_multiset

3] unordered_map

4] unordered_multimap

5. 컨테이너 어댑터

컨테이너 어댑터란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다.
이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 한다.
단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다.

1) 컨테이너 어댑터의 종류

STL에서는 컨테이너 어댑터로 다음과 같은 클래스 템플릿을 제공한다.

1] stack

2] queue

3] priority_queue

(1) `stack`

stack 컨테이너는 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공한다.
stack 컨테이너는 stack 헤더 파일에 정의되어 있다.

스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료 구조이다.
즉, 가장 나중에 저장된 데이터가 가장 먼저 인출되는 구조이다.

stack 컨테이너는 스택 메모리 구조를 표현하기 위해 다음과 같은 멤버 함수를 제공한다.

1] empty()

스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함

2] size()

스택 요소의 총 개수를 반환함

3] top()

스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소에 대한 참조를 반환함

4] push()

스택의 제일 상단에 요소를 삽입함

5] pop()

스택의 제일 상단에 있는 요소를 삭제함

다음의 코드는 stack 컨테이너를 사용하여 10진수를 2진수로 변환하는 것이다.

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

int main(void) {
    int decimal = 123;
    stack<int> st;

    // 10진수를 2진수로 변환
    do {
        st.push(decimal % 2);
        decimal /= 2;
    } while (decimal);

    // 스택의 모든 요소를 인출
    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }

    cout << endl;

    return 0;
}

// 1111011

참고로 stack 컨테이너는 요소에 대한 임의 접근을 허용하지 않을 뿐만 아니라, 스택을 순회하는 반복자도 허용하지 않는다.

(2) `queue`

queue 컨테이너는 deque 클래스의 인터페이스를 제한하여, 전형적인 큐 메모리 구조의 인터페이스를 제공한다.
queue 컨테이너는 queue 헤더 파일에 정의되어 있다.

큐 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO)의 시멘틱을 따르는 자료 구조이다.
즉, 가장 먼저 저장된 데이터가 가장 먼저 인출되는 구조이다.

queue 컨테이너는 큐 메모리 구조를 표현하기 위해 다음과 같은 멤버 함수를 제공한다.

1] empty()

큐가 비어 있으면 true를, 비어 있지 않으면 false를 반환함

2] size()

큐 요소의 총 개수를 반환함

3] front()

큐의 맨 앞에 있는(제일 먼저 저장된) 요소에 대한 참조를 반환함

4] back()

큐의 맨 뒤에 있는(제일 나중에 저장된) 요소에 대한 참조를 반환함

5] push()

큐의 맨 뒤에 요소를 삽입함

6] pop()

큐의 맨 앞의 요소를 삭제함

다음의 코드는 queue 컨테이너를 사용하여 정해진 수만큼 피보나치 수열을 출력하는 것이다.

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

int main(void) {
    int n = 20;  // 20개의 피보나치 수열을 출력함
    queue<int> que;
    que.push(0);  // 초기값인 0과 1을 저장함
    que.push(1);

    // 피보나치 수열
    for (int i = 2; i < n; i++) {
        int temp = que.front();
        cout << temp << " ";
        que.pop();
        que.push(temp + que.front());
    }

    cout << endl;

    return 0;
}

// 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

(3) `priority_queue`

priority_queue 컨테이너는 queue와는 달리 큐의 맨 앞의 요소로 가장 먼저 저장된 요소가 아닌, 가장 큰 값을 지닌 요소가 위치하게 된다.
또한, queue가 deque 클래스를 기반으로 하는 것과 달리, priority_queue는 vector 클래스를 기반으로 한다.

하지만 사용할 수 있는 멤버 함수는 queue 컨테이너와 같다.
priority_queue 컨테이너는 queue 헤더 파일에 정의되어 있다.

다음의 코드는 priority_queue의 동작 방식을 보여주는 것이다.

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

int main(void) {
    priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(100);
    pq.push(3);

    // 우선 순위 큐의 모든 요소를 인출
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }

    cout << endl;

    return 0;
}

// 100 20 10 3

위의 코드에서 볼 수 있듯이 priority_queue 의 요소는 언제나 값의 내림차순으로 정렬되게 된다.

19. STL 컨테이너(STL Container)

1. 키워드

2. 컨테이너

1) 컨테이너의 종류

3. 시퀀스 컨테이너

1) 시퀀스 컨테이너의 요구 사항

2) 시퀀스 컨테이너의 종류

(1) vector

(2) deque

(3) list

(4) forward_list