[C++] list 컨테이너 사용법

Doorbals·2023년 1월 30일

cpp

CPP

목록 보기

15/16

1. C++의 list 컨테이너

: STL에 지정된 list는 Double Linked List(양방향 연결 리스트)로 구현되어 있다.

2. Vector와 List의 차이점

1) Vector

연속적 메모리
미래에 들어갈 요소를 위해 메모리 공간을 선할당
동적으로 확장 및 축소가 가능한 동적 배열로 구현

장점

개별 원소들에 접근 가능
랜덤으로 원소 순회 가능
개별 원소에 대한 접근 속도가 빠르다.
원소를 마지막에 삽입하는 것이 빠르다.

단점

컨테이너 끝이 아닌 곳에 삽입/제거 시 성능 현저히 하락
동적이라 확장 및 축소가 편하나 확장 시 비용이 크다.

2) List

비연속적 메모리
메모리를 선할당 하지 않는다.
근본적인 배열이 존재하지 X, 따라서 원소의 배열이 필요하면 새로운 배열을 만들어 원소들을 추가해야 한다.

장점

컨테이너 어느 위치에서라도 삽입/제거 속도가 빠르다.
원소들의 컨테이너 내 이동이 빠르다.

단점

원소의 인덱스로 직접 접근이 불가능
특정 원소에 접근하려면 처음이나 끝부터 선형 탐색 필요
컨테이너 내 순회가 forward/reverse만 가능하여 느림
원소 간 상호 연결 정보(prev, next)를 위해 추가적 메모리 비용 발생

❗결론

중간 부분에서의 삽입 및 삭제가 잦은 경우
: vector는 원소를 밀어내야하지만 list는 노드만 연결하면 되므로 list가 시간복잡도의 우위를 가진다.
특정 값을 탐색하고자 하는 경우
: 특정 원소에 직접 접근 가능한 vector가 탐색적인 측면에서 우위를 가진다.

3. C++ STL list 사용법

1. 선언

list<type> list1;		// type 자료형을 담는 리스트 선언
list<type> list1(num);	// num개의 원소를 갖는 리스트 선언 (각 원소는 0으로 초기화 됨)
list<type> list1(num, value)	// num개의 원소를 갖는 리스트 선언, 각 원소는 value로 초기화
list<type> list1{1, 2, 3, 4}	// 특정 공간의 개수, 특정 값 지정해 리스트 초기화

2. 삽입

list1.push_front(value)		// 리스트 맨 앞에 value값 갖는 원소 추가
list1.push_back(value)		// 리스트 맨 뒤에 value값 갖는 원소 추가
insert(iterator, value)		// iterator가 가리키는 부분 앞에 value값 갖는 원소 추가

3. 삭제

list1.pop_front()		// 리스트 맨 앞의 원소 삭제
list1.pop_back()		// 리스트 맨 뒤의 원소 삭제
erase(iterator)			// iterator가 가리키는 부분 원소 삭제

4. 조회

*iterator		// iterator가 가리키는 원소에 접근
list1.front()	// 리스트 맨 앞의 원소 반환
list1.back()	// 리스트 맨 뒤의 원소 반환

5. 기타

list1.empty()	// 리스트가 비어있는지 여부 반환 (비어있으면 1, 아니면 0 반환)
list1.size() 	// 리스트의 사이즈 반환(원소 개수)

4. list iterator의 위치 옮기기

list의 경우 iterator에 + 나 - 등 의 산술 연산이 불가능하다.
: 산술 연산이 가능한 iterator는 Random Access Iterator(임의 접근 반복자)인데, 이에 해당하는 컨테이너는 vector와 deque밖에 없기 때문이다. 때문에 list의 iterator를 이동시키기 위해서는 다른 방법을 사용해야 한다.

advance() 함수

: advance() 함수는 주어진 값만큼 iterator를 이동시키는 역할을 하는 함수이다.
해당 함수를 사용하면 임의 접근이 불가능한 list에서 임의 접근과 같은 효과를 낼 수 있다.

list<int> list1{1, 2, 3};
auto it = list1.begin();	// list1의 맨 앞 부분을 가리킴.
advance(it, 1);				// list1의 맨 앞에서 한 칸 오른쪽으로 이동
cout << *it << endl;

출력 : 2