[C++] STL - list

list

앞서 봤던 벡터와 덱이 배열 기반 시퀀스 컨테이너였다면

리스트는 노드 기반 이중 연결 리스트로 구현된 시퀀스 컨테이너이다.

 

 

따라서 벡터, 덱과 달리 임의의 위치에 있는 원소에 바로 접근할 수 없고 반복자를 통해 순차적으로 접근할 수 밖에 없다는 단점이 존재한다. 

 

※ 리스트의 반복자

리스트의 반복자의 경우 순차적인 작업밖에 수행하지 못하기 때문에 ++, -- 와 같은 연산만 수행할 수 있다.

즉, itr + 5 와 같은 연산은 불가능하다.

 

하지만 벡터와 덱에서 O(n) 이었던 임의의 위치에 원소 추가 / 제거하는 작업을 O(1)에 수행할 수 있다는 장점이 있다.

리스트의 경우 원하는 위치의 앞과 뒤에 있는 링크값만 바꾸어주면 되기 때문이다. 

 

임의의 위치 원소 접근	순차탐색만 지원	O(n)
맨 앞에 원소 추가 / 제거	push_front(), pop_front()	O(1)
맨 뒤에 원소 추가 / 제거	push_back(), pop_back()	O(1)
임의의 위치 원소 추가 / 제거	insert(), erase()	O(1)

 

리스트는 벡터와 덱과 다른 멤버 함수가 몇 가지 존재한다.

sort()	리스트에 담긴 원소를 정렬
unique()	연속적으로 중복된 값이 배치된 원소를 제거
remove()	인자로 받은 값과 같은 값의 원소를 모두 제거
remove_if()	인자의 조건식에 해당하는 원소를 모두 제거
reverse()	리스트의 원소의 순서를 역순으로 변경
list1.merge(list2)	list1에 list2를 정렬하면서 병합
list1.splice(itr, list2)	list1에서 itr가 가리키는 곳에 list2원소를 잘라 붙임

 

#include <iostream>
#include <list>
using namespace std;

int main(){
    list<int> list;
    list.push_back(5);		// 5
	list.push_front(3);		// 3 5
	list.push_back(2);		// 3 5 2
    list.push_front(4);
    list.push_front(4);	
    list.push_front(4);	    // 4 4 4 3 5 2

    list.sort();	// 리스트 정렬(오름차순)
    list.unique(); // 인접한 동일 값 제거

    for (auto i = list.begin(); i != list.end(); i++) {
		cout << *i << " ";
	} // 2 3 4 5
}