C++ STL컨테이너

컨테이너(container)

STL에서 컨테이너(container)는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있습니다.

 

컨테이너는 클래스 템플릿으로, 컨테이너 변수를 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있습니다.

 

컨테이너에는 복사 생성과 대입을 할 수 있는 타입의 객체만을 저장할 수 있습니다.

 

또한, 컨테이너는 요소의 추가 및 제거를 포함한 다양한 작업을 도와주는 여러 멤버 함수를 포함하고 있습니다.

 

컨테이너의 각 요소에는 반복자를 사용하여 접근할 수 있습니다.

컨테이너의 종류

STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있습니다.

 

STL 컨테이너는 크게 다음과 같이 세 가지 유형으로 구분됩니다.

 

 

 

1. 시퀀스 컨테이너(sequence container)

 

2. 연관 컨테이너(associative container)

 

3. 컨테이너 어댑터(adapter container)

 

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

 

 

 

시퀀스 컨테이너(sequence container)

시퀀스 컨테이너(sequence container)는 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너입니다.

 

시퀀스 컨테이너에서는 삽입된 요소의 순서가 그대로 유지됩니다.

 

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

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

 

 

 

1. 모든 요소가 직선 순서대로 배치되어 있어야 합니다.

 

즉, 첫 번째 요소와 마지막 요소를 제외한 나머지 요소들은 반드시 앞뒤로 인접한 요소를 하나씩 가지고 있어야 합니다.

 

 

 

2. 반복자가 최소한 순방향 반복자(forward iterator) 이상이어야 합니다.

 

이것은 반복자가 이동할 때마다 요소들의 순서가 변하지 않음을 보장해 주는 것입니다.

 

 

 

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

 

시퀀스 컨테이너의 종류

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

 

 

 

1. vector

 

2. deque

 

3. list

 

4. forward_list

 

벡터(vector)

벡터(vector) 컨테이너는 동적 배열의 클래스 템플릿 표현이라 할 수 있습니다.

 

벡터(vector) 객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경합니다.

 

이 컨테이너는 vector 헤더 파일에 정의되어 있으며, 임의 접근을 제공하는 가장 간단한 시퀀스 컨테이너입니다.

 

 

 

벡터 컨테이너는 다음과 같이 선언합니다.

 

문법

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

 

 

 

템플릿 인수로는 벡터 컨테이너에 저장될 요소의 타입을 전달합니다.

 

생성자 인수로는 벡터 컨테이너의 초기 크기를 전달하며, 생략하면 요소를 가지지 않는 빈 벡터를 생성합니다.

 

 

 

예제

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, " "));

 

위의 예제에서 사용된 STL 함수는 다음과 같습니다.

 

 

 

1. size() 함수 : 컨테이너에 저장된 요소의 개수를 반환함.

 

2. push_back() 함수 : 컨테이너의 마지막 요소로 해당 데이터를 추가함.

 

3. begin() 함수 : 컨테이너의 첫 번째 요소를 가리키는 반복자를 반환함.

 

4. end() 함수 : 컨테이너의 마지막 요소 바로 다음(past-the-end)을 가리키는 반복자를 반환함.

 

데큐(deque)

데큐(deque) 컨테이너는 double-ended queue를 의미하며, 양쪽에 끝이 있는 큐(queue)입니다.

 

이 컨테이너는 컨테이너의 양 끝에서 빠르게 요소를 삽입하거나 삭제할 수 있습니다.

 

데큐 컨테이너는 deque 헤더 파일에 정의되어 있습니다.

 

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

 

 

 

예제

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, " "));

 

위의 예제에서 사용된 STL 함수는 다음과 같습니다.

 

 

 

1. push_front() 함수 : 컨테이너의 첫 번째 요소로 해당 데이터를 추가함.

 

2. front() 함수 : 컨테이너의 첫 번째 요소를 반환함.

 

3. pop_front() 함수 : 컨테이너의 첫 번째 요소를 삭제함.

 

리스트(list)

리스트(list) 컨테이너는 이중 연결 리스트(doubly linked list)의 클래스 템플릿 표현이라 할 수 있습니다.

 

이 컨테이너는 컨테이너의 모든 요소에서 양방향 접근, 빠른 삽입과 삭제를 할 수 있지만, 임의 접근은 할 수는 없습니다.

 

리스트 컨테이너는 list 헤더 파일에 정의되어 있습니다.

 

 

 

벡터 객체는 임의 접근을 통한 빠른 접근이 장점이며, 리스트 객체는 요소들의 빠른 삽입과 삭제가 장점입니다.

 

또한, 리스트를 구성하는 링크(link)는 포인터이므로, 다음과 같은 특정 작업을 링크만 재배치하는 것으로 아주 빠르게 수행할 수 있습니다.

 

함수	설명
swap()	두 요소의 위치를 서로 바꿈.
reverse()	리스트 전체의 요소의 위치를 역순으로 변경함.
sort()	리스트 전체의 요소를 정렬함.
unique()	같은 값이 인접해 있을 경우, 그 값들을 하나로 단일화함.
merge()	두 정렬된 리스트를 합병함.
splice()	두 리스트를 연결하거나, 한 쪽 리스트로 이동시킴.

 

다음 예제는 unique() 함수를 사용하여 리스트에서 서로 인접한 위치에 있는 동일한 값들을 제거하는 예제입니다.

 

예제

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, " "));

 

위의 예제에서 unique() 함수만을 사용하면, 서로 인접해 있지 않은 두 개의 3은 제거되지 않습니다.

 

따라서 unique() 함수를 사용하기 전에 sort() 함수를 먼저 사용하여 정렬하면, 리스트 내의 모든 중복값을 제거할 수 있습니다.

 

순방향 리스트(forward_list)

순방향 리스트(forward_list) 컨테이너는 단방향 연결 리스트(singly linked list)의 클래스 템플릿 표현이라 할 수 있습니다.

 

C++11부터 추가된 이 컨테이너는 모든 요소에서 순방향으로 접근할 수는 있지만, 역방향으로 접근할 수는 없습니다.

 

따라서 순방향 리스트 컨테이너에서는 오직 순방향 반복자(forward iterator)만을 사용합니다.

 

 

 

리스트 객체와 비교하면 순방향 리스트 객체는 더 적은 메모리를 가지고 간편하게 사용할 수 있는 장점이 있습니다.

 

 

 

예제

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, " "));

 

위의 예제에서 사용된 STL 함수는 다음과 같습니다.

 

 

 

1. remove() 함수 : 전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함.

 

2. splice_after() 함수 : 해당 요소를 원본 순방향 리스트에서 삭제하고, 대상 순방향 리스트의 지정된 위치에 삽입함.

 

 

 

따라서 위의 예제에서 splice_after() 함수가 호출된 후에 순방향 리스트 fls02에는 어떠한 요소도 저장되어 있지 않게 됩니다.

 

연관 컨테이너(associate container)

연관 컨테이너(associate container)는 키(key)와 값(value)처럼 관련있는 데이터를 하나의 쌍으로 저장하는 컨테이너입니다.

 

키와 값을 이용한 연관 컨테이너는 요소들에 대한 빠른 접근을 제공해 줍니다.

 

하지만 연관 컨테이너는 삽입되는 요소의 위치를 지정할 수는 없습니다.

 

 

 

이러한 연관 컨테이너는 보통 균형 잡힌 이진 탐색 트리(balanced binary search tree)나 해시 테이블(hash table)을 이용하여 구현합니다.

 

연관 컨테이너의 종류

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

 

 

 

1. set

 

2. multiset

 

3. map

 

4. multimap

 

집합(set)과 멀티집합(multiset)

집합(set) 컨테이너는 저장하는 데이터 그 자체를 키로 사용하는 가장 단순한 연관 컨테이너입니다.

 

이 컨테이너는 벡터와 달리 오름차순으로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.

 

 

 

집합(set)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.

 

하지만 멀티집합(multiset)은 키의 중복을 허용하므로, 같은 값을 여러 번 저장할 수 있습니다.

 

이 두 컨테이너는 모두 set 헤더 파일에 정의되어 있습니다.

 

 

 

집합 컨테이너는 다음과 같이 선언합니다.

 

문법

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

 

 

 

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

 

 

 

다음 예제는 반복자의 범위를 매개변수로 사용하는 집합 컨테이너의 생성자를 사용하는 예제입니다.

 

예제

int arr[5] = {10, 20, 30, 40, 50}; // 배열 생성 및 초기화

 

set<int> st(arr, arr+3); // 배열의 일부 요소를 가지고 셋 컨테이너를 생성함.

 

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, " "));

 

 

 

위의 예제에서 사용된 STL 함수는 다음과 같습니다.

 

 

 

1. insert() 함수 : 컨테이너에 해당 데이터를 추가함.

 

2. erase() 함수 : 전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함.

 

맵(map)과 멀티맵(multimap)

맵(map) 컨테이너는 키와 값의 쌍으로 데이터를 관리하는 진정한 연관 컨테이너입니다.

 

이 컨테이너는 집합 컨테이너와 마찬가지로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.

 

 

 

맵(map)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.

 

따라서 하나의 키에 하나의 값만이 연결될 수 있습니다.

 

하지만 멀티맵(multimap)은 값의 중복을 허용하므로, 하나의 키가 여러 개의 값과 연결될 수 있습니다.

 

이 두 컨테이너는 모두 map 헤더 파일에 정의되어 있습니다.

 

 

 

맵 컨테이너는 다음과 같이 선언합니다.

 

문법

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

 

 

 

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

 

 

 

다음 예제는 맵 컨테이너에 요소를 추가하는 방법을 알려주는 예제입니다.

 

예제

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;

 

}

 

 

 

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

 

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

순서가 지정되지 않은(unordered) 연관 컨테이너는 순서가 지정된 기존의 연관 컨테이너와 같은 동작을 합니다.

 

기존의 연관 컨테이너는 트리(tree) 구조를 기반으로 동작하지만, C++11부터 추가된 이 컨테이너는 해시 테이블(hash table)을 기반으로 동작하게 됩니다.

 

 

 

따라서 요소의 추가, 삭제 속도가 빨라졌으며, 다양한 검색 알고리즘을 사용할 수 있게 되었습니다.

 

순서가 지정된 연관 컨테이너는 양방향 반복자를 지원하지만, 이 컨테이너는 순방향 반복자만을 지원합니다.

 

 

 

C++11부터 추가된 순서가 지정되지 않은 연관 컨테이너는 다음과 같습니다.

 

 

 

1. unordered_set

 

2. unordered_multiset

 

3. unordered_map

 

4. unordered_multimap

 

컨테이너 어댑터(container adapter)

컨테이너 어댑터(container adapter)란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미합니다.

 

이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 합니다.

 

단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없습니다.

 

컨테이너 어댑터의 종류

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

 

 

 

1. stack

 

2. queue

 

3. priority_queue

 

스택(stack)

스택(stack) 컨테이너는 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공합니다.

 

스택 컨테이너는 stack 헤더 파일에 정의되어 있습니다.

 

 

 

스택 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 후입선출(LIFO)의 시멘틱을 따르는 자료 구조입니다.

 

즉, 가장 나중에 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조입니다.

 

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

 

멤버 함수	설명
empty()	스택이 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
size()	스택 요소의 총 개수를 반환함.
top()	스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소에 대한 참조를 반환함.
push()	스택의 제일 상단에 요소를 삽입함.
pop()	스택의 제일 상단에 있는 요소를 삭제함.

 

 

다음 예제는 스택 컨테이너를 사용하여 10진수를 2진수로 변환하는 예제입니다.

 

예제

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();

 

}

 

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

큐(queue)

큐(queue) 컨테이너는 deque 클래스의 인터페이스를 제한하여, 전형적인 큐 메모리 구조의 인터페이스를 제공합니다.

 

큐 컨테이너는 queue 헤더 파일에 정의되어 있습니다.

 

 

 

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

 

즉, 가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)되는 구조입니다.

 

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

 

멤버 함수	설명
empty()	큐가 비어 있으면 true를, 비어 있지 않으면 false를 반환함.
size()	큐 요소의 총 개수를 반환함.
front()	큐의 맨 앞에 있는(제일 먼저 저장된) 요소에 대한 참조를 반환함.
back()	큐의 맨 뒤에 있는(제일 나중에 저장된) 요소에 대한 참조를 반환함.
push()	큐의 맨 뒤에 요소를 삽입함.
pop()	큐의 맨 앞의 요소를 삭제함.

 

다음 예제는 큐 컨테이너를 사용하여 정해진 수만큼의 피보나치 수열을 출력하는 예제입니다.

 

예제

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());

 

}

 

피보나치 수열의 수학 공식은 다음과 같습니다.

f(n) = 1, n<=2일때

f(n) = f(n-1) + f(n-2), n>2일때

따라서 큐를 사용하는 것보다 재귀 호출을 통해 프로그램을 구현하는 편이 더욱 간단합니다.

우선순위 큐(priority_queue)

우선순위 큐(priority_queue) 컨테이너는 큐와는 달리 큐의 맨 앞의 요소로 가장 먼저 저장된 요소가 아닌, 가장 큰 값을 지닌 요소가 위치하게 됩니다.

 

또한, 큐가 deque 클래스를 기반으로 하는 것과는 달리, 우선순위 큐는 vector 클래스를 기반으로 합니다.

 

 

 

하지만 사용할 수 있는 멤버 함수는 큐 컨테이너와 같습니다.

 

우선순위 큐 컨테이너는 queue 헤더 파일에 정의되어 있습니다.

 

 

다음 예제는 우선순위 큐의 동작 방식을 보여주는 예제입니다.

 

예제

priority_queue<int> pq;

 

pq.push(10);

 

pq.push(20);

 

pq.push(100);

 

pq.push(3);

 

 

 

// 우선순위 큐의 모든 요소를 인출

 

while(!pq.empty())

 

{

 

cout << pq.top() << " ";

 

pq.pop();

 

}

 

위의 예제에서 볼 수 있듯이 우선순위 큐의 요소는 언제나 값의 내림차순으로 정렬되게 됩니다.