test LOWER_BOUND przeciwko końca iterator

Question

W skutecznej STL przez Scott Meyers (strona 195) znajduje się następujący wiersz:

„Wynik LOWER_BOUND muszą być badane, aby zobaczyć, czy to, wskazując na wartość jesteś W przeciwieństwie do find, nie można po prostu przetestować wartości zwracanej przez lower_bound na iterator końcowy. "

Czy ktoś może wyjaśnić, dlaczego nie możesz tego zrobić? Wydaje mi się, że działa dobrze dla mnie.

Answer 1

Działa to dobrze, ponieważ twój element jest obecny.

lower_bound zwraca iteracyjnej z pierwszym elementem nie mniej od podanej wartości i upper_bound zwraca iteracyjnej z pierwszym elementem większej niż podana wartość.

Biorąc pod tablicą 1, 2, 3, 3, 4, 6, 7, lower_bound(..., 5) powróci iterator wskazujący na 6.

Stąd dwa sposoby sprawdzenia, czy wartość jest obecny:

• Zastosowanie equal_range również uzyskać upper_bound (computing oddzielnie lower_bound i upper_bound będzie prawdopodobnie nieoptymalny). Jeśli wartość std::distance między granicami jest większa niż 0, element jest obecny.

  1, 2, 3, 3, 4, 6, 7 
  std::distance(std::lower_bound(v.begin(),v.end(),5), std::upper_bound(v.begin(),v.end(),5)) == 0 // 6 is absent 
  std::distance(std::lower_bound(v.begin(),v.end(),3), std::upper_bound(v.begin(),v.end(),3)) == 2 // 3 is present 
  

• Porównaj elementu wskazywanego przez iterator ze swojej wartości (pod warunkiem operatorów != i < są spójne), ale trzeba się upewnić, że nie zwraca iterator end.

  *(std::lower_bound(v.begin(), v.end(), 5)) != 5 
  

Dodatkowo, ponieważ lower_bound jest binarnym algorytmy wyszukiwania byłoby to niezgodne wrócić end jeśli element nie został znaleziony. Rzeczywiście, iteratory zwracane przez ten algorytm mogą być na przykład wskazówką dla kolejnej operacji wstawiania.