C++ STL List 사용법과 예제

C++에서 list 사용법을 간단하게 알아보자

장점 : 삽입삭제 잦을 시 사용하기 좋다.

Vector와 Dequeue와 번갈아 사용됨

 

배경지식

C++ STL 컨테이너 - 벡터 (std::vector)

C++ STL 에서 컨테이너는 크게 두 가지 종류가 있습니다. 먼저 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container) 와 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있습니다.

먼저 시퀀스 컨테이너의 경우 vector, list, deque 이렇게 3 개가 정의되어 있습니다.

먼저 벡터(vector) 의 경우, 쉽게 생각하면 가변길이 배열이라 보시면 됩니다 (템플릿 강의에서 Vector 를 제작하신 것을 기억 하시나요?) 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고, 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있습니다.

리스트 (list)

리스트(list) 의 경우 양방향 연결 구조를 가진 자료형이라 볼 수 있습니다.!

따라서 vector 와는 달리 임의의 위치에 있는 원소에 접근을 바로 할 수 없습니다. list 컨테이너 자체에서는 시작 원소와 마지막 원소의 위치만을 기억하기 때문에, 임의의 위치에 있는 원소에 접근하기 위해서는 하나씩 링크를 따라가야 합니다.

그래서 리스트에는 아예 [] 나 at 함수가 아예 정의되어 있지 않습니다.

물론 리스트의 장점이 없는 것은 아닙니다. vector 의 경우 맨 뒤를 제외하고는 임의의 위치에 원소를 추가하거나 제거하는 작업이 O(n)O(n) 이였지만 리스트의 경우 O(1)O(1) 으로 매우 빠르게 수행될 수 있습니다. 왜냐하면 원하는 위치 앞과 뒤에 있는 링크값만 바꿔주면 되기 때문입니다.

 C/C++ 확대 축소

 

한 가지 재미있는점은 리스트의 반복자의 경우 다음과 같은 연산밖에 수행할 수 없습니다.

itr + 5 // 불가능!

와 같이 임의의 위치에 있는 원소를 가리킬 수 없다는 것입니다. 반복자는 오직 한 칸 씩 밖에 움직일 수 없습니다.

이와 같은 이유는 list 의 구조를 생각해보면 알 수 있습니다. 앞서 말했듯이 리스트는 왼쪽 혹은 오른쪽을 가리키고 있는 원소들의 모임으로 이루어져 있기 때문에, 한 번에 한 칸 씩 밖에 이동할 수 없습니다. 즉, 메모리 상에서 원소들이 연속적으로 존재하지 않을 수 있다는 뜻입니다. 반면에 벡터의 경우 메모리 상에서 연속적으로 존재하기 때문에 쉽게 임의의 위치에 있는 원소를 참조할 수 있습니다.

이렇게 리스트 에서 정의되는 반복자의 타입을 보면 BidirectionalIterator 타입임을 알 수 있습니다. 이름에서도 알 수 있듯이 양방향으로 이동할 수 있되, 한 칸 씩 밖에 이동할 수 없습니다. 반면에 벡터에서 정의되는 반복자의 타입은 RandomAccessIterator 타입 입니다.

즉, 임의의 위치에 접근할 수 있는 반복자 입니다 (참고로 RandomAccessIterator 는 BidirectionalIterator 를 상속받고 있습니다)

 

리스트 기본 함수

iterator(반복자)

• begin() : beginning iterator를 반환
• end() : end iterator를 반환

추가 및 삭제

• push_front(element) : 리스트 제일 앞에 원소 추가
• pop_front() : 리스트 제일 앞에 원소 삭제
• push_back(element) : 리스트 제일 뒤에 원소 추가
• pop_back() : 리스트 제일 뒤에 원소 삭제
• insert(iterator, element) : iterator가 가리키는 부분 “앞”에 원소를 추가
• erase(iterator) : iterator가 가리키는 부분에 원소를 삭제

조회

• *iterator : iterator가 가리키는 원소에 접근
• front() : 첫번째 원소를 반환
• back() : 마지막 원소를 반환

기타

• empty() : 리스트가 비어있으면 true 아니면 false를 반환
• size() : 리스트 원소들의 수를 반환

#include <iostream>
#include <list>

using namespace std;

int main(){

	list<int> l;


	// push_back
	l.push_back(5);
	l.push_back(6);
	l.push_back(7);
	l.push_back(8);
	l.push_back(9);
	l.push_back(10);


	// pop_back
	l.pop_back();


	// push_front
	l.push_front(4);
	l.push_front(3);
	l.push_front(1);
	l.push_front(0);


	// pop_front
	l.pop_front();


	// back and front
	cout << "list front value : " << l.front() << '\n';
	cout << "list end value : " << l.back() << '\n';


	// size
	cout << "list size : " << l.size() << '\n';


	// empty
	cout << "Is it empty? : " << (l.empty() ? "Yes" : "No") << '\n';


	// iterator
	list<int>::iterator begin_iter = l.begin(); // auto begin_iter = l.begin()도 가능
	list<int>::iterator end_iter = l.end(); // auto end_iter = l.end()도 가능


	// insert
	begin_iter++; // 2번째를 가리키는 iterator
	l.insert(begin_iter, 2);


	// erase
	end_iter--; // 마지막 원소를 가리키는 iterator
	l.erase(end_iter);


	// *iterator : 원소 접근
	cout << "list "<< distance(l.begin(), begin_iter)+ 1 << " element : " << *begin_iter << '\n';

	return 0;

}