컨테이너 관련 알고리즘에서 search_n을 고쳐야 하지 않을까요?
글쓴이: dltkddyd / 작성시간: 일, 2014/01/05 - 12:20오후
search_n은 컨테이너에서 일련의 탐색 문자가 처음에 나온 맨 앞의 반복자를 반복합니다. 그리고 그 알고리즘은 다음과 같다는데요.
template<class ForwardIterator, class Size, class T> ForwardIterator search_n (ForwardIterator first, ForwardIterator last, Size count, const T& val) { ForwardIterator it, limit; Size i; limit=first; std::advance(limit,std::distance(first,last)-count); while (first!=limit) { it = first; i=0; while (*it==val) // or: while (pred(*it,val)) for the pred version { ++it; if (++i==count) return first; } ++first; } return last; }
여기서 질문드립니다. 여기서 limit는 끝 지점 last 전의 count 개의 요소를 남겨놓은 지점을 가리킵니다. 그리고 저 limit라는 것은 더 이상 검색할 필요가 없는 지점을 가리키기 위한 조건의 기준 값으로 쓰이는 것인데, while(first!=limit) 라는 조건에 의하면 마지막에서 count개를 남겨놓은 지점은 검토하지 않도록 돼어 있습니다. 알고리즘대로라면요. 그런데 그 지점을 검토하네요. 그 이유가 뭔가요? 정확히 저 알고리즘은 이런 식으로 바꿔야 되지 않을까요?
template<class ForwardIterator, class Size, class T> ForwardIterator search_nn(ForwardIterator first, ForwardIterator last, Size count, const T& val) { ForwardIterator it, limit; Size i; limit=first; std::advance(limit, std::distance(first, last)-count); if(count==0) {return last;} while(first!=(limit+1)) { it=first;i=0; while(*it==val) { ++it; if(++i==count) {return first;} } ++first; } return last; }
Forums:
댓글 달기