std::equal_range

#include <algorithm>

// So sánh bằng toán tử <
template <class ForwardIterator, class T>
std::pair<ForwardIterator, ForwardIterator>
  equal_range (ForwardIterator first, ForwardIterator last, const T& val);

// Sử dụng hàm so sánh tùy chỉnh
template <class ForwardIterator, class T, class Compare>
std::pair<ForwardIterator, ForwardIterator>
  equal_range (ForwardIterator first, ForwardIterator last, const T& val,
              Compare comp);

Tìm phạm vi con (subrange) trong một phạm vi (range) đã được sắp xếp mà chứa tất cả các phần tử có giá trị tương đương với một giá trị cho trước. Phạm vi con này được xác định bởi cặp iterator, iterator đầu tiên trỏ đến phần tử đầu tiên không nhỏ hơn giá trị cho trước (lower bound), và iterator thứ hai trỏ đến phần tử đầu tiên lớn hơn giá trị cho trước (upper bound).

Tham số

`first`

Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi đã sắp xếp cần tìm kiếm.

`last`

Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. Phạm vi là [first, last).

`val`

Giá trị cần tìm phạm vi con tương đương.

`comp`

Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (một phần tử trong phạm vi và val) và trả về true nếu phần tử thứ nhất (trong phạm vi) được coi là nhỏ hơn val theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

Một std::pair chứa hai Forward Iterator:
- pair.first: Iterator trỏ đến phần tử đầu tiên không nhỏ hơn val (lower bound).
- pair.second: Iterator trỏ đến phần tử đầu tiên lớn hơn val (upper bound).

thông tin

Phạm vi con chứa các phần tử tương đương với val là [pair.first, pair.second). Nếu không có phần tử nào tương đương với val, hai iterator trong pair sẽ bằng nhau và trỏ đến vị trí mà val có thể được chèn vào mà không làm mất tính sắp xếp.

Đặc điểm

Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
equal_range() yêu cầu phạm vi đầu vào đã được sắp xếp theo thứ tự tương ứng (tăng dần hoặc theo comp).
equal_range() trả về một std::pair chứa hai iterator, đại diện cho lower bound và upper bound của phạm vi con.
equal_range() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
equal_range() sử dụng thuật toán tìm kiếm nhị phân (binary search) để tìm kiếm phạm vi con, do đó, độ phức tạp thời gian là O(log n), trong đó n là số phần tử trong phạm vi.
Phạm vi đầu vào phải được sắp xếp theo thứ tự tăng dần (hoặc theo tiêu chí so sánh được cung cấp) trước khi gọi equal_range(). Nếu phạm vi không được sắp xếp, kết quả sẽ không chính xác.
equal_range() thường được sử dụng để:
- Tìm tất cả các phần tử có giá trị bằng với một giá trị cho trước trong một dãy đã sắp xếp.
- Xác định số lần xuất hiện của một giá trị trong một dãy đã sắp xếp.
- Triển khai các cấu trúc dữ liệu và thuật toán dựa trên tìm kiếm nhị phân.

Phân biệt với lower_bound() và upper_bound()

lower_bound() trả về iterator trỏ đến phần tử đầu tiên không nhỏ hơn val.
upper_bound() trả về iterator trỏ đến phần tử đầu tiên lớn hơn val.
equal_range() trả về một cặp iterator, tương đương với (lower_bound, upper_bound).

Ví dụ

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> numbers = {1, 2, 3, 4, 4, 4, 5, 6};

  // Tìm phạm vi con chứa các phần tử có giá trị bằng 4
  auto range = std::equal_range(numbers.begin(), numbers.end(), 4);

  std::cout << "Lower bound index: " << (range.first - numbers.begin()) << std::endl;
  std::cout << "Upper bound index: " << (range.second - numbers.begin()) << std::endl;

  std::cout << "Elements equal to 4: ";
  for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;

  // Tìm phạm vi con chứa các phần tử có giá trị bằng 7 (không tồn tại)
  auto range2 = std::equal_range(numbers.begin(), numbers.end(), 7);
  std::cout << "Range for 7: [" << (range2.first - numbers.begin()) << ", "
            << (range2.second - numbers.begin()) << ")" << std::endl;
  if (range2.first == range2.second)
      std::cout << "not found" << std::endl;
  return 0;
}

Các hàm liên quan


lower_bound	Tìm vị trí đầu tiên trong một phạm vi đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi
upper_bound	Tìm vị trí đầu tiên trong một phạm vi đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi, nhưng phải đảm bảo giá trị được chèn vào sau tất cả các phần tử có giá trị bằng với nó
binary_search	Kiểm tra xem một giá trị cho trước có tồn tại trong một phạm vi đã được sắp xếp hay không, sử dụng thuật toán tìm kiếm nhị phân

Tham số​

first​

last​

val​

comp​

Giá trị trả về​

Đặc điểm​

Ví dụ​

Các hàm liên quan​