Check whether pointer points to vector element

Question

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).

`intptr_t` is not your friend: you have _fewer_ guarantees with comparing it than with comparing normal pointers. For example, it's not even guaranteed that a single pointer will reliably convert to a single integer (but all such integers must [convert back to the same pointer](http://eel.is/c++draft/expr.reinterpret.cast#5)). — Davis Herring, Jun 18 '18 at 00:40
@DavisHerring it's intended that `uintptr_t` have a natural mapping to integers — M.M, Jun 18 '18 at 00:56
Of course it's intended: paragraph 4 says so. And it's implementation-defined, not unspecified, so your implementation might very well say it's good and obvious. But that doesn't make `intptr_t` an improvement over the built-in pointer comparisons, which are _unspecified_, not _undefined behavior_. — Davis Herring, Jun 18 '18 at 02:12
@DavisHerring Thanks for the correction. I thought that comparing unrelated pointers is undefined behavior, but per https://stackoverflow.com/questions/31774683/is-pointer-comparison-undefined-or-unspecified-behavior-in-c only substracting unrelated pointers is UB, and comparing them is merely unspecified behavior. Correct? — tbleher, Jun 18 '18 at 08:55
Yes, that's [expr.add/5](http://eel.is/c++draft/expr.add#5), which also includes the unfortunate case of subtracting pointers that are too far apart in the same array (normally only possible for `char*`). — Davis Herring, Jun 18 '18 at 13:03

super · Answer 1 · 2018-06-18T00:48:50.660

4

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.

edited Jun 18 '18 at 00:48

answered Jun 16 '18 at 08:08

super

12,335
2
19
29

What stops that total order from including an unrelated pointer between two elements of the `vector`? – Davis Herring Jun 18 '18 at 00:08
@DavisHerring A vector stores it's data in contiguous memory, so there can be no unrelated pointer between two elements. – super Jun 18 '18 at 00:16
Of course a vector is contiguous -- but a pointer to an unrelated object is not ordered by the built-in operators, so nothing restricts its position in the total order to not lie between the elements. – Davis Herring Jun 18 '18 at 00:17
@DavisHerring I'm re-reading the quote, and I think theoretically you are right (depending on how you interpret it). I don't see how that would make sense in any implementation of said total order though. Finding relevant paragraphs in the standard might give more detailed definition. – super Jun 18 '18 at 00:31
That is the relevant paragraph (along with, trivially, [expr.rel/3.3](http://eel.is/c++draft/expr.rel#3.3)). It is meant to support segmented architectures where pointer comparison might involve analyzing control registers and page tables. – Davis Herring Jun 18 '18 at 00:37
@DavisHerring I added an edit for it. Feel free to edit it for clarity. – super Jun 18 '18 at 00:49

Klaus · Answer 2 · 2018-06-16T08:41:19.097

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!"

There are some cases where it can make sense to have pointers which are recognizable as either identifying a shared object of effectively static duration or an unshared allocated one. For example, a function might usually return one of four strings, but sometimes return something completely different. While it would be possible to have the function always return a newly-allocated string, it may be much more efficient to handle the common case by returning a string from a common pool and having the destructor refrain from freeing strings in that pool. — supercat, Jun 16 '18 at 18:00
Caution: your check() function invokes undefined behavior if ptr is outside of vec, so a compiler could rightfully replace the function content with "return true". The goal of my code was to have an efficient debug check to catch errors early, which is valuable, even if it doesn't catch all errors. — tbleher, Jun 17 '18 at 20:44
@tbleher: "your check() function invokes undefined behavior if" Why? Can you explain what my code breaks? Thanks! — Klaus, Jun 18 '18 at 18:18

Check whether pointer points to vector element

2 Answers2