template<
class Ty,
class Allocator = std::allocator<Ty>
> class forward_list;
forward_list는 단일 연결리스트를 구현한 컨테이너이다. <forward_lsit> 헤더에 구현되어 있다. 삽입/삭제를 O(1)f로 빠르게 할 수 있지만, 특정 원소에 접근하기 위해서는 O(n)이라는 시간이 걸릴 수 있다.
1. 사용
생성
다양한 방법을 이용해 생성 가능하다. 빈 컨테이너를 생성하거나, 미리 요소가 추가된 컨테이너를 생성할 수 있다. 각 생성자들은 Allocator를 추가적으로 받을 수 있다.
- 기본 생성자
- size를 전달하는 생성자
- initializer_list를 전달하는 생성자
- 시작과 끝의 이터레이터를 전달하는 생성자
- 복사 생성자
- 이동 생성자
// 1. 기본 생성자
// 아무것도 할당되지 않은 상태로 초기화.
forward_list<int> list1;
// 2. size를 전달 받는 생성자.
// size만큼의 기본 값을 갖는 node를 리스트에 추가함.
forward_list<int> list(5); // 0 0 0 0 0
// 3. size와 초기화 값 v을 받는 생성자
// size만큼의 v값을 갖는 node를 리스트에 추가함.
forward_list<int> list3(5, 1); // 1 1 1 1 1
// 4. initializer_list
forward_list<int> list4 = { 1,2,3,4,5 }; // 1 2 3 4 5
forward_list<int> list4_2{ 1,2,3,4,5 };
forward_list<int> list4_3({ 1,2,3,4,5 });
// 5. iterator
forward_list<int> list5(list4.begin(), list4.end()); // 1 2 3 4 5;
// 6. copy
forward_list<int> list6(list4); // 1 2 3 4 5
// 7. move
forward_list<int> list7(move(list6)); // 1 2 3 4 5
접근
front()라는 단 하나의 접근 메서드를 제공한다. 첫 번째 요소의 레퍼런스를 얻을 수 있다. node가 아니라 요소 자체의 레퍼런스기 때문에 반환 값을 사용해서 다음 요소를 얻을 수 없다. 다음 요소를 얻기 위해서는 이터레이터를 사용해야 한다.
forward_list<int> list{ 1,2,3,4,5 };
int v = list.front(); // 1
이터레이터
역참조 관련 연산 외의 ++ 연산만을 지원한다. 정수를 더하거나, 뺄 수 없다. 이터레이터 끼리 뺄 수 없다. --역시 사용이 불가능한데, 리스트 자체가 단방향이기 때문에 이터레이터 역시 단방향만을 가리킬 수 있다.
forward_list<int> list{ 1,2,3,4,5 };
auto iter = list.begin();
iter++; // 2
//iter += 2; // error
iter = next(iter, 2); // 4
//iter--; // error
//auto dist = list.end() - iter; // error
auto dist = distance(iter, list.end()); // 2
용량
삽입된 요소의 개수를 확인하는 메서드가 존재하지 않는다. 컨테이너가 비어있는지 확인할 수 있는 empty()와 총 삽입 가능한 크기를 알려주는 max_size()만 존재한다.
list.empty(); // false
list.max_size(); // 가용 가능한 메모리 총량
수정
삽입과 삭제 연산에 _after가 붙는데, 이는 단일 연결리스트가 다음 요소만 가리킨다는 특징에 기인한다. 현재 요소의 위치에 새로운 요소를 추가하거나, 삭제하려면 이전 원소의 next 값을 수정해야하는데, 현재 요소에서 이전 요소에 접근할 방법이 없다. 따라서, 다음 위치에 추가하거나 제거하는 연산을 수행하고, 이를 강조하기 위해 _after라는 키워드를 붙인 것으로 보인다. insert_after(), emplace_after()를 통하 삽입 연산을 수행하고 erase_after()로 제거한다.
forward_list<int> list{ 1,2,3,4,5 };
auto iter = list.begin();
iter = next(iter, 2); // 3
iter = list.insert_after(iter, 11); // 1 2 3 11 4 5
iter = list.insert_after(iter, 12); // 1 2 3 11 12 4 5
iter = next(iter, 2); // 5
iter = list.emplace_after(iter, 6); // 1 2 3 11 12 4 5 6
iter = list.emplace_after(iter, 7); // 1 2 3 11 12 4 5 6 7
iter = next(list.begin(), 2); // 3
// erase_after가 다음 iter이 12를 가리키기 떄문에 반환 값을 얻오면 안됨.
list.erase_after(iter); // 1 2 3 12 4 5 6 7
list.erase_after(iter); // 1 2 3 4 5 6 7
단, 첫 번째 요소에 대해서는 list 내부에서 접근을 위해 기억하고 있기 때문에, 삽입, 삭제가 가능한데, 이를 위해서 emplace_front()와 push_front(), pop_front()를 이용할 수 있다.
list.push_front(0); // 0 1 2 3 4 5 6 7
list.emplace_front(-1); // -1 0 1 2 3 4 5 6 7
list.pop_front(); // 0 1 2 3 4 5 6 7
clear()를 통해 컨테이너를 비우거나, resize()를 통해서 기존 node를 잘라버리거나, 요소의 끝에 일정한 노드를 붙일 수 있다.
list.resize(2); // 0 1
list.resize(5); // 0 1 0 0 0
list.resize(10, 4); // 0 1 0 0 0 4 4 4 4 4
list.clear(); // empty
기타
리스트에서 사용할 수 있는 독특한 연산이나, 이터레이터를 만족하지 못해서 사용할 수 없던 <algorithm>의 함수들을 내부 메서드로 지원한다.
remove(e): e와 같은 요소들을 제거하고, 제거된 수를 반환한다.remove_if(f): 요소가 함수 f를 만족하면 제거하고, 제거된 수를 반환한다.reverse(): 리스트의 순서를 뒤집는다.unique(): 연속적으로 같은 값이 반복되어 있다면 하나를 제외하고 제거한다.sort(): 리스트를 정렬한다.merge(): 정렬된 두 리스트를 순서를 유지하며 합친다.splice_after(): 다른 리스트를 가져와 이동시킨다.
forward_list<int> list{ 3,3,9,2,3,4,1,1,7,8 };
auto n = list.remove(1); // 3 3 9 2 3 4 7 8
n; // 2
// 5보다 크면 삭제한다. // 3 3 2 3 4
n = list.remove_if([](int v) { return v > 5; });
n; // 3
list.reverse(); // 4 3 2 3 3
n = list.unique(); // 4 3 2 3
n; // 1
list.push_front(5); // 5 4 3 2 3
list.sort(); // 2 3 3 4 5
forward_list<int> list2{ 0,1,10,11,12 };
// list2는 이동되어 empty가 된다.
list.merge(list2); // 0 1 2 3 3 4 5 10 11 12
list.resize(4); // 0 1 2 3
list2.assign({ 7,8,9 }); // 7 8 9
// list2는 이동된다.
list.splice_after(list.begin(), list2); // 0 7 8 9 1 2 3