[C++] 데큐와 리스트
순차 컨테이너와 그 컨테이너의 속한 벡터를 알아보았었다. 이번에는 순차 컨테이너에 속하는 데큐와 리스트를 알아볼 것이다. 벡터와 비교해서 어느부분이 차이가 있고 어떠한 이점을 가지고 있는지 살펴보자!
데큐 (Deque, Double Ended Queue)
#include <deque>
//...
deque<DataType> dq;
모든 면에서 벡터와 유사하지만 작업 위치에 따른 실행 비용에서 차이가 있다. 벡터처럼 모든 요소들을 큰 메모리 블럭에 저장하지만 요소들을 여러개의 메모리블로으로 이용한다.
▹ 마지막에 추가/제거하는 작업의 속도는 빠른 속도(O(1))이지만 중간에 요소를 추가/제거하는 속도는 비교적 느린속도(O(N))이다.
▹ 큐와 같이 FIFO(First In First Out)의 데이터 구조를 구현하는 데에 최적의 성능을 가진다. 그리고 큐와는 다르게 양방향 입출력이 가능하다.
▹ 몇개의 메모리 블럭에 요소들을 보관하며 각각의 메모리 블럭 내에서는 순차적으로 요소들을 보관한다.
▹ 탐색 속도는 벡터와 비교해서 비슷하지만 작업속도는 벡터보다는 느린편이다.
데큐의 생성자와 반복자
//생성자
deque<DataType> dq //빈 컨테이너
deque<DataType> dq(n) //기본 값으로 초기화된 n개의 원소를 가짐
deque<DataType> dq(n, x) //x값으로 초기화된 n개의 원소를 가짐
deque<DataType> dq(dq2) //dq2 컨테이너 복사본
//반복자
deque<DataType>::iteratir it;
it = dq.begin(); //첫 원소를 가리키는 반복자
it = dq.end(); //끝을 표식하는 반복자
it = dq.rbegin(); //역 순차열의 첫 원소를 가리키는 반복자
it = dq.rend(); //역 순차열의 끝을 표식하는 반복자
데큐의 함수
deque<DataType> dq;
dq.assign(n,x); //x값으로 n개의 원소를 할당
dq.at(i); //i번째 원소를 참조
dq.front(); //첫 번째 원소를 참조
dq.back(); //마지막 원소를 참조
dq.clear(); //모든 원소를 제거
dq.empty(); //비어있는지 조사 불
dq.erase(p); //p가 가리키는 원소를 제거
dq.erase(b,e); //b~e의 모든 원소를 제거
dq.insert(p,x); //p가 가리키는 위치에 x값을 삽입
dq.max_size(); //담을 수 있는 최대 원소의 개수
dq.pop_back(); //마지막 원소 제거
dq.pop_front(); //첫 원소를 제거
dq.push_back(); //끝에 원소 추가
dq.push_front(); //앞쪽에 원소 추가
dq.resize(n); //크기를 n으로 변경하고 확장된 공간의 값을 기본값으로 초기화
dq.resize(n,x); //크기를 n으로 변경하고 확장된 공간의 값을 x값으로 초기화
dq.size(); //원소의 개수
dq.swap(dq2); //dq2와 스왑
양방향으로 입출력이 가능하다보니 벡터와는 다르게 pop_front, push_front와 같은 앞에서 추가/제거하는 함수가 있다.
리스트 (List)
#include <list>
//...
list<DataType> l;
▹ 양방향 반복자를 제공히여 이전이나 다음 요소를 얻을 수 있지만, 특정 요소를 접근하기 위해서는 원하는 위치의 참조반복자를 가지고 있어야한다.
▹ 유연성이 떨어진대신 특정 작업에 대한 높은 성능의 편의를 가진다.
▹ 모든 요소에 대한 순차적 탐색은 벡터보다 느리다.
▹ 중간에서 다른 요소를 추가/제거 하더라도 인접한 다른 요소들을 수정할 필요가 없어 알고리즘 구현하는데 상당한 이점이 있지만 거의 대부분의 작업이 메모리 할당이 필요해 성능이 떨어질 수 있다.
리스트 생성자와 반복자
#include <list>
//...
//생성자
list<DataType> l //빈 컨테이너
list<DataType> l(n) //기본 값으로 초기화된 n개의 원소를 가짐
list<DataType> l(n, x) //x값으로 초기화된 n개의 원소를 가짐
list<DataType> l{1,2,3} //1,2,3 값을 가진 3개의 원소를 가짐
list<DataType> l(l2) //l2값 복사
//박복자
list<DataType>::iterator it;
it = l.begin(); //시작 반복자 반환
it = l.end(); //마지막 반복자 반환
리스트 함수
l.push_front(x); //맨 앞에 x원소 추가
l.pop_front(); //맨 앞 원소 제거
l.push_back(x); //맨 뒤 x원소 추가
l.pop_back(); //맨 뒤 원소 제거
l.insert(it, x); //반복자가 가리키는 부분 앞에 x원소 추가
l.erase(it); //반복자가 가키리는 부분 원소 제거
l.front(); //첫번째 원소 반환
l.back(); //마지막 원소 반환
l.empty(); //비어있는지 조사 bool
l.size(); //원소들의 수 반환
데큐와 리스트 요약표
dhk | 데큐 | 리스트 |
뒤쪽에 요소 추가/제거 | O(1) | O(1) |
앞쪽에 요소 추가/제거 | O(1) | O(1) |
중간에 요소 추가/제거 | O(N) | O(1) |
메모리 할당 | 주기적으로 일반적 이용중 발생 | 삽입/제거 시 매번 |
탐색 성능 | 벡터와 비슷한 성 | 벡터보다 느림 |
메모리 접근 | 거의 가능, 몇개의 순차적 블럭으로 구성 | 불가능 |
반복자 실효 | 삽입이나 삭제 후 | 실효 X |
데큐는 게임 메세지를 보관하는 큐, 리스트는 실행되는 동안 추가/제거가 게임 내의 개체등의 사용되는 것이 좋을거 같다.
기본적으로 순서로 정리된 요소들을 이용할때는 벡터를 이용하는 것이 기본적인 속도를 보장 받을 수 있지만 앞으로 요소를 추가할때는 데큐를 탐색의 속도보다는 중간에 요소를 추가/제거를 위한 기능을 위한것이라면 리스트를 사용하는 것이 좋을것 같다.
'Game Programming > 게임 프로그래밍 C++' 카테고리의 다른 글
[C++] 해시 (Hash) (0) | 2022.09.20 |
---|---|
[C++] 연관 컨테이너, 집합과 맵 (0) | 2022.09.19 |
[C++] 순차 컨테이너와 벡터 (0) | 2022.09.16 |
[C++] STL (0) | 2022.09.16 |
[C++] 메모리 할당 (0) | 2022.09.12 |