1-5. 반복자, std::list

반복자

std::forward_list 반복자와 std::vector, std::array 반복자의 차이를 알아볼 것이다. 

앞에서 배열과 포인터를 설명할 때 반복자에 숫자를 더하여 사용한 것을 기억할 것이다. 

 

반복자는 포인터와 비슷하지만, STL 컨테이너에 대해 공통의 인터페이스를 제공한다. 

반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다. 

백터와 배열에서 사용하는 반복자는 기능 면에서 가장 유연하다. 

백터와 배열은 연속된 자료구조를 사용하기 때문에 특정 위치의 원소에 곧바로 접근할 수 있다. 이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다. 

 

그러나 std::forward_list의 경우 기본적으로 역방향으로 이동하는 기능을 제공하지 않으며, 바로 이전 노드로 이동하려면 맨 처음 노드부터 시작해서 찾아가야 한다. 

따라서 std::forward_list에서는 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(forward iterator)라고 한다. 

 

반복자 타입에 따라 사용할 수 있는 함수 중에 advance(), next(), prev() 함수에 대해 알아보자. 

 

advance() 함수는 반복자와 거리 값을 인자로 받고, 반복자를 거리 값만큼 증가시킨다. 

next()와 prev() 함수도 반복자와 거리 값을 인자로 받고, 해당 반복자에서 지정한 거리만큼 떨어진 위치의 반복자를 반환한다. 

이들 함수는 해당 반복자가 지원할 경우에만 동작한다. 예를 들어, 순방향으로만 이동 가능한 순방향 반복자에 대해 prev() 함수를 사용하면 에러가 발생한다.

 

이들 함수의 동작 시간은 반복자 타입에 따라 결정된다. 

임의 접근 반복자에서는 덧셈 또는 뺄셈이 상수 시간으로 동작하므로 next(), prev() 등의 함수도 상수 시간으로 동작한다. 

나머지 타입의 반복자에서는 주어진 거리만큼 순방향 또는 역방향을 이동해야 하기 때문에 선형 시간이 소요된다. 

 

벡터에서는 특정 원소에 즉각적으로 접근할 수 있으므로 벡터 반복자의 덧셈과 뺄셈 연산은 O(1)이다. 

반면에 std::forward_list는 연속적인 순회를 통해서만 특정 원소에 접근할 수 있다. 

그러므로 std::forward_list 반복자의 덧셈 연산 시간 복잡도는 O(n)이고, 여기서 n은 순회할 횟수를 나타낸다. 

 

 

std::list

std::forward_list는 아주 기본적인 형태로 구현된 연결 리스트이다. 

std::forward_list는 다른 유용한 기능 중에서도 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능은 제공하지 않는다. 이는 메모리를 적게 쓰고 빠른 성능을 유지하기 위함이다. 

즉, std::forward_list는 빠른 원소 삽입이 필요한 모든 경우에 어울리는 컨테이너는 아니다. 

이러한 std::forward_list의 단점을 보완하기 위해 c++는 std::list를 제공한다. 

 

std::list는 양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked list) 구조로 되어 있으며, 덕분에 std::forward_list에 비해 더 많은 기능을 제공하고, 조금 더 많은 메모리를 사용한다. 

 

이중 연결 리스트에서 사용하는 노드의 기본 형태는 다음과 같다. 

struct doubly_linked_list_node
{
int data;
double_linked_list_node* next;
double_linked_list_node* prev;
};

이중 연결 리스트 노드는 이전 노드를 가리키는 포인터가 추가로 있다. 

이 포인터를 이용하여 역방향으로 이동할 수 있으며, 맨 마지막 원소와 리스트 크기를 따로 저장하여 빠른 push_back() 또는 size() 함수를 지원할 수 있다. 

 

또한 std::forward_list와 마찬가지로 템플릿 매개변수로 사용자 정의 할당자를 지정할 수도 있다. 

 

 

std::list 멤버 함수

std::list에서 제공하는 대부분의 함수는 std::forward_list의 함수와 같거나 유사하며, 약간의 차이가 있다. 

예를 들어 std::forward_list에서 _after로 끝나는 함수는 std::list에서 _after로 끝나지 않는 형태로 바뀐다. 

즉, insert_after()과 emplace_after() 함수는 insert()와 emplace() 함수와 대응된다. 

std::list에서는 원소 이동을 역방향으로도 할 수 있으므로 원소 삽입을 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도 되며, 대신 정확하게 새로운 원소가 삽입될 위치를 가리키는 반복자를 함수 인자로 전달한다.

 

이외에도 std::list는 빠른 push_back(), emplace_back(), pop_back() 함수를 제공한다. 

 

#include <iostream>
#include <list>

int main()
{
std::list<int> list1 = {1, 2, 3, 4, 5};
list1.push_back(6); //{1, 2, 3, 4, 5, 6}
list1.insert(next(list1.begin()), 0);   //{1, 0, 2, 3, 4, 5, 6}
list1.insert(list1.end(), 7);  //{1, 0, 2, 3, 4, 5, 6, 7}
}

list1.pop_back();  //{1, 0, 2, 3, 4, 5, 6}
for(auto i : list1)
	std::cout<<i<<" ";

}

 

std::forward_list와 std::list의 push_front(), insert(), pop_front(), erase() 함수 시간 복잡도는 서로 같지만, 실제로 std::list에서 좀 더 많은 연산이 필요하다. 

왜냐하면 std::list는 각각의 노드에 두 개의 포인터를 가지고 있고, 삽입 또는 삭제 연산 시 두 개의 포인터를 관리해야 하기 때문이다. 이중 연결 리스트에서 포인터를 관리하기 위해서는 단일 연결 리스트보다 대략 두 배의 연산을 수행해야 한다. 

 

remove(), remove_if(), sort(), unique(), reverse() 등의 함수도 std::list에서 제공되며, std::forward_list와 같은 형태로 동작한다. 

 

 

양방향 반복자

앞서 반복자에 대해 설명할 때, 배열 기반의 임의 접근 반복자와 std::forward_list 기반의 순방향 반복자와의 유연성 차이에 대해 알아봤다. 

std::list의 반복자는 이 두 반복자 중간 정도의 유연성을 가지고 있다. 

std::list의 반복자는 역방향으로 이동할 수 있으므로 std::forward_list보다 제약이 적다. 

즉, std::list는 역방향으로의 연산이 필요한 경우에는 역방향 반복자(reverse iterator)를 사용할 수 있다. 

그러나 std::list 반복자는 임의 접근 반복자보다 유연하지 않다. 이를 이용하여 어느 방향이든 원하는 만큼 이동할 수 있지만, 임의 접근 반복자의 경우처럼 특정 위치로 한 번에 이동하는 것은 불가능하다. 

그러므로 std::list 반복자를 이용하여 특정 위치로 이동하는 작업은 선형 시간 복잡도를 가진다. 

std::list 반복자는 어느 방향으로든 이동할 수 있으므로 양방향 반복자(bidirectional iterators)라고 부른다. 

 

 

반복자 무효화

지금까지 어떤 컨테이너든 원소 접근, 순회, 삽입, 삭제 등의 작업을 반복자를 사용하여 모두 같은 방식으로 처리한다는 점을 확인했다. 

반복자는 메모리 주소를 가리키는 포인터를 이용하여 구현되었기 때문에 경우에 따라 컨테이너가 변경될 경우 제대로 동작하지 않을 수 있다. 

 

벡터에서 맨 뒤에 원소를 추가하는 vector::push_back() 함수를 예로 들어보자. 

이 함수는 경우에 따라 새로 메모리 공간을 할당하고 기존의 모든 원소를 새 메모리 공간으로 복사하는 동작이 발생한다. 

이 경우 기존에 사용하던 모든 반복자와 포인터, 참조는 모두 무효화된다. 

 

마찬가지로 vector::insert() 함수를 수행할 때 메모리 재할당이 필요한 경우라면, 이 경우에도 기존의 반복자, 포인터, 참조는 모두 사용하면 안된다. 

vector::insert() 함수에서 메모리 재할당 없이 원소를 삽입하는 경우라면, 원소 삽입 위치 이후에 있는 원소들을 모두 이동해야 하므로 이 위치를 가리키는 반복자는 모두 무효화된다. 

 

벡터와 달리 연결 리스트에서는 삽입 또는 삭제 동작에서 원소를 이동할 필요가 없으므로 반복자가 무효화되지 않는다. 

즉, std::list 또는 std::forward_list에서 삽입 동작은 반복자의 유효성에 영향을 미치지 않는다. 

다만, 특정 원소를 삭제하는 경우, 삭제되는 원소를 가리키던 반복자는 당연히 무효화 되지만 나머지 원소를 가리키는 반복자는 그대로 사용할 수 있다. 

 

std::vector<int> vec = {1, 2, 3, 4, 5};
auto v_it4 = vec.begin()+4;   //v_it4는 vec[4] 원소를 가리킨다
vec.insert(vec.begin()+2, 0);  //v_it4 반복자는 무효화된다


std::list<int> lst = {1, 2, 3, 4, 5};
auto l_it4 = next(lst.begin(), 4);
lst.insert(next(lst.begin(), 2), 0);  //l_it4 반복자는 여전히 유효하다.

 

std::list는 size(), push_back(), pop_back() 등의 더 많은 함수를 제공하며, 이들 연산은 O(1) 시간 복잡도로 동작한다.

그러므로 std::list가 std::forward_list보다 더 자주 사용된다. 

std::forward_list는 데이터를 역방향으로 이동하며 접근하지 않아도 되는 경우에 메모리 또는 성능을 최적화하고 싶을 때에만 제한적으로 사용된다. 즉, 대부분의 경우에는 std::list를 사용하는 것이 더 나은 선택이다.