常量时间“包含”为“std：：vector”？[重复]

Question

我正在使用一些代码，通过将 std：：vector 的地址与描述向量数据范围的地址进行比较来检查 std：：vector 是否在常量时间内包含给定元素。然而，我怀疑，尽管它有效，但它依赖于未定义的行为。如果向量不包含该元素，则不允许指针比较。

bool contains(const std::vector<T>& v, const T& a) {
  return (v.data() <= &a) && (&a < v.data() + v.size());
}

我是否认为这是未定义的行为？如果是这样，有没有办法在不大幅改变代码的时间复杂度的情况下做同样的事情？

Answer 1

是的，如果引用没有引用已经是向量元素的内容，则不允许进行所写的比较。

您可以通过将所有指针强制转换为uintptr_t并进行比较来定义行为。这将适用于所有具有连续内存的架构（即可能不是旧的 16 位 x86），尽管我不知道是否保证了特定的语义。

作为旁注，我总是将名称包含解释为关于值，因此如果语义不是 std：：find（v.begin（）， v.end（）， a） ！= v.end（） ，我会感到非常惊讶。考虑使用更具表现力的名称。

Answer 2

你可以使用 std：：less

对于任何指针类型，std：：less 的专用化都会产生实现定义的严格总顺序，即使内置的

更新：

不过，该标准并不能保证这实际上适用于包含。如果你有两个向量 a 和 b，则允许总订单为

正如注释中指出的，该标准仅保证 std：：less 产生实现定义的严格总序，这与内置运算符强加的偏序一致。但是，该标准不保证指向不同对象或数组的指针的顺序。相关：https://devblogs.microsoft.com/oldnewthing/20170927-00/?p=97095

有趣的是，在Herb Sutter的gcpp库（链接）中也有类似的用法。有评论说它是便携式的，但该库是实验性的。

    //  Return whether p points into this page's storage and is allocated.
    //
    inline
    bool gpage::contains(gsl::not_null<const byte*> p) const noexcept {
        //  Use std::less<> to compare (possibly unrelated) pointers portably
        auto const cmp = std::less<>{};
        auto const ext = extent();
        return !cmp(p, ext.data()) && cmp(p, ext.data() + ext.size());
    }