“std::vector”的恒定时间“包含”？

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

您可以使用std::less

任何指针类型的 std::less 特化都会产生实现定义的严格全序，即使内置 < 运算符不会。

更新：

但该标准并不保证这实际上适用于 contains。如果有两个向量 a 和 b，则总顺序允许为 &a[0], &b[0], &a[1], &b[1], &a[2], &b[2], ... ，即元素交错。

正如评论中指出的，该标准仅保证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());
    }