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?
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.
Update:
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.
As pointed out in the comments, the standard only guarantees that std::less yields the implementation-defined strict total order, which is is consistent with the partial order imposed by the builtin operators. However, the standard doesn't guarantee the order of pointers pointing to different objects or arrays. Releated: https://devblogs.microsoft.com/oldnewthing/20170927-00/?p=97095
One interesting thing is that there's a similar usage in Herb Sutter's gcpp library(link). There's a comment saying that it is portable, the library is experimental though.
// 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());
}