std :: forward_list - 끝에 요소를 삽입하는 방법

Question

forward_list는 (표준 목록 컨테이너와 달리) 단일 링크 된 목록입니다. list에는 앞뒤 모두를 삽입하는 함수가 있지만 forward_list에는 요소를 뒤에 삽입하는 함수가 없습니다 (push_back과 같은 것). 목록 뒤쪽에 요소를 삽입 할 수없는 이유는 무엇입니까?

Answer 1

단일 링크 된 목록과 비교할 때 forward_list에 오버 헤드가 없어야한다는 의도적 인 디자인 결정입니다. 이것은 C++ 11 표준 (23.3.4.1)에 기록됩니다 :

참고 : 그것은 forward_list이 단독 목록 연결된 손으로 쓴 C 스타일의 제로 공간이나 시간의 오버 헤드 상대가 있다는 것입니다. 이 목표와 충돌하는 기능은 생략되었습니다.

목록 끝까지 포인터를 유지하면 포인터의 공간 오버 헤드와 시간 오버 헤드 (요소가 삽입되거나 목록의 끝에 지워질 때 포인터 업데이트)가 추가됩니다.

Answer 2

나는이 데이터 구조의 정의이기 때문에
을 말하기에 더 좋은 방법이 없습니다. push_back과 같이 다른 데이터 구조를 사용해야합니다.

== 편집 == 내가 조금 자세히 설명하려고합니다 :
그것은 당신이 마지막 요소 push_back에 반복자가있는 경우 O 것은 사실이다 (1).
그러나 마지막 요소에 반복기를 유지하면 erase과 같은 다른 연산에서 오버 헤드가 발생할 수 있습니다.