checking if pointer points within an array

Question

Can I check whether or not a given pointer points to an object within an array, specified by its bounds?

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return begin <= p && p < end;
}

Or do the pointer comparisons invoke undefined behavior if p points outside the bounds of the array? In that case, how do I solve the problem? Does it work with void pointers? Or is it impossible to solve?

Answer 1

Although the comparison is valid only for pointers within the array and "one past the end", it is valid to use a set or map with a pointer as the key, which uses std::less<T*>

There was a big discussion on this way back in 1996 on comp.std.c++

Answer 2

Straight from the MSDN documentation:

Two pointers of different types cannot be compared unless:

• One type is a class type derived from the other type.
• At least one of the pointers is explicitly converted (cast) to type void *. (The other pointer is implicitly converted to type void * for the conversion.)

So a void* can be compared to anything else (including another void*). But will the comparison produce meaningful results?

If two pointers point to elements of the same array or to the element one beyond the end of the array, the pointer to the object with the higher subscript compares higher. Comparison of pointers is guaranteed valid only when the pointers refer to objects in the same array or to the location one past the end of the array.

Looks like not. If you don't already know that you are comparing items inside the array (or just past it), then the comparison is not guaranteed to be meaningful.

There is, however, a solution: The STL provides std::less<> and std::greater<>, which will work with any pointer type and will produce valid results in all cases:

if (std::less<T*>()(p, begin)) {
    // p is out of bounds
}

Update:

The answer to this question gives the same suggestion (std::less) and also quotes the standard.

Answer 3

The only correct way to do this is an approach like this.

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    for (; begin != end; ++begin)
    {
        if (p == begin)
            return true;
    }
    return false;
}

Fairly obviously, this doesn't work if T == void. I'm not sure whether two void* technically define a range or not. Certainly if you had Derived[n], it would be incorrect to say that (Base*)Derived, (Base*)(Derived + n) defined a valid range so I can't see it being valid to define a range with anything other than a pointer to the actual array element type.

The method below fails because it is unspecified what < returns if the two operands don't point to members of the same object or elements of the same array. (5.9 [expr.rel] / 2)

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return !(p < begin) && (p < end);
}

The method below fails because it is also unspecified what std::less<T*>::operator() returns if the two operands don't point to members of the same object or elements of the same array.

It is true that a std::less must be specialized for any pointer type to yield a total order if the built in < does not but this is only useful for uses such as providing a key for a set or map. It is not guaranteed that the total order won't interleave distinct arrays or objects together.

For example, on a segmented memory architecture the object offset could be used for < and as the most significant differentiator for std::less<T*> with the segment index being used to break ties. In such a system an element of one array could be ordered between the bounds of a second distinct array.

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return !(std::less<T*>()(p, begin)) && (std::less<T*>()(p, end));
}

Answer 4

The C++ standard does not specify what happens when you are comparing pointers to objects that do not reside in the same array, hence undefined behaviour. However, the C++ standard is not the only standard your platform must conform. Other standards like POSIX specify things that C++ standard leaves as undefined behaviour. On platforms with virtual address space like Linux and Win32/64 you can compare any pointers without causing any undefined behaviour.

Answer 5

comparisions on pointer types don't neccesarily result in a total order. std::less/std::greater_equal do, however. So ...

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return std::greater_equal<T*>()(p, begin) && std::less<T*>()(p, end);
}

will work.

Answer 6

Could you not do this with std::distance, i.e. your problem effectively boils down to:

return distance(begin, p) >= 0 && distance(begin, p) < distance(begin, end);

Given this random access iterator (pointer) is being passed in, it should boil down to some pointer arithmetic rather than pointer comparisons? (I'm assuming end really is end and not the last item in the array, if the last then change the less than to <=).

I could be way off the mark...