指针相减的结果存储

Question

通常指针相减的结果应该是std::ptrdiff_t，它是一个有符号的类型。然而：

如果一个数组太大（大于PTRDIFF_MAX个元素，但小于SIZE_MAX字节），两个指针之间的差值可能无法表示为std::ptrdiff_t，所以从这样的指针中减去另外一个指针的结果是不确定的。

为了避免进入未定义行为的领域，是否有另一种类型可以在不担心溢出的情况下合法地存储指针减法操作的结果（按照标准意图的术语，而不是特定/常见实现的术语）？

特别地，是否有任何保证表明std::size_t或std::uintptr_t适合存储这样的操作结果，而不会发生溢出、下溢或未定义行为（假设在表达式a-b中，a比b大，以防止下溢）？

- Pharap

---

表达式 a - b 必须在编译时具有某种类型。它不能是 "ptrdiff_t 如果 a < b 或者 a 足够接近 b 以至于不会溢出 ptrdiff_t，否则就是 size_t"，因为条件只能在运行时评估。 - Igor Tandetnik

有趣的问题。如果std::distance应该返回“从第一个到最后一个的跳数”，那么libcxx中是否存在“错误”？ - Julius

Answer 1

虽然我不是语言专家，但我有两个想法可以在理论上计算出两个合适指针之间的“距离”。

1. 逐一计算指针之间的跳数
2. 使用std::less和其他相关函数，以获得更多关于总序列的保证（GCC确实会考虑）

这在理论上有所帮助，因为逐一增加跳数效率太低。请注意，线性成本最大的情况是std::ptrdiff_t不足时。

#include <cassert>
#include <cstddef>

#include <functional>

template<class T>
constexpr std::size_t generalized_distance(T* first, T* last) {
// prefer `std::less_equal(first, last)` over `first <= last` because
// > it yields a strict total order even if the built-in operator<= does not
// (https://en.cppreference.com/w/cpp/utility/functional/less_equal)
  assert(std::less_equal{}(first, last));

  std::size_t number_of_hops = 0;
// `last` might be "one past the end" so let us be sure and increment one by one
  while(std::less{}(first, last)) {
    ++first;
    ++number_of_hops;
  }
  return number_of_hops;
}

- Julius

---

我不确定那会如何有所帮助。如果指针算术存在基本的平台限制，多次增加指针可能无法避免该限制，这正是你使用 ++first; 所做的。 - Andrew Henle

在可能超过 2^31（更不用说 2^63）的情况下，逐一计算跳数可能会显得相当低效。因此，我们可以说。 - Igor Tandetnik

如果实现通过减法防止计算两个指针之间的差异，为什么您认为可以通过重复递增其中一个指针来计算该差异？它们都在执行相同的基本算术指针操作并且作用于相同的对象。如果递增直到它们相等是有效的，那么减法也是有效的。然而，实现已经有了限制，使得该减法无效。在这种实现中，您提出的方法根本是有缺陷的，它生成的任何结果都可能是完全无效的。 - Andrew Henle

@Julius，减法的定义就是计算X和Y之间增量的数量。如果减法无效，增量的计数也是无效的。 - Andrew Henle

@Julius，这就是说注意：如果i-j的值不在std::ptrdiff_t类型的可表示值范围内，则行为是未定义的。 这正是我一直在说的-如果存在某种奇异的实现，使得两个指针的减法导致未定义的行为，你不能通过将一个指针递增直到与另一个指针相匹配来解决这个问题。这完全属于“数学家和计算机科学家都讨厌的技巧！”的领域。 - Andrew Henle