c++ - `contains` 的恒定时间 `std::vector` ？

Question

这个问题在这里已经有了答案:





How to correcly check whether a pointer belongs within an allocated block?

(1 个回答)


24 天前关闭。




我正在使用一些代码来检查是否 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

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