是否包含`std：：Vector`的常量时间`？ [英] Constant time `contains` for `std::vector`?

问题描述

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

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

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

推荐答案

您可以使用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库中也有类似的用法(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`的常量时间`？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！