15. C++ STL 컨테이너 : 시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어댑터

 

• 컨테이너(container)

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

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

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

 

• 컨테이너의 종류

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

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

 

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

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

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

---

 

 

• 시퀀스 컨테이너(sequence container)

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

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

 

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

 

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

 

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

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

 

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

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

 

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

 - STL은 제공하는 기능에 따라 반복자를 다음과 같이 다섯 가지로 분류하고 있습니다.

 

• 시퀀스 컨테이너의 종류

 - 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<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)는 포인터이므로, 다음과 같은 특정 작업을 링크만 재배치하는 것으로 아주 빠르게 수행할 수 있습니다.

 

 

 - 예제

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

---

• 순방향 리스트(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() 함수 : 해당 요소를 원본 순방향 리스트에서 삭제하고, 대상 순방향 리스트의 지정된 위치에 삽입함.

---

연관 컨테이너(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;
}

---

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

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

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

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

 

  1. unordered_set

  2. unordered_multiset

  3. unordered_map

  4. unordered_multimap

---

컨테이너 어댑터

 

• 컨테이너 어댑터(container adapter)

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

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

 

컨테이너 어댑터의 종류

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

 

  1. stack

  2. queue

  3. priority_queue

---

• 스택(stack)

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

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

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

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

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

---

• 큐(queue)

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

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

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

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

 

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

---

• 우선순위 큐(priority_queue)

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

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

 

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

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