[C++] list 자료형 사용하기 - Quick Note

** 주의

PS를 할 때 C++에서 list 자료형은 인덱싱을 할 수 없다는 치명적인 결함 때문에 거의 쓰이지 않습니다.

이 글에서는 list 자료형을 사용할 수 있는 방법을 소개했지만, PS를 할 때는 다른 라이브러리를 사용하는 것을 추천드립니다.

1. 개요

알고리즘을 풀 때 만약 요소를 순서대로 조회하면서 인덱싱을 하려면

std::vector 라이브러리나 std::deque, std::map (포인터로 iterator 생성가능) 등의 자료형을 사용할 것이다.

 

하지만 만약 시퀀스 중간에서 삽입, 삭제가 일어나야 할 경우, 위에 나온 자료형 모두 사용하기가 애매해진다. (map은 확인 필요)

- 특히, std::vector는 push_back, pop_back 등의 메소드는 amortized O(1)로 O(n)이 나올 상황을 방지할 수 없고, 무엇보다 erase() 메소드는 O(n)의 시간복잡도를 가진다.

 

그래서 인덱싱 및 중간에서의 삽입, 삭제를 O(1)만에 하기 위해서는 list 자료형이 그 무엇보다 간절해진다.

이 글에서는 빠르게 std::list의 사용법, 시간복잡도를 알아보겠다.

 

2. 사용법

// 예제코드
// Test Source.
#include <list>
using namespace std;

int main() {
	list<int> lst;
	
	return 0;
}

다음과 같이 코드를 짜면 list 자료형을 가지는 lst가 생성된다.

이때 list에서 사용할 수 있는 메소드는 다음 블로그에 잘 정리되어 있으니 참고하기 바란다.

https://losskatsu.github.io/programming/c-stl-list/

[C언어] C++ STL 리스트(list) 사용법 정리

 

3. 인덱싱

하지만 std::list 라이브러리의 가장 큰 문제가 아직 남아있다.

.at()메소드나 인덱싱이 되지 않아 어떤 한 요소에 바로 접근할 수 없는 것이다.

 

하지만 다음 블로그의 내용을 참고하면 이를 해결할 수 있다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cksdn788&logNo=220448923269 

[Grind Away] STL list 에서 index로 값 접근하기

advance()메소드를 사용하는 것인데 예제 코드는 다음과 같다.

 

// Test Source.
#include <iostream>
#include <list>
using namespace std;

int main() {	
	list<int> lst;
	list<int>::iterator itr = lst.begin();
	
	for(int i = 0; i < 5; i++)
		lst.push_back(i);
	// test output
	for (itr = lst.begin(); itr != lst.end(); itr++)
		cout << *itr << " ";
	// itr initalize
	itr = lst.begin();
    // itr에 다음 요소의 주소를 할당 (뒤의 숫자만큼 인덱스 증가)
	advance(itr, 1);
	cout << *itr;		

	return 0;
}

- advande(std::list<자료형>::iterator itr, int increaseIdx)

- 뒤의 숫자만큼 다음 인덱스로 가며, 배열의 끝 +1 번지에 도착하는 건 괜찮지만, 그 주소에서 역참조를 해 값을 출력, 연산하려고 하면 오류가 나니 조심하자.

 

- 이를 이용하면 인덱싱도 가능해진다. (itr = begin()으로 초기화해줘야 함)

무엇보다 advance는 itr에 주소를 할당시켜 주므로 erase()메소드 등을 이용하기 오히려 편리하다.

- 주소를 증가시킨다는 것은 이런  뜻이다.

- i로 실수로 할당하면 포인터가 배열을 벗어난 주소를 가리키게 되니 주의하자.

 

+)

- 이런 식으로 미리 초기화를 해주면 인덱싱하는것 처럼 쓸 수 있으니 참고하자.