std::vector的常数时间contains实现是否存在未定义行为？

1. 你的判断是正确的，该实现确实存在未定义行为 #

C++标准明确规定：只有指向**同一个数组（包括数组末尾后一个虚地址）**的指针，才能使用<、<=、>、>=这类关系运算符比较。如果两个指针分别指向不同的独立对象，这类比较的结果是未定义的。
你观察到的“可运行”只是主流编译器（GCC、Clang、MSVC）在x86/ARM等平坦内存模型架构下的兼容实现，标准并没有对这种行为做任何保证，一旦切换到分段内存架构、或者开启高等级优化，编译器可能基于“不会跨对象比较指针”的假设优化掉判断逻辑，直接得到错误结果。

2. 常数时间复杂度的标准兼容实现方案 #

如果你的需求确实是判断某个元素的地址是否属于vector的连续存储区间（不是判断值相等，和std::find的逻辑完全不同），可以用标准库提供的通用比较函数替代原生关系运算符，不需要改动时间复杂度：

• 兼容C11及以上版本的实现：
  C标准明确要求std::less、std::greater_equal等函数模板对任意指针类型的比较都具备明确定义的全序结果，即使指针指向不同对象，也能按内存地址正常比较，编译后和原生指针比较的性能完全一致，没有额外开销：

  #include <functional>
  #include <vector>
  
  template<typename T>
  bool contains(const std::vector<T>& v, const T& a) {
      const T* buf_begin = v.data();
      const T* buf_end = v.data() + v.size();
      return std::greater_equal<const T*>()(&a, buf_begin) 
          && std::less<const T*>()(&a, buf_end);
  }
  

• C++20及以上版本还可以用更简洁的std::cmp_less系列比较函数，效果完全一致：

  #include <utility>
  #include <vector>
  
  template<typename T>
  bool contains(const std::vector<T>& v, const T& a) {
      const T* buf_begin = v.data();
      const T* buf_end = v.data() + v.size();
      return std::cmp_greater_equal(&a, buf_begin) 
          && std::cmp_less(&a, buf_end);
  }
  

注意：如果你的实际需求是判断vector中是否存在和a值相等的元素，那原本的判断逻辑本身就是错误的，和未定义行为无关。这种场景如果需要O(1)查询，可以提前把vector元素存入std::unordered_set做预处理，后续查询的时间复杂度为常数级别。

内容的提问来源于stack exchange，提问作者Richard Forrest