CODEWITHSUNDEEP
c++undefined-behavior
tbleher
tbleher

Reputation: 1115

Check whether pointer points to vector element

I'd like to have a function to check whether a pointer points to an element of a vector:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr);

The function is a helper function for safely creating an iterator from a pointer:

template <typename T>
std::vector<T>::iterator toIterator(std::vector<T>& vec, T* ptr)
{
    assert(pointsToElement(vec, ptr));
    return vec.begin() + (ptr - &vec[0]);
}

The "obvious" way would be something like:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    if (vec.empty())
        return false;
    return ptr >= &vec.front() && ptr <= &vec.back();
}

Unfortunately, this seems to invoke undefined behavior, since it may compare pointers to different objects.

A safe way would be:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    for (auto& elem : vec) {
        if (&elem == ptr)
            return true;
    }
    return false;
}

But this of course is O(N), so very undesirable.

I can imagine one other way:

template <typename T>
bool pointsToElement(const std::vector<T>& vec, const T* ptr)
{
    if (vec.empty())
        return false;
    intptr_t pos   = reinterpret_cast<intptr_t>(ptr);
    intptr_t begin = reinterpret_cast<intptr_t>(&vec.front());
    intptr_t end   = reinterpret_cast<intptr_t>(&vec.back());
    return pos >= begin && pos <= end;
}

I don't think the standard guarantees any ordering on inptr_t, but this should at least not invoke any undefined behavior and produce the correct results on major platforms (I'm only concerned about Linux and Windows at the moment).

Is this analysis correct? Is there any better way to check whether a pointer falls within a certain range?

(Note: there are a few similar questions, but none considers the possibility of using a cast to intptr_t).

Upvotes: 2

Views: 1492

Answers (2)

super
super

Reputation: 12928

This is one of the situations where std::less and std::greater comes in handy.

A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not. The strict total order is consistent among specializations of std::less, std::greater, std::less_equal, and std::greater_equal for that pointer type, and is also consistent with the partial order imposed by the corresponding built-in operators (<, >, <= and >=).

With these guarantees you can use your "obvious" solution.

DavisHerring pointed out in the comments that there can be architectures with segmented memory layouts where an unrelated pointer could be ordered between two vector elements and still conform to the strict total order.

Upvotes: 4

Klaus
Klaus

Reputation: 25613

First of all:

If you need to check if a pointer is valid, you have a general design problem! You have to think who owns data and how long pointers to this data are valid.

For your idea to build a function which "check" that a pointer points to an element of a vector:

    template < typename T>
bool check( const std::vector<T>& vec, const T* ptr )
{   
    const T* start = vec.data();
    const T* end = start + vec.size();

    std::cout << start << " " << end << " " << ptr << std::endl;

    // this did NOT check if pointer points to start of a element boundary!
    if (( ptr >= start ) && ( ptr < end ))
    {   
        return true;
    }

    return false;
}

int main()
{
    std::vector<int> vec{0,1,2,3,4,5};

    std::cout << check( vec, &vec[0]) << std::endl;
    std::cout << check( vec, &vec[5]) << std::endl;
    std::cout << check( vec, &vec[6]) << std::endl;
}

But what will this help?

If your pointer was a assigned to some element of a vector and later on the vector reallocates some times, it is possible that it is again on that place but shifted some elements away.

In general: If your design can result in dangling pointers it makes no sense to do any later runtime checks. A broken design can not be fixed by later on runtime checking! Your program has still "undefined behavior!"

Upvotes: 1

Related Questions