`std::vector` 的常数时间`contains`？

Question

我正在使用一些代码来检查 std::vector 是否在恒定时间内包含给定元素，方法是将其地址与描述 vector 数据范围的地址进行比较。但是我怀疑，尽管它有效，但它依赖于未定义的行为。如果 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），尽管我不知道是否可以保证特定的语义。

附带说明一下，我总是将名称 contains 解释为与值有关，因此非常如果语义不是 std::find(v.begin(), v.end(), a) != v.end()。考虑使用更具表现力的名称。

Answer 2

您可以使用std::less

A specialization of std::less for any pointer type yields the implementation-defined strict total order, even if the built-in < operator does not.

更新：

The standard doesn't guarantee that this will actually work for contains though. If you have say two vectors a and b, the total order is permitted to be &a[0], &b[0], &a[1], &b[1], &a[2], &b[2], ..., i.e., with the elements interleaved.

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

一件有趣的事是，在 Herb Sutter 的 gcpp 库 (link) 中也有类似的用法。有评论说它是可移植的，虽然这个库是实验性的。

    //  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());
    }

`std::vector` 的常数时间`contains`？

Constant time `contains` for `std::vector`?

c++

contains

time-complexity

stdvector

undefined-behavior