[Algorithm] STL 순방향 리스트 (Forward list)

순방향 리스트

C++11에서 도입된 컨테이너로 자신의 요소를 단방향 연결리스트로 관리한다.

 

사진 출처 : http://hyeonstorage.tistory.com/259

 

순방향 연결리스트를 사용하기 위해서는 <forward_list>를 인클루드 해야한다.

namespace std 안에 정의되어 있다.

 

기능 

순방향 리스트는 개념적으로 되돌아가지 못하는 리스트와 같다.

따라서 리스트가 제공하지 않는 기능은 제공되지 않는다.

리스트보다 좋은 점은 메모리를 덜 사용하고 실행 시간이 조금 더 빠르다

 

되돌아가지 못하기 때문에 리스트에는 없는 제약 조건이 몇 가지 있다.

1. 양방향이 아닌 순방향 반복자를 제공한다.

따라서 역방향 연산은 제공되지 않는다.

2. size() 함수를 제공하지 않는다.

공간이나 시간 부하를 만드는 특성을 생략했기 때문이다.

3. 순방향 리스트의 앵커는 마지막 요소를 가리키는 포인터를 갖지 않는다.

따라서 마지막 요소를 다루는 함수를 제공하지 않는다.

4. 특정 위치에 요소를 삽입/삭제하는 멤버 함수에 대해 특수한 함수가 제공된다.

이런 차이점 때문에 멤버함수 이름 뒤에 _after가 붙는다.

 

size() 함수를 제공하지 않기 때문에 크기를 알고자한다면 외부에서 알아내거나 list를 사용한다.

 

이런 차이점을 제외하고는 리스트와 같게 동작한다.

 

연산 

생성자와 소멸자

연산	설명
forward_list<Elem> c	기본 생성자, 빈 순방향 연결리스트 생성
forward_list<Elem> c(c2)	복사 생성자. 같은 자료형을 갖는 순방향 리스트 c2를 복사한 순방향 리스트 생성  모든 요소를 복사
forward_list<Elem> c = c2	복사 생성자. 같은 자료형을 갖는 순방향 리스트 c2를 복사한 순방향 리스트 생성  모든 요소를 복사
forward_list<Elem> c(rv)	이동 생성자. rv의 내용을 갖는 새로운 순방향 리스트 생성 ( C++11 이후 지원 )
forward_list<Elem> c = rv	이동 생성자. rv의 내용을 갖는 새로운 순방향 리스트 생성 ( C++11 이후 지원 )
forward_list<Elem> c(n)	기본 생성자로 초기화된 n개의 요소를 갖는 순방향 리스트 생성
forward_list<Elem> c(n, elem)	elem으로 초기화된 n개의 요소를 갖는 순방향 리스트 생성
forward_list<Elem> c(beg, end)	범위 [beg, end) 내의 요소를 갖는 순방향 리스트 생성
forward_list<Elem> c(initlist)	초기화자 목록의 요소로 초기화된 순방향 리스트 생성 ( C++11 이후 지원 )
forward_list<Elem> c = initlist	초기화자 목록의 요소로 초기화된 순방향 리스트 생성 ( C++11 이후 지원 )
c.~forward_list()	모든 요소를 삭제하고 메모리 해제

 

 

수정하지 않는 연산

size()를 제공하지 않는 것을 제외하면 일반적인 연산을 제공한다.

연산	설명
c.empty()	컨테이너가 비었는지 여부를 알려줌
c.max_size()	최대 저장 가능한 요소의 수를 반환
c1 == c2	c1이 c2와 같은지 반환. 모든 요소에 대해 == 호출
c1 != c2	c1이 c2와 다른지 반환
c1 < c2	c1이 c2보다 작은지 반환
c1 > c2	c1이 c2보다 큰지 반환
c1 <= c2	c1이 c2보다 작거나 같은지 반환
c1 >= c2	c1이 c2보다 크거나 같은지 반환

 

순방향 리스트의 크기를 알고싶다면 distance() 함수를 사용하자.

 

 할당

연산	설명
c = c2	c2의 모든 요소를 c에 할당
c = rv	rv의 모든 요소를 c에 이동 할당 ( C++11 이후 지원 )
c = initlist	초기화자 목록 내 모든 요소를 c에 할당 ( C++11 이후 지원 )
c.assign(n, elem)	n개의 elem을 요소로 할당
c.assign(beg, end)	범위 [beg, end) 내 요소를 할당
c.assing(initlist)	초기화자 목록 initlist 내 모든 요소를 c에 할당
c1.swap(c2)	c1과 c2의 데이터를 교환
swap(c1, c2)	c1과 c2의 데이터를 교환

 

 

요소 접근

직접 접근할 수 있는 요소는 첫 번째 요소 뿐이다.

연산	설명
c.front()	첫 번째 요소 반환 ( 첫 번째 요소가 있는지 확인하지 않음 )

 

 

반복자

연산	설명
c.begin()	첫 번째 요소에 대한 순방향 반복자 반환
c.end()	마지막 요소 다음 위치에 대한 순방향 반복자 반환
c.cbegin()	첫 번째 요소에 대한 순방향 상수 반복자 반환 ( C++11 이후 지원 )
c.cend()	마지막 요소 다음 위치에 대한 순방향 상수 반복자 반환 ( C++11 이후 지원 )
c.before_begin()	첫 번째 요소 직전의 위치를 가리키는 순방향 반복자 반환
c.cbefore_begin()	첫 번째 요소 직전의 위치를 가리키는 순방향 상수 반복자 반환

 

before_begin()과 cbefore_begin()은 유효한 위치를 가리키지 않는다.

따라서 이 위치를 참조 해지하는 경우 에러가 발생한다.

 

요소 삽입/제거

연산	설명
c.push_front(elem)	elem의 복사본을 앞에 삽입
c.pop_front()	첫 번째 요소 삭제, 반환값 없음
c.insert_after(pos, elem)	반복자 위치 pos 뒤에 elem의 복사본을 삽입 후 새 요소의 위치 반환
c.insert_after(pos,n, elem)	반복자 위치 pos 뒤에 elem의 복사본을 n개 삽입 후 새 요소의 중 첫 번째 요소의 위치 반환
c.insert_after(pos,beg,end)	반복자 위치 pos 뒤에 범위 [beg,end) 내 요소의 복사본 삽입 후 새 요소 중 첫 번째 요소의 위치 반환
c.insert_after(pos, initlist)	반복자 위치 pos 뒤에 초기화자 목록의 요소의 복사본 삽입 후 새 요소 중 첫 번째 요소의 위치 반환 ( C++11 이후 지원 )
c.emplace_after(pos, args...)	반복자 위치 pos 뒤에 인자 args로 초기화된 요소의 박사본을 삽입 후 새 요소의 위치 반환 ( C++11 이후 지원 )
c.emplace_front(args...)	인자 args로 초기화된 요소의 복사본을 순방향 리스트의 맨 앞에 삽입  반환값 없음 ( C++11 이후 지원 )
c.erase_after(pos)	반복자 위치 pos 다음에 있는 요소 제거
c.erase_atfer(beg,end)	범위 [beg, end) 내의 모든 요소 제거
c.remove(val)	값이 val인 요소 모두 제거
c.remove_if(op)	op(elem)을 만족하는 모든 요소 제거
c.resize(num)	요소의 수를 num개로 바꿈, 현재 개수보다 많은 경우 기본 생성자로 초기화
c.resize(num,elem)	요소의 수를 num개로 바꿈, 현재 개수보다 많은 경우 elem으로 초기화
c.clear()	모든 요소를 제거

 

접미사 _after이 들어가는 함수들은 pos 다음 위치에 작업을 수행한다는 것을 명심하자!

 

순방향 리스트의 특별 수정 연산

연산	설명
c.unique()	연속한 요소 중 같은 값을 갖는 중복 요소 제거
c.unique(op)	연속한 요소 중 op()이 참인 중복 요소 제거
c.splice_after(pos, c2)	c2의 모든 요소를 c의 반복자 위치 pos 뒤로 이동
c.splice_after(pos,c2,c2pos)	c2의 c2pos 뒤에 있는 요소를 c의 반복자 위치 pos 뒤로 이동
c.splice_after(pos,c2,c2beg, c2end)	c2beg, c2end 내 모든 요소(양쪽 끝 제외)를 c의 반복자 위치 pos 뒤로 이동
c.sort()	모든 요소를 연산자 < 기준으로 정렬
c.sort(op)	모든 요소를 op() 기준으로 정렬
c.merge(c2)	두 컨테이너가 모드 정렬되있을 때 c2의 모든 요소를 c로 이동하고 모든 요소가 정렬된 상태를 유지
c.merge(c2,op)	두 컨테이거나 모두 op()의 기준에 따라 정렬되있을 때 c2의 모든 요소를 c로 이동하고 정렬 기준 op()의 기준으로 정렬된 상태 유지
c.reverse()	모든 요소의 순서를 뒤집음