C++에서 std :: forward_list swap() 구현

Question

내 가정은 std::list<>에있는 목록 자체에 대한 swap 함수는 앵커 노드를 교체하여 수행된다는 것입니다. 노드는 이전 노드에 액세스하고 이전 노드의 다음 포인터를 다른 목록의 앵커를 가리 키도록 쉽게 업데이트 할 수 있습니다. 그러나 이것은 std::forward_list에서 할 수 없습니다 (글쎄, 그럴 수 있습니다, 그것은 매우 값 비쌉니다).

내 가정이 맞는 경우 swap()은 효율적인 방식으로 std::forward_list에 어떻게 구현됩니까? 그리고 우리가 그것에 도달하는 동안 은 iterator에 대해 어떻게 구현 되었습니까? std::forward_list? std::forward_list

Answer 1

그러므로 당신은 단순히 swap() 작업을 수행하기 위해 목록의 head 및 tail 포인터를 교체 할 수 있습니다, A는 std::list 같은 이중 연결리스트가 아닌 단독으로 연결된 간단하다.

Answer 2

이것은 완전히 구현에 따라 다르지만, 클래스가 첫 번째와 마지막 링크 셀 목록에 포인터를 저장하도록함으로써 앞으로 목록이 구현되는 경우 스왑은 두 포인터를 스왑 할 수 있습니다. 순방향 링크리스트에는 백 포인터가 없으므로 더 이상 업데이트 할 필요가 없으며 O (1)에서 전체 연산을 수행 할 수 있습니다.

반복자를 사용한 스왑의 경우 두 목록간에 연결된 목록 셀을 실제로 교환하지 않습니다. 두 번째 이터레이터에서 참조하는 셀에 첫 번째 이터레이터를 가리키고 그 반대의 경우도 마찬가지입니다. 당신이 가리키고있는 값을 바꾸고 싶다면 링크 된리스트 셀의 객체를 수정하여 값을 바꿀 수 있습니다. 어떤 방법 으로든 목록을 다시 연결할 필요는 없습니다.

희망이 있습니다.

Answer 3

나는 당신이 혼란 스럽다고 생각합니다. (또는 당신이 묻는 것을 혼동합니다.) std :: forward_list :: swap (std :: forward_list & other)은 각 목록 객체가 std :: list와 같이 목록의 헤드 (및 다른 멤버 변수)에 대한 포인터를 교환한다는 점에서 간단합니다.

iterator 객체에는 스왑 메소드가 없습니다. 포함 된 개체는 전역 스왑 메서드를 사용하거나 사용할 수 있지만 개체에서 작동하며 목록 자체 나 해당 노드를 변경하지 않습니다.