[게임 프로그래머 입문 올인원] STL Container : list와 iterator(67강)

A. list

1. list의 기본기 (복습)

vector와 비슷하다

 

a. size와 capacity

• size : 리스트의 노드 개수 
• capacity : 존재하지 않음

 

이게 데이터 10개를 할당

이렇게 생성할 수도 있음

 

b. 데이터 삽입 / 추출의 시간복잡도

🧡 시간복잡도

- 시작 O(1)

- 중간 O(1) << 조건부 (위치를 기억하고 있으면 빠르다)

- 끝 O(1)

- front  O(1)

- back  O(1)

- push_front  O(1)

- push_back  O(1)

 

 

c. 데이터 삽입시 위치 정하기

 

📘 문법

list.insert();

ex) 
li.insert(li.end(), 1);
li.insert(li.end(), 2);
//insert함수는 iterator를 반환
li<int>::iterator it = li.insert(li.end(), 3);
li.insert(li.end(), 3);
li.insert(li.end(), 4);

//그걸 저장해 지우거나 삽입할 때 사용가능
li.insert(it,100);
li.erase(it);

 

d. 임의 접근 

위에서 설명했듯 capacity와 임의접근은 제공되지 않음 

 

e. 순회

1) 리스트의 처음부터 끝까지 리스트를 순회하고 추출하는 코드

 

기본 코드

 

2) 끝까지 순회했는지 체크하는 코드

 

 

3) 값을 제거하면서 순회하는 코드

 

 

f.속도

노드를 타고 가기때문에 벡터보다 속도가 느림

 

 

---

B. list의 iterator

벡터보단 구현 방식이 많음 (양방향)

 

1. iterator 구현하기

a. 클래스로 반복자 생성하기

 

b. 특성 구현하기

 

• 생성자 : 노드 넣어주기
• 노드를 지정 : 노드를 저장시키기
• ++it (전위형) : 다음 노드 지정하기
• it++ (후위형) : 원래 위치를 기억해주고  다음 노드를 지정하기

 

 

• * : 데이터 꺼내오기
• == : 노드끼리 비교하기

 

c. 리스트 코드 수정하기 

 

iterator를 가지고 있고

시작과 끝 노드를 내보내는 코드를 추가

 

d. list의 반복자 사용하기

 

여기서 end()함수는 리스트의 마지막 데이터가 아니라

그 데이터의 다음 (?) 가상의 무언가를 가리킴

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -