시퀀스 컨테이너
시퀀스 컨테이너(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, " "));
실행 결과
현재 벡터의 크기는 3입니다.
현재 벡터의 크기는 4입니다.
현재 벡터의 네 번째 요소는 40입니다.
현재 벡터의 모든 요소는 다음과 같습니다 :
10 20 30 40
위의 예제에서 사용된 STL 함수는 다음과 같습니다.
1. size() 함수 : 컨테이너에 저장된 요소의 개수를 반환함.
2. push_back() 함수 : 컨테이너의 마지막 요소로 해당 데이터를 추가함.
3. begin() 함수 : 컨테이너의 첫 번째 요소를 가리키는 반복자를 반환함.
4. end() 함수 : 컨테이너의 마지막 요소 바로 다음(past-the-end)을 가리키는 반복자를 반환함.
데큐(deque)
데큐(deque) 컨테이너는 double-ended queue를 의미하며, 양쪽에 끝이 있는 큐(queue)입니다.
이 컨테이너는 컨테이너의 양 끝에서 빠르게 요소를 삽입하거나 삭제할 수 있습니다.
데큐 컨테이너는 deque 헤더 파일에 정의되어 있습니다.
큐(queue)에 대한 더 자세한 사항은 C++ 컨테이너 어댑터 수업에서 확인할 수 있습니다.
데큐(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, " "));
실행 결과
현재 데큐의 모든 요소는 다음과 같습니다 :
10 20 30
현재 데큐의 첫 번째 요소는 10입니다.
현재 데큐의 모든 요소는 다음과 같습니다 :
20 30
위의 예제에서 사용된 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, " "));
실행 결과
현재 리스트의 모든 요소는 다음과 같습니다 :
1 2 3 4 3 5
위의 예제에서 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, " "));
실행 결과
현재 순방향 리스트의 모든 요소는 다음과 같습니다 :
10 20 30
fls01 : 10 40 50 20 30
fls02 :
위의 예제에서 사용된 STL 함수는 다음과 같습니다.
1. remove() 함수 : 전달된 값과 같은 값을 가지는 요소를 컨테이너에서 모두 삭제함.
2. splice_after() 함수 : 해당 요소를 원본 순방향 리스트에서 삭제하고, 대상 순방향 리스트의 지정된 위치에 삽입함.
따라서 위의 예제에서 splice_after() 함수가 호출된 후에 순방향 리스트 fls02에는 어떠한 요소도 저장되어 있지 않게 됩니다.
