如何在不新建std::vector的情况下用std::lower_bound搜索二维矩阵最右列？

我正在使用C++20解决Leetcode 74题：搜索二维矩阵。题目要求在按行主序部分有序的二维矩阵中查找指定元素。

我的解法思路是先定位目标可能存在的行，再在该行内查找：具体通过对每行的最后一个元素进行二分查找，找到首个最后元素大于等于目标的行。

现在我想知道，能否无需新建std::vector来存储最右列，直接使用std::lower_bound搜索该列？我曾尝试使用view，但未满足相关concept要求。

示例代码 #

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

auto searchMatrix(auto&& matrix, auto target) {
  // MAYBE use an iterator?
  auto rightmost_col = [&]{
    using Col = std::remove_reference<decltype(matrix[0])>::type;
    auto rightmost_col = Col();
    for (auto i : std::views::iota(0, std::ssize(matrix))) {
      rightmost_col.push_back(matrix[i].back());
    }
    return rightmost_col;
  }();

  auto find = [&](const auto& space) -> std::optional<decltype(target)> {
    auto pos = std::ranges::lower_bound(space, target);
    if (pos == std::ranges::end(space)) return std::nullopt;
    return pos - std::ranges::begin(space);
  };

  if (auto candidate_row = find(rightmost_col)) {
    if (auto candidate_col = find(matrix[*candidate_row])) {
      return matrix[*candidate_row][*candidate_col] == target;
    }
  }
  return false;
}

auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -> int {
  auto matrix = std::vector<std::vector<int>>{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  auto target = 3;
  auto result = searchMatrix(matrix, target);
  std::cout << std::boolalpha << result << std::endl;
}

完全可以不用额外创建std::vector，利用C++20的Ranges库就能直接对矩阵的最右列进行二分查找，核心是用std::views::transform生成惰性视图映射每行的最后一个元素，同时确保视图满足std::ranges::random_access_range要求，让std::ranges::lower_bound高效执行二分。

修改后的代码 #

#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
#include <optional>

auto searchMatrix(auto&& matrix, auto target) {
  // 生成最右列的惰性视图，不拷贝任何元素
  auto rightmost_col_view = matrix | std::views::transform([](auto&& row) -> decltype(auto) {
    return row.back();
  });

  // 适配range的通用查找逻辑
  auto find_pos = [&](const auto& range) -> std::optional<std::ptrdiff_t> {
    auto it = std::ranges::lower_bound(range, target);
    if (it == std::ranges::end(range)) {
      return std::nullopt;
    }
    // 用ranges::distance计算位置，适配不同类型的range
    return std::ranges::distance(std::ranges::begin(range), it);
  };

  if (auto candidate_row_idx = find_pos(rightmost_col_view)) {
    auto& candidate_row = matrix[*candidate_row_idx];
    if (auto candidate_col_idx = find_pos(candidate_row)) {
      return candidate_row[*candidate_col_idx] == target;
    }
  }
  return false;
}

auto main([[maybe_unused]] int argc, [[maybe_unused]] char** argv) -> int {
  auto matrix = std::vector<std::vector<int>>{{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
  
  auto target = 3;
  auto result = searchMatrix(matrix, target);
  std::cout << std::boolalpha << result << std::endl;

  target = 13;
  result = searchMatrix(matrix, target);
  std::cout << std::boolalpha << result << std::endl;
}

关键细节说明 #

1. 惰性视图的优势：std::views::transform生成的视图不会拷贝原矩阵元素，仅在需要时返回对应行的最后一个元素，节省内存和拷贝开销。由于原矩阵是std::vector<std::vector<int>>（属于random_access_range），转换后的视图也继承了该属性，保证二分查找的时间复杂度为O(log n)。
2. 迭代器位置计算：用std::ranges::distance替代原生指针减法，因为视图的迭代器不一定是原生指针，而std::ranges::distance会根据range类型自动选择最优计算方式（random_access_range下为O(1)）。
3. 避免不必要拷贝：用decltype(auto)确保返回行最后元素的引用，避免值拷贝。

之前view尝试失败的原因 #

大概率是你生成的视图未满足random_access_range要求，或是用了原生指针减法计算位置（视图迭代器不支持该操作）。上面的代码通过继承原矩阵的random_access属性，并使用std::ranges::distance计算位置，解决了这个问题。

内容的提问来源于stack exchange，提问作者argmaxmax