24.12.10 (화)

std::find 

InputIterator find(InputIterator first, InputIterator last, const T& value);

std::find는  특정 컨테이너(vector, list 등)에서 특정 값을 검색할 때 사용하는 함수이다.

이 함수는 <algorithm>에 정의 되어있고 O(n)의 시간 복잡도를 가지며, n은 배열의 크기를 의미한다.

 

반환 값은 value가 존재하면 해당 값의 Iterator를 반환하고, 존재하지 않으면 last Iterator를 반환한다.

 

순차적으로 검색함으로, 최악의 경우 마지막까지 탐색한다.

 

 

std::distance

distance(InputIterator first, InputIterator last);

std::distance는 두 Iterator 사이의 거리(요소 개수)를 계산하는 함수이다. 이는 list와 같이 순차적으로 접근해야하는 컨테이너에서도 거리를 계산할 수 있다.

 

왼쪽은 문제에서 "kim"이 반드시 seoul 안에 포함되어 있다고 명시되어있기 때문에 std::distance안에 std::find를 사용해서 바로 "Kim"이 위치해 있는 인덱스 값을 얻어왔는데, 만약 문제에서 찾고자 하는 "Kim"이 없을 수도 있다는 가정이 있다면,

우측과 같이 std::find를 통해 가져온 Iterator 값이 "Kim"의 Iterator가 맞는지 확인하는 과정이 필요해 보인다.