c++ - 自定义迭代器中 distance_type 的目的 - std::distance(first, last) 将返回错误结果，如果 first 和 last 距离太远

Question

我想为自定义类实现一个迭代器

template</*...*/>
class foo
{
public:
    using value_type = /* depends on template parameters */;
    using size_type = /* depends on template parameters */;

    class iterator
        : public std::iterator<std::random_access_iterator_tag, value_type, /* some suitable difference_type compatible to size_type */>
    {
    public:
        iterator(foo& bar, size_type i)
            : m_bar(bar), m_i(i),
              m_dereferenceable(i != bar.size())
        { }

    private:
        foo& m_bar;
        size_type m_i;
        bool m_dereferenceable;
    };

    size_type size() const { /* ... */ }
    value_type operator[](size_type) { /* ... */ }
};

想知道我应该如何实现 operator+=(difference_type) .我已经定义了 difference_type成为std::make_signed_t<size_type>因为这对我来说非常有意义。

关键点是以下几点:我认为定义 m_i 是合理的类型为 size_type , 确保其值被限制在 [0, m_bar.size()]并使用标志 m_dereferenceable处理 iterator 的情况与 m_i == 0递减。

这有点复杂，如果我改变 m_i 的类型，一切都会更容易。到签名类型 difference_type .但是，如果 m_bar，那将阻止我遍历整个范围。的大小正在开发全系列size_type .

现在，我意识到(例如)std::distance的返回类型是 difference_type .一方面，这是合理的，因为我们可能有负距离。另一方面，如果 m_bar的大小正在开发全系列size_type , std::distance可能会返回错误的结果。

So, the question is: Taking in mind that (for example) std::distance might return wrong results, if I define m_i to be of type size_type, should I simply use difference_type instead (and benefit from an easier implementation)?

---

编辑:让我强调以下几点:假设我们有一个 vector x与 vector = std::vector</* ... */>并执行 x.resize(std::numeric_limits<vector::size_type>::max()) .

由于 d = std::distance(x.begin(), x.end()) 的类型是vector::difference_type和 s = x.size() 的类型是vector::size_type ，我很好奇是否d将等于 s .

这个问题不是关于 vector 的, 这是一个关于 size_type 的整个概念的问题, 一个 difference_type以及它们作为迭代器的用途。

请忽略任何技术问题(内存寻址等)并考虑 size_type作为“复杂的东西”(即人们对“大小”表示的理解的抽象)。

很明显，d必须是有符号类型，因为我们可能有负距离。当然，我能想到阻止标准保证 difference_type 的技术问题。对象必须能够存储 size_type目的。但由于 STL 完全是关于泛型编程的，所以我很惊讶。

Answer 1

您应该知道 size_type 和 difference_type 只是容器分配器的类型定义或迭代器自己的类型定义。它们与载体本身完全无关。

除此之外，我认为您从整体上考虑过度了。 size_type 和 difference_type 是两种概念上不同的类型:

差异类型:
表示序列中任意两个元素地址之差的有符号整数类型

尺寸类型:
表示序列长度的无符号整数类型

每当您使用返回这些类型之一的函数时，它们都会返回一个与其定义一致的值。使用 std::distance，您真的找到了容器的大小吗？不，您正在寻找两个迭代器之间的区别。使用 std::size 你没有发现迭代器之间的任何差异，你正在检索一个应该具有逻辑意义的值，一个 unsigned 整数类型，它将代表容器。这只是比返回 signed 类型更好的表示，如您所知，容器的长度始终为正数。

因此，您可以仅使用 difference_type，毕竟您始终能够使用 std::distance 安全地计算容器的大小。

但是你应该吗？

size_type 只是 unsigned difference_type 的表示。仅此而已，它只是保证能够保存一个表示容器大小的值。

判决

您可以少打字并从代码中省略 size_type，但我强烈建议您不要这样做。它是标准的一部分，并且合乎逻辑。当您计算两个对象的差异时，结果必须能够处理负数，但大小永远不会有这个问题，所以为什么要将它定义为 signed。