std::map::upper_bound

#include <map>

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.

      iterator upper_bound(const key_type& key);
const_iterator upper_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 lớn 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 lớn 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 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ử "lớn hơn": upper_bound() tìm kiếm phần tử đầu tiên có key lớn hơn key.
2. Sắp xếp: upper_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 hoặc bằng key, upper_bound() trả về end() (hoặc cend()).
4. Không thay đổi std::map: upper_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 lower_bound(): upper_bound() tìm phần tử đầu tiên có key lớn hơn key, trong khi 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).
6. Kết hợp với equal_range(): upper_bound() thường được sử dụng cùng với lower_bound() hoặc equal_range() để xác định phạm vi của các phần tử có cùng key.
7. Độ phức tạp: Độ phức tạp của upper_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 lớn hơn 25
  auto it = mymap.upper_bound(25);
  if (it != mymap.end()) {
    std::cout << "The upper bound of 25 is: " << it->first << '\n'; // Output: The upper bound of 25 is: 30
  } else {
    std::cout << "No element has a key greater than 25\n";
  }

  // Tìm phần tử đầu tiên có key lớn hơn 30
  it = mymap.upper_bound(30);
  if (it != mymap.end()) {
    std::cout << "The upper bound of 30 is: " << it->first << '\n'; // Output: The upper bound of 30 is: 40
  } else {
    std::cout << "No element has a key greater than 30\n";
  }

  // Tìm phần tử đầu tiên có key lớn hơn 5 (tồn tại)
  it = mymap.upper_bound(5);
  if (it != mymap.end()) {
    std::cout << "The upper bound of 5 is: " << it->first << '\n'; // Output: The upper bound of 5 is: 10
  } else {
    std::cout << "No element has a key greater than 5\n";
  }

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

  return 0;
}

Các hàm liên quan

lower_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::map có key lớn hơn hoặc bằng 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