Game Programming/게임 프로그래밍 C++

[C++] 데큐와 리스트

Doanie 2022. 9. 18. 13:04

[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