std::forward_list

배열이나 벡터 같은 연속된 자료 구조에서 데이터 중간에 자료를 추가하거나 삭제할 때 작업이 매우 비효율적이다.

연결 리스트와 같은 형태의 자료 구조 등장

자료 구조 중간에 삽입 또는 삭제 작업을 필요

연결 리스트를 구성하려면 포인터, new, delete 연산자를 이용하여 메모리 할당하고 해제 필요

 

std::forward_list는 기본적인 연결 리스트의 성능을 유지하면서 추가적인 기능 제공

성능 유지를 위해 std::forward_list는 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능 X

front() : 맨 처음 원소에 접근하는 함수

back() : X 존재 X

push_front()  : 리스트 맨 앞에 새로운 원소를 삽입. 시간 복잡도 O(1), 매개변수 ( 넣을 원소 )

insert_after() : 특정 위치에 원소 삽입. 시간 복잡도 O(1), 매개변수 ( iter(위치), 넣을 원소 )

emplace_front() : 삽입 함수와 같은 기능을 수행 / 추가적인 복사 또는 이동 X -> 효율적

emplace_after() : 삽입 함수와 같은 기능을 수행 / 추가적인 복사 또는 이동 X -> 효율적

pop_front() : 리스트의 맨 처음 원소 제거. 시간 복잡도 O(1)

erase_after() : 두 가지 형태로 제공, 하나는 특정 원소를 가리키는 반복자를 인자로 받아 다음 위치의 원소 삭제

                   일련의 원소를 제거할 때에도 erase_after() 사용, 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제                     할 범위 끝 원소를 가리키는 반복자를 인자로 받음, 일련의 원소를 삭제하는 시간 복잡도는 삭제할 원소                     의 선형 함수 형태 ( 각각의 노드는 전체 메모리의 임의 위치에 산재, 각각의 노드에 사용된 메모리를 개                     별적으로 해제해야만 함)

remove() : 삭제할 원소 값 하나를 매개변수, 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전달된 값과 일치하                는 모든 원소를 찾아 삭제, 저장된 데이터 타입에서 등호 연산이 지원되지 않으면 remove() 사용 X 

remove_if() :  데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자 함수를 인자로 조건자가 true를 반환하는                    모든 데이터 원소를 리스트에서 삭제