집합의 반복자는 어떻게 작동합니까?

Question

C++의 STL에서 반복기가 어떻게 설정되는지 궁금합니다. 세트가 이진 검색 트리를 사용하여 구현되었다고 가정합니다. 즉,이 트리는이 트리를 순회하는 것을 의미합니다. 그러나 내 질문은 그들이 언제 우리가 을 좋아할 때이 traversing을 할 것인가입니다. 그것은 = s.begin() 입니다. 내부적으로 스택의 종류에서 순회 포인터를 저장하고 모든 증가마다이 데이터 구조만을 참조하십시오. 이터레이터 에 있거나 iterator의 증가분은 트리에서 새로운 inorder traversal을 수행합니다. 우리가

 set<int> s; 
    set<int>::iterator it; 

//and then use it like: 

     for(it = s.begin(); it!=s.end();) 
     { 
      dosth(); 
      ++it;  // does this do a inorder traversal of the tree again to find the next 
        // node or it gets the next node in the tree by reading the internal 
        // data structure(of inorder traversal) which is created when we do s.begin(). 
     } 

Answer 1

처럼 구현 의존의 초기화 할 때

는 내 말은. 그러나 반복자가 집합에서 제거 된 요소를 참조하는 경우에만 std :: set 반복자가 무효화됩니다. 따라서 std::set 반복자를 트리의 노드로 생각할 수 있습니다. ++는 그것을 트리의 한쪽 탐색 방향으로 이동시키고, 다른 방향으로 이동시킨다.

반복자는 begin이라는 다른 함수에서 반환되므로 시작/끝 반복에만 그 유효성이 제한되지 않습니다.

Answer 2

흥미로운 질문입니다. 니콜 (Nicol)은 구현에 의존하고 있으며 자체 세트를 구현하는 동안 더 작은 반복자를 사용할지 또는 더 빠른 탐색을 사용할지 (반복 속도를 높이기 위해 더 많은 데이터를 넣을 수 있음) 여부를 결정해야한다고 지적했습니다.

내 플랫폼 (64 비트) std::set<T>::iterator은 8 바이트 크기로, 실제 노드에 대한 포인터를 유지하는 것이 좋습니다. 집합이 어떤 종류의 트리를 사용하여 구현되면 반복자의 증가는 O (1) 연산이 아니며 균형 잡힌 트리에 대해 말하면 추가 노드 (N 개)까지 트래버스해야합니다. 나는 또한 다른 노드에 대한 ++it 작업의 속도를 점검했으며 여분의 탐색을 제안하는 것은 일정하지 않습니다. 트리 트래 버설의 복잡성에 대한 기대를 충족 시키므로 사람들은 일반적으로 iterator를 가능한 한 작게 가정하기 때문에 범용 set 컨테이너에 대해서는 완전히 완벽합니다. 표준 재귀 적 트리 순회를 구현하는 경우 정확히 동일하므로 스택에서 여분의 노드 방문을 숨길 수 있습니다.

자신의 트리 반복자 구현에 대한 자세한 내용은 Implementing an iterator over a binary search tree을 참조하십시오.