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

Question

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

我怎样才能做到这一点std::lower_bound？

Answer 1

介绍

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

每个这样的函数，比如std::lower_bound，都接受一个开始和一个结束 迭代器来知道它们要搜索哪些元素。在我们的例子中，问题在于创建一个迭代列而不是行的迭代器似乎并不简单。

好消息; 事实并非如此。

形成指向数组的指针

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

指针的好处是，如果我们加一，我们就会到达下一个元素，无论指针引用什么类型。在我们的例子中，我们想要迭代 2D 数组中的所有嵌套数组。

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::beginand是andstd::end的更清晰的替代。&a[0]&a[5]

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