STL 리스트, list 사용법 [C++]

 

나는 벡터를 가장 많이 쓰지만...그래도

알아둬야할 것들은 알아둬야지

 

항상 자료구조를 배울 땐 중요한 것이 있다.

CRUD, 삽입, 수정, 접근, 삭제

Create, Read, Update, Delete

이다.

 

우선 list란

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

 

시퀀스형 컨테이너 구조로

삽입과 삭제에 O(1)복잡도를 가지며

iterator는 bidirectional이란다.

 

property로는

Sequence

Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence.

Doubly-linked

listEach element keeps information on how to locate the next and the previous elements, allowing constant time insert and erase operations before or after a specific element (even of entire ranges), but no direct random access.

Allocator-aware

The container uses an allocator object to dynamically handle its storage needs.

 

주요 함수로는

 

iterator(반복자)

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

 

Insert & Delete & Update

• push_front(element): 리스트 제일 앞에 원소 추가
• pop_front(): 리스트 제일 앞에 원소 삭제
• push_back(element): 리스트 제일 뒤에 원소 추가
• pop_back(): 리스트 제일 뒤에 원소 삭제
• insert(iterator, element): iterator가 가리키는 부분에 원소를 추가 -> 기존의 원소는 뒤로 밀림.
• erase(iterator): iterator가 가리키는 부분에 원소를 삭제 -> 형태 2가지임 (범위 또는 위치)

 

vector랑 다르다면 앞에 원소가 추가,삭제가 가능하다는거??

 

Read

• *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;

}

 

 

와 벡터보다 좋아보이는데 왜 리스트 안써???라고 생각할 수 있겠다.

아니 삽입, 삭제가 O(1)인데 갓이 아닌가???

 

 

다만 구현 방식이 2개가 다르다.

 

 우선 메모리 할당을 다르게 하는데

vector는 미리 일정크기의 메모리를 할당해 놓고 그 이상의 값들이 추가되면 새로운 더 큰 메모리를 할당한다.

list는 값을 넣을때마다 메모리를 할당하게 된다.

 메모리 사용량도 다르다.

vector의 경우 연속적인 주소에 할당 되므로 추가적인 linked list처럼 next의 주소등 다른 변수들을 가지고 있을 필요가 없다. 따라서 vector가 list보다 적은 메모리를 사용한다.

 

비슷해보이지만 내가 무엇에 이용할 것인가 차이를 두면 되겠다.

 

맨뒤에서만 추가 삭제가 일어나는 경우는 vector가 빠르며 메모리도 적게 먹는다.

즉, 순서와 상관없이 또는 순차적으로 추가,삭제가 일어난다면 vector가 유리하다.

반대로

순서가 중요하여 리스트의 중간위치에 값이 추가, 삭제가 되는 경우 list를 사용하는 것이 좋다.

 

벡터는 중간에 추가,삭제가 되면 뒤에 것들을 밀거나 당겨오는 작업 O(n)이 필요하기 때문이다.

 

 

http://www.cplusplus.com/reference/list/list/