c++ - 是否可以编写符合标准的随机访问(或至少向前)整数迭代器？

假设我们有函数 f ，它接受整数并返回一个单调递增的值。我们想要找到最小的 x 使得 f(x) >= C 。为简单起见，我们假设答案在 [l;r) 范围内。显然我们可以编写自己的二进制搜索实现，但我们想使用现有的( std::patition_point )。

如此幼稚的实现(可能)会起作用:

// f;
std::vector<int> v(r - l);
std::iota(v.begin(), v.end(), l);
answer = l + partition_point(v.begin(), v.end(), [&](int x) {
    return f(x) <= C;
}) - v.begin();

明显的问题是我们必须存储所有的数字，这会占用大量内存，也需要时间来填充数组

下一个逻辑思想是以这种方式将整数包装到迭代器中:

struct IntIterator: std::iterator<std::random_access_iterator_tag, int> {
    int current;
    IntIterator(int i) : current(i) {}
    int operator*() const { return current; }
    IntIterator& operator++() { ++current; return *this; }
    IntIterator& operator+=(size_t n) { current += (int)n; return *this; }
    IntIterator operator+(size_t n) const { return current+(int)n;  }
    size_t operator-(IntIterator that) const { return size_t(current - that.current); }
    // others operators to conform
};

answer = partition_point(IntIterator{l}, IntIterator{r}, [&](int x) {
    return f(x) <= C;
});

这将适用于我的编译器(标准库)，但不符合随机访问迭代器，因为

operator* 应该返回 std::iterator_traits<IntIterator>::reference 。

如果我们将 std::iterator_traits<IntIterator>::reference 更改为 int (例如通过将模板参数更改为 std::iterator )，它将无法满足前向迭代器的要求:

如果我们将 operator* 的返回类型更改为 [const ]T& 它将无法满足前向迭代器的另一个要求

所以我不明白如何使它符合和问题是否可能出现。

最佳答案

我认为你不应该把这个要求看得太重。标准库包含一个容器 ( std::vector<bool> )，其 const_iterator 和 iterator 无法满足此要求。我知道有 a point of view that "std::vector<bool> IS NOT a Container" ，但我更倾向于认为引用的要求过于严格，而不是完全同意这种观点。

关于c++ - 是否可以编写符合标准的随机访问(或至少向前)整数迭代器？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38675445/