为什么 `std::input_iterator` 需要 `value_type`？

Question

我正在尝试为动态大小的数组创建一个数据结构。可以有多种选择，最简单的一种是 std::vector>。然而它通常效率不高，我们希望将所有内部向量的数据压缩成一个大的向量，并有一个偏移向量来告诉每个元素从哪里开始。

示例：

  // encoding of : | 4.,5.,1. | 7.,8.,9.,2 |
  std::vector<double> v    = {4.,5.,1., 7.,8.,9.,2};
  std::vector<int> offsets = {0       , 3         , 7};

让我们封装它！考虑以下数据结构：（

注意：代码既不完整、通用也不精确，此时这只是为了说明正在发生的事情）：

  class vblock_vector {
    private:
      std::vector<double> v;
      std::vector<int> offsets;

    public:
      using iterator = vblock_iterator;
      auto begin() -> iterator {
        return {v.data(),offsets.data()};
      }
      auto end() -> iterator {
        return {v.data(),offsets.data()+offsets.size()};
      }
  };

迭代器类型的基本实现如下：

  struct vblock_iterator {
    private:
      double* ptr;
      int* offsets_ptr;

    public:
      using reference = span_ref<double>; // see notes (0) and (1)
      // using value_type = ???; // See below

      auto operator++() {
        ++offsets_ptr;
        return *this;
      }
      auto operator*() const {
        return span_ref<double,int>(ptr+offsets_ptr[0],ptr+offsets_ptr[1]);
      }
      auto operator<=>(const vblock_iterator&) const = default;

      // ... other iterator interface stuff that is trivial
  };

此迭代器可与例如 std::copy 配合使用。 (4)

现在假设我想用 std::ranges::copy 替换旧的 std::copy 调用。为此，vblock_iterator 需要满足 std::input_iterator 概念。为了做到这一点，vblock_iterator需要有一个关联的value_type（中间std::indirectly_read 概念）。

一个明显的选择是使用 value_type = std::vector(2)，但我肯定不想给出 std::ranges: :copy 在其实现中自行决定使用此类型的自由：这将是低效的。

我的问题如下：为什么 std::input_iterator 需要 In 具有 value_type？至少对于复制来说不需要它（我可以使用 std::copy 并且它做正确的事情证明了这一点）。当然，有人可以说：“将 value_type 定义为任何内容，无论如何它都不会被 std::range::copy 实现使用”，但是为什么需要它？

我目前的印象是 value_type 对于例如 std::swappable 是强制性的，但对于 std::input_iterator 不是强制性的（甚至也不是 >std::random_access_iterator 我敢说）。但标准委员会却另有决定：这一选择背后的原因是什么？ (3)

注释：

(0) span_ref 就像一个 std::span 具有引用语义（其 operator= 是“通过分配”而不是“重新绑定到新数组”）。

(1) 实际上，引用类型需要更复杂一点才能考虑偏移量，但这不是这里的主题。可以说，这个结构可以有一个有效的引用类型。

(2) 我认为这是唯一合理的选择。至少需要一个容器（vector、deque...）。例如 std::span 就不行，因为如果我们费心去保存迭代器指向的值，那是因为我们会修改原始内存，而 std::span< /code> 不会帮助我们解决这个问题。

(3) 在演示文稿中关于 std::indirectly_read 概念（后来称为 Readable），Eric Niebler 详细介绍了为什么我们需要value_type 以某种形式与 reference 相关，以便与代理引用很好地配合使用，但我仍然不明白为什么我们甚至需要 value_type > 对于不需要交换元素（或将它们存储在某处）的算法。是的，在数学上，vblock_iterator 存在一个 value_type，但如果不打算使用它，为什么需要它呢？ （类似地，也有数学operator+=用于向前范围：但由于它效率低下，所以根本不需要）。

(4) 以及其他算法：std::move、std::find、std::find_if、 std::any_of、std::partition_point、std::lower_bound、std::unique...所以我认为有一些东西更根本的事情比：“我们只是幸运地拥有 std::copy”。

Answer 1

std::copy 需要 LegacyInputIterator 其迭代器类型。 它不会检查此要求。如果您未能提供 LegacyInputIterator，则您的程序格式错误，无需进行诊断。

LegacyInputIterator 要求 std::iterator_traits::value_type 存在，因为它包含 LegacyIterator。

因此，一旦您将程序传递给 std::copy，您的程序就格式不正确。格式错误的程序的行为无论如何都不是由 C++ 标准决定的；编译器可以合法地为您提供一个程序，将您的浏览器历史记录通过电子邮件发送给您的尤斯蒂斯阿姨，并且符合标准。或者它可以做一些恰好与您认为程序“应该”做的事情一致的事情。否则可能无法编译。

std::ranges 算法的要求略有不同。与旧式算法相比，这些要求更有可能通过概念进行检查，并告诉用户编译时错误。

你就遇到了这样的情况。

更清楚地说，您不能依赖 std 代码的实现来强制执行该标准。

需要这些类型的部分原因是为了更容易地讨论相关类型以及对它们的操作在语义上的含义。

除了诸如 std::iterator_traits::value_type 之类的简单要求之外，还存在关于 *it 的作用、x = *it++< 的语义要求/code> 确实如此，等等。大多数这些要求无法被编译器检查（由于莱斯定理，理论上它们无法检查）；但是 std 命名空间中的算法依赖对于传入的任何迭代器来说这些语义都是正确的。

因为编译器可以假设语义是正确的，所以算法可以更清晰，比检查更简单、更快。这意味着多个不同的编译器供应商可以编写不同的 std 算法实现，相互改进算法，并且有一个客观的标准可以争论。

对于 LegacyInputIterator 以及来自 std::iterator_traits 的 value_type 和 reference 类型，我们必须

value_type v = *it;

：一个有效的表达式，*it 必须返回 reference，并且

*it++

必须返回可转换为 value_type 的类型。

并非每个算法都需要使用它要求迭代器具有的每个迭代器的每个属性。这里的目标是拥有语义上有意义的类别，并且不需要太多的开销。

要求东西上的迭代器实际上有一个它是迭代器的类型并不是一个很大的开销。这使得谈论迭代器变得非常容易。

您可以重构它并删除该概念，或者将概念分割成更小的部分，以便仅在需要时才需要 value_type ，但这会使概念更难编写并且更难理解。