std::map::lower_bound

#include <map>

Trả về một iterator trỏ đến phần tử đầu tiên trong std::map có key không nhỏ hơn (lớn hơn hoặc bằng) giá trị key cho trước.

      iterator lower_bound(const key_type& key);
const_iterator lower_bound(const key_type& key) const;

Tham số

key

• Giá trị của key cần tìm kiếm.

Giá trị trả về

• iterator (phiên bản không const): Trả về iterator có thể đọc và ghi, trỏ đến phần tử đầu tiên có key không nhỏ hơn key.
• const_iterator (phiên bản const): Trả về const_iterator chỉ đọc, trỏ đến phần tử đầu tiên có key không nhỏ hơn key. Phiên bản này được sử dụng khi std::map là một đối tượng const.
• Nếu không có phần tử nào trong std::map có key lớn hơn hoặc bằng key, hàm trả về end() (hoặc cend() cho phiên bản const).

Đặc điểm

1. Tìm kiếm phần tử "không nhỏ hơn": lower_bound() tìm kiếm phần tử đầu tiên có key không nhỏ hơn key, tức là lớn hơn hoặc bằng key.
2. Sắp xếp: lower_bound() dựa trên thứ tự sắp xếp của các key trong std::map.
3. Trả về end() nếu không tìm thấy: Nếu tất cả các key trong std::map đều nhỏ hơn key, lower_bound() trả về end() (hoặc cend()).
4. Không thay đổi std::map: lower_bound() là một hàm const, nó không làm thay đổi nội dung hay trạng thái của std::map.
5. Phân biệt với upper_bound(): lower_bound() tìm phần tử đầu tiên có key không nhỏ hơn key (lớn hơn hoặc bằng), trong khi upper_bound() tìm phần tử đầu tiên có key lớn hơn key.
6. Không đảm bảo key tồn tại: lower_bound() chỉ trả về iterator đến phần tử đầu tiên có key không nhỏ hơn key, không đảm bảo key đó tồn tại trong std::map.
7. Độ phức tạp: Độ phức tạp của lower_bound() là O(log n), với n là số phần tử trong std::map.

Ví dụ

#include <iostream>
#include <map>

int main() {
  std::map<int, std::string> mymap = {
    {10, "ten"},
    {20, "twenty"},
    {30, "thirty"},
    {40, "forty"},
    {50, "fifty"}
  };

  // Tìm phần tử đầu tiên có key không nhỏ hơn 25
  auto it = mymap.lower_bound(25);
  if (it != mymap.end()) {
    std::cout << "The lower bound of 25 is: " << it->first << '\n'; // Output: The lower bound of 25 is: 30
  } else {
    std::cout << "No element has a key greater than or equal to 25\n";
  }

  // Tìm phần tử đầu tiên có key không nhỏ hơn 30
  it = mymap.lower_bound(30);
  if (it != mymap.end()) {
    std::cout << "The lower bound of 30 is: " << it->first << '\n'; // Output: The lower bound of 30 is: 30
  } else {
    std::cout << "No element has a key greater than or equal to 30\n";
  }

  // Tìm phần tử đầu tiên có key không nhỏ hơn 60 (không tồn tại)
  it = mymap.lower_bound(60);
  if (it != mymap.end()) {
    std::cout << "The lower bound of 60 is: " << it->first << '\n';
  } else {
    std::cout << "No element has a key greater than or equal to 60\n"; // Output: No element has a key greater than or equal to 60
  }

  return 0;
}

Các hàm liên quan

upper_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::map có key lớn hơn giá trị key cho trước
equal_range	Trả về một cặp iterator xác định phạm vi các phần tử trong std::map có key bằng với giá trị key cho trước
find	Tìm kiếm một phần tử có key bằng với giá trị key cho trước trong std::map
count	Đếm số lượng phần tử có key bằng với giá trị key cho trước trong std::map