[C++] 아주 기본적인 연결 리스트(std::forward_list)

C++는 C 스타일 배열에 대한 래퍼 클래스 std::array를 제공하듯이 기본적인 연결 리스트에 대한 래퍼 클래스인 std::forward_list 클래스를 제공합니다.

 

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

 

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

즉, 맨 처음 원소에 접근하는 front()함수를 제공하지만, 반대 방향의 원소로 이동하는 back()같은 함수는 제공하지 않습니다.

원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 제공합니다. 이러한 기능은 기본적인 연결 리스트의 메모리 사용량이나 성능에 영향을 주지 않습니다.

 

std::vector와 마찬가지로 std::forward_list 도 두 번째 템플릿 매개변수에 사용자 지정 할당자를 지정할 수 있습니다. 따라서 맞춤형 메모리 관리가 필요한 고급 응용 프로그램에서도 std::forward_list 를 사용할 수 있습니다.

---

std::forward_list에서 원소 삽입과 삭제

원소 삽입: 

• push_front()
• insert_after()

push_front()함수는 연결 리스트 맨 앞에 새로운 원소를 삽입합니다.

 

특정 위치에 원소를 삽입하려면 insert()가 아니라 insert_after()를 사용해야 합니다. 이는 연결 리스트에서 새로운 원소를 삽입한 후, 해당 위치 앞에 있는 원소의 next포인터를 수정해야 하기 때문입니다.

 

std::forward_list에서 반대 방향으로 이동하는 것이 허용되지 않으므로 특정 원소 뒤에 새로운 원소를 삽입한 후, 해당 원소의 next 포인터를 수정하는 것이 타당합니다.

 

std::forward_list의 삽입 함수는 리스트의 원소 크기에 영향을 받지 않기때문에, 시간 복잡도는 O(1)입니다.

 

std::forward_list<int> fwd_list = {1, 2, 3};

fwd_list.push_front(0);	// 맨 앞에 0 추가: {0, 1, 2, 3} beste

auto it = fwd_list.begin(); 

fwd_list.insert_after(it, 5);	// 맨 처음 원소 뒤에 5 추가: {0, 5, 1, 2, 3} 

fwd_list.insert_after(it, 6);	// 같은 위치에 6 추가: {0, 6, 5, 1, 2, 3}

 

 

 

std::forward_list는 std::vector의 emplace() 함수와 유사한 emplace_front()와 emplace_after() 함수도 제공합니다. 

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

 

원소 삭제:

• pop_front()
• erase_after()

pop_front() 함수는 리스트의 맨 처음 원소를 제거합니다.

 

erase_after()는 두 가지 형태로 제공됩니다.

 

하나는 특정 원소를 가리키는 반복자를 인자로 받아서 바로 다음 위치의 원소를 삭제합니다.

 

나머지 하나는, 일련의 원소를 제거할 때에도 erase_after() 함수를 사용할 수 있으며, 이 경우에는 삭제할 범위의 시작 원소 앞을 가리키는 반복자와 삭제할 범위 끝 원소를 가리키는 반복자를 인자로 받습니다.

std::forward_list<int> fwd_list = {1, 2, 3, 4, 5);

fwd_list.pop_front();	// 맨 앞 원소를 삭제:{2,3,4,5}

auto it = fwd_list.begin();

fwd_list.erase_after(it); // 맨 앞의 다음 원소를 삭제: {2,4,5}

fwd_list.erase_after(it, fwd_list.end()); //맨 앞 원소 다음부터 맨 마지막 원소까지 삭제: {2}

erase_after() 함수를 사용하여 일련의 원소를 삭제하는 시간 복잡도는 삭제할 원소 개수의 선형 함수 형태로 나타납니다.
이는 연결 리스트에서 각각의 노드는 전체 메모리의 임의 위치에 산재되어 있으며, 각각의 노드에 사용된 메모리를 개별적으로 해체해야 하기 때문입니다.

---

정렬하는 sort()멤버 함수

std::array, std::vector 등에 저장된 데이터는

범용적인 std::sort(first_iterator, last_iterator) 함수를 이용하여 원소를 정렬할 수 있습니다.

 

그러나 연결 리스트 같은 자료구조는 특정 원소에 임의 접근이 불가능하므로 std::sort()함수를 사용할 수 없습니다.

또한 std::forward_list에서 사용하는 반복자는 std::array또는 std::vector의 반복자와 다릅니다.

 

std::forward_list에서 제공하는 sort()함수는 두 가지 형태를 지원합니다.

 

1. 하나는 < 연산자를 기반으로 정렬하고,
2. 다른 하나는 매개변수로 전달된 비교자(comparator)를 사용합니다.

기본 sort()함수는 std::less<value_type>을 비교자로 사용합니다.

비교자의 경우 첫 번째 인자가 두 번째보다 작으면 true를 반환하며, 사용자 정의 타입 원소를 사용할 경우에는 < 연산자가 재정의되어 있어야 합니다.

 

이외에도 다른 기준을 이용하여 원소를 비교하고 정렬하려면 이항 조건자(binary predicate)를 지정할 수 있습니다.

 

두 가지 형태의 sort()함수 모두 선형 로그 시간 복잡도O(nlogn)을 갖습니다.

std::forward_list<int> list1 = {23,0,1,-3,34,32};

list1.sort() //{-3,0,1,23,32,34} 순서로 바뀝니다

list1.sort(std::greater<int>()) //{34,32,23,1,0,-3} 순서로 바뀝니다.

std::greater<int>는 표준으로 제공되는 비교 함수 객체이며, 

원소를 내림차순으로 정렬하기 위한 > 연산자에 대한 래퍼입니다.

---

reverse() 와 unique()

• reverse() : 저장된 원소의 순서를 역순으로 변경 (O(n))
• unique() : 인접하여 중복되는 원소에 대해서 첫번째만 남겨두고 나머지는 제거함.

 

 

unique()함수는 두 원소가 같은지를 판단하는 방식에 따라 두 가지 형태로 제공됩니다.

 

1. 인자가 없는 형태로, 원소 타입의 등호 연산자를 사용하여 같은지를 판단함.
2. bool값을 반환하는 이항 조건자를 인자로 받으며, 이 조건자는 리스트 원소 타입의 인자를 두 개 받습니다.

unique()함수는 보통 리스트를 먼저 정렬한 후 사용하는게 정석임

 

 

 

std::forward_list<int> list1={2,53,1,0,4,10};
list1.reverse(); //실행 결과: {10,4,0,1,53,2}

list1={0,1,0,1,-1,10,5,5,10,0};
list1.unique(); //실행 결과: {0,1,0,1,-1,10,5,10,0}

list1={0,1,0,1,-1,10,5,5,10,0};
list1.sort(); //실행 결과: {-1,0,0,0,1,1,5,5,10,10}
list1.unique(); //실행 결과: {-1,0,1,5,10}



//리스트에서 특정 원소가 바로 앞 원소보다 2 이상 크지 않으면 삭제함
list1.unique([](int a,int b)){return (b-a) < 2;});
//실행 결과: {-1,1,5,10}

---

std::forward_list의 기타 멤버 함수

원소값을 검사하여 삭제하는 remove()와 remove_if() 함수도 제공합니다. 

 

remove()함수는 삭제할 원소 값 하나를 매개변수로 받습니다.

이 함수는 저장된 데이터 타입에 정의된 등호 연산자를 사용하여 전잘된 값과 일치하는 모든 원소를 찾아 삭제합니다.

저장된 데이터 타입에서 등호 연산이 지원되지 않으면 remove()함수를 사용할 수 없으며, 이 경우 컴파일러는 에러를 발생시킵니다.

remove()함수는 오직 등호 연산에 근거하여 원소를 삭제하며, 다른 조건에 근거하여 삭제 여부를 결정할수 없습니다.

 

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

최신 C++버전을 사용한다면 조건자 자리에 람다식을 사용할 수 있습니다.

remove_if() 함수는 특정 조건에 해당하는 원소를 선별적으로 삭제할 때 사용합니다.