Тест LOWER_BOUND против конца итератора

Question

В эффективной STL Скотт Мейерс (стр 195) есть следующая строка:

«Результат lower_bound должен быть проверен, чтобы увидеть, если он указывает на значение, которое вы в отличие от find, вы не можете просто проверить возвращаемое значение lower_bound в конце итератора ».

Может кто-нибудь объяснить, почему вы не можете это сделать? кажется, работает отлично для меня.

Answer 1

Он отлично подходит для вас, потому что ваш элемент присутствует.

lower_bound возвращает итератор на первый элемент не менее, чем заданное значение, и upper_bound возвращает итератор на первый элемент большей, чем заданное значение.

Учитывая массив 1, 2, 3, 3, 4, 6, 7, lower_bound(..., 5) возвращает итератор, указывающий на 6.

Следовательно, два способа проверки, присутствует ли значение:

• Используйте equal_range также получить upper_bound (вычисления отдельно lower_bound и upper_bound, вероятно, будут субоптимальными). Если std::distance между границами больше 0, то элемент присутствует.

  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 
  

• Сравните элемент, на который указывает итератор со своим значением (при условии, операторы != и < когерентны), но вы должны убедиться, что он не возвращает конечный итератор.

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

Кроме того, поскольку lower_bound является бинарным алгоритмы поиска было бы непоследовательно вернуть end, если элемент не был найден. Фактически, итераторы, возвращаемые этим алгоритмом, могут использоваться как подсказка для последующей операции вставки, например.