1

If a pointer p has been created as a dynamic array

double* p = new double[n]

a pointer q is said to point to the array referenced by p if q has been defined as q = p + k with 0 <= k < n. Is there a way to know if a given pointer q points to the array of length n referred by p with O(1) operations?

remark: the test (q >= p && q < p + n) has undefined behaviour.

remark: the question 'How do I safely and sensibly determine whether a pointer points somewhere into a specified buffer?' does provide an answer that is O(1) on gcc but not on every compiler. But it seems that there is no better answer.

InsideLoop
  • 6,063
  • 2
  • 28
  • 55
  • If you want `0 <= k < n` (rather than `<=`), [I asked that question here](http://stackoverflow.com/questions/27766570/how-do-i-safely-and-sensibly-determine-whether-a-pointer-points-somewhere-into-a). As simple as the question seems, the answer is actually very complicated. If you do mean `0 <= k <= n`, then you could adapt the code there to cover the `k == n` case too. –  Feb 22 '15 at 23:24
  • Re. "remark": it's unspecified in C++11 and later – M.M Feb 22 '15 at 23:32
  • C++14 adds a stricter condition (although still not strict enough for what you need): "Otherwise, if a pointer p compares greater than a pointer q, p>=q, p>q, q<=p, and q

    =p, and q>p all yield false"

     – M.M Feb 22 '15 at 23:35
  • Closed as a duplicate now that you changed the question so that it is an exact duplicate of my question. My answer there is conceptually O(n), but O(1) at run-time on GCC when optimisations are enabled. That's the best you can get in standard C++. –  Feb 22 '15 at 23:35
  • Agreed that my answer there is not guaranteed O(1) (and actually, on some current popular optimising compilers does not compile to something that runs in constant time), but sorry, C++ just doesn't have anything better. I was looking for something that runs in O(1) as well. –  Feb 22 '15 at 23:52

0 Answers0