Kiểm tra giá trị trả về của lower_bound so với trình lặp kết thúc

Question

Trong STL hiệu quả bởi Scott Meyers (trang 195) có dòng sau:

"Kết quả của lower_bound phải được kiểm tra để xem liệu nó có trỏ đến giá trị bạn đang Không giống như tìm kiếm, bạn không thể chỉ kiểm tra giá trị trả về của lower_bound đối với trình lặp kết thúc. "

Có ai giải thích tại sao bạn không thể làm điều này? dường như làm việc tốt cho tôi.

Answer 1

Nó hoạt động tốt cho bạn bởi vì yếu tố của bạn là hiện tại.

lower_bound trả về một iterator tới phần tử đầu tiên không ít hơn giá trị nhất định, và upper_bound trả về một iterator tới phần tử đầu tiên hơn hơn giá trị nhất định.

Với mảng 1, 2, 3, 3, 4, 6, 7, lower_bound(..., 5) sẽ trả về một iterator trỏ đến 6.

Do đó, hai cách để kiểm tra xem giá trị hiện diện:

• Sử dụng equal_range để cũng nhận được upper_bound (máy tính riêng biệt lower_bound và upper_bound có thể sẽ tối ưu hóa dưới mức). Nếu std::distance giữa các giới hạn lớn hơn 0 thì phần tử có mặt.

  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 
  

• Hãy so sánh các yếu tố được trỏ bởi biến lặp với giá trị của mình (với điều kiện khai thác != và < là mạch lạc), nhưng bạn phải chắc chắn rằng nó không trả lại lặp kết thúc.

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

Bên cạnh đó, kể từ lower_bound là một thuật toán tìm kiếm nhị phân nó sẽ là không phù hợp để trở end nếu nguyên tố này không được tìm thấy. Trên thực tế, các trình vòng lặp được trả về bởi thuật toán này có thể được sử dụng như một gợi ý cho một thao tác chèn tiếp theo chẳng hạn.