c++ - 在二维数组中查找列的 lower_bound()

Question

我有一个二维数组，我想在其中找到特定列的下界。

我如何使用 std::lower_bound 做到这一点？

Answer 1

简介

这并不像人们想象的那么难，让我们首先浏览一下适用于范围的算法函数的摘要。

每个这样的函数，比如 std::lower_bound，接受一个 begin 和一个 end 迭代器来知道它们要搜索哪些元素.我们案例中的问题是，创建一个遍历列而不是行的迭代器似乎很重要。

好消息；它不是。

---

形成指向数组的指针

我们可以在 C++ 中创建指向几乎所有内容的指针，当然也包括数组。

指针的好处在于，如果我们递增一个，我们将到达下一个元素，无论指针指的是什么类型。在我们的例子中，我们希望遍历二维数组中的所有嵌套数组。

T a[5][3] = { ... };

T(*p)[3] = &a[0]; // is a pointer to an array of three `T`,
                  // currently pointing to a[0]

++p;              // now referring to a[1]

---

实现

#include <iostream>
#include <algorithm>
#include <iterator>

struct not_less_than_column {
  not_less_than_column (unsigned long idx)
    : m_idx (idx)
  { }

  template<class T, unsigned long N>
  bool operator() (T(&arr)[N], T const& needle) const {
    return arr[m_idx] < needle;
  }

  unsigned long m_idx;
};

int main () {
  int a[5][3] = {
    { 0, 24,  1 },
    { 0, 35,  1 },
    { 0, 42,  1 },
    { 0, 66,  1 },
    { 0, 100, 1 }
  };

  auto ptr = std::lower_bound (std::begin (a), std::end (a), 36, not_less_than_column (1));

  for (auto const& e : *ptr)
    std::cout << e << " "; // 0 42 1
}

<sup>注意:使用std::begin和 std::end是 &a[0] 和 &a[5] 的更清晰的替代。

注意:我们可以将 not_less_than_column(1) 替换为 lambda，但由于通用 lambda 是C++11 不支持当前方法更简洁。</sup>