1.5 std::forward_list

array와 vector 같은 연속된 자료구조에서 데이터 중간에 원소를 삽입하거나 삭제하는 작업이 매우 비효율적이다.

-> 연결 리스트 사용

 

std::forward_list

 

원소 삽입

push_front(): 연결 리스트 맨 앞에 새로운 원소 삽입

insert_after(): 특정 원소 뒤에 새로운 원소 삽입

시간복잡도 O(1)

 

std::forward_list<int> fwd = {1, 2, 3};
fwd.push_front(4);	// {4, 1, 2, 3}
auto it = fwd.begin();
fwd.insert_after(it, 5); // {4, 5, 1, 2, 3}

emplace_front()와 emplace_after()함수 제공. 삽입 함수와 같은 기능을 수행하지만 추가적인 복사 또는 이동을 하지 않기 때문에 더 효율적이다.

 

원소 삭제

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

erase_after()

1. erase_after(iterator): iterator 바로 다음 위치의 원소 삭제

2. erase_after(iterator1, iterator2): iterator1 바로 다음 위치 원소부터 iterator2 까지 삭제

시간복잡도: 삭제할 원소 개수의 선형함수 형태

std::forward_list<int> fwd = {0, 1, 2, 3, 4};
fwd.pop_front();	// {1, 2, 3, 4};
fwd.erase_after(fw.begin());	// {1, 3, 4};
fwd.erase_after(fw.begin(), fwd.end());	// {1}

 

기타 멤버함수

remove(삭제할_원소_값): 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 인자 값과 일치하는 모든 원소를 찾아 삭제한다. 등호 연산이 지원되지 않는 데이터 타입이라면 컴파일 에러가 발생한다.

remove_if(조건자_함수(데이터_원소_값)): 조건자(predicate)함수가 true를 반환하는 모든 데이터 원소를 리스트에서 삭제한다. 조건자 함수 대신 람다 표현식(lambda expression)을 사용할 수 있다.

시간복잡도 O(n)

 

sort()

1. sort(): <연산자 기반 정렬. <연산자 정의 필요. default 비교자(comparator): std::less<value_type>

2. sort(비교자): 비교자 - std::greater<type>() 등이 존재.

3. 이항조건자(binary predicate)를 지정하여 특정 기준으로 원소를 정렬할 수 있다.

시간복잡도 O(nlogn)

[참고] std::forward_list에서 사용하는 iterator는 std::array, std::vector의 iterator와 다르다.

 

reverse(): 저장된 원소 역순으로 변경. 시간복잡도 O(n) 

unique()

1. unique(): 원소 타입의 등호 연산자를 사용하여 원소 값이 같은지 판단. 인접한 원소1과 원소2를 비교하여 같다면 원소2를 삭제한다. 따라서 중복값을 하나만 남기고 다 삭제하려면 리스트를 정렬한 후 unique()함수를 사용해야 한다.

2. unique(이항조건자(원소타입 인자1, 원소타입 인자2)): 이항조건자는 bool값을 반환한다. 인자1, 인자2를 특정 조건에 대해 비교하고 true면 인자2 삭제 // 다시 확인할 것.

 

std::forward_list<int> fwd = {4, 2, 3, 1};
fwd.reverse();	//{1, 3, 2, 4}

std::forward_list<int> fwd = {1, 4, 2, 2, 1, 3, 1};
fwd.unique();	//{1, 4, 2, 1, 3, 1}
fwd = {1, 4, 2, 2, 1, 3, 1};
fwd.sort();	//{1, 1, 1, 2, 2, 3, 4}
fwd.unique(); //{1, 2, 3, 4};
fwd.unique([](int a, int b) { return (b-a) < 2; });
//{1, 3};