I am working with some code that checks if std::vector contains a given element in constant time by comparing its address to those describing the extent of the vector's data. However I suspect that, although it works, it relies on undefined behaviour. If the element is not contained by the vector then the pointer comparisons are not permitted.

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

Am I right in believing it is undefined behaviour? If so, is there any way to do the same thing without drastically changing the time complexity of the code?

CodePudding user response：

You can use 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.

CodePudding user response：

Yes, the comparisons as written are not permitted if the reference doesn't reference something that is already an element of the vector.

You can make the behavior defined by casting all pointers to uintptr_t and comparing those. This will work on all architectures with continuous memory (i.e. possibly not old 16-bit x86), although I don't know if the specific semantics are guaranteed.

As a side note, I would always interpret the name contains to be about the value, and thus be very surprised if the semantics are anything other than std::find(v.begin(), v.end(), a) != v.end(). Consider using a more expressive name.