1-based arrays and pointer arithmetic
Bjarke Hammersholt Roune
index 1 instead of 0. If p points to a usual 0-based C++ array, then q
= p - 1 will act as a 1-based array since p[0] can be accessed as
q[1]. However now q points outside the allocated array and it is not
one past the end. It is my understanding that this implies that just
computing the value p - 1 invokes undefined behavior. Is that true? If
so, how likely am I to ever run into a problem by implementing a 1-
based array using this technique anyway? Also, is there a good
rationale for the standard to disallow this technique?
If you are wondering why I need a 1-based array; I am implementing a
binary heap, and the formulas for navigating a binary heap become more
efficient if indexes for the underlying array start at 1 instead of 0.
I could use a 0-based array and just leave the first element unused,
but I much prefer the cleaner q = p - 1 solution if it is available.
--
[ comp.std.c++ is moderated. To submit articles, try posting with your ]
[ newsreader. If that fails, use mailto:std-cpp...@vandevoorde.com ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Daniel Krügler
On 2011-07-01 10:46, Bjarke Hammersholt Roune wrote:
>
> I need a 1-based array, i.e. an array where the first element is at
> index 1 instead of 0. If p points to a usual 0-based C++ array, then q
> = p - 1 will act as a 1-based array since p[0] can be accessed as
> q[1]. However now q points outside the allocated array and it is not
> one past the end. It is my understanding that this implies that just
> computing the value p - 1 invokes undefined behavior. Is that true?
I'm not exactly sure what you are trying to do, but assuming you do
the following:
int p[4];
int* q = p - 1;
This would indeed invoke undefined behaviour, because p - 1 (which is
equivalent to &p[-1]) does not refer to an address in the range [p +
0, p + 4).
> If
> so, how likely am I to ever run into a problem by implementing a 1-
> based array using this technique anyway? Also, is there a good
> rationale for the standard to disallow this technique?
The rationale is that some architectures don't like it, if you try to
refer to an address before an initial boundary.
> If you are wondering why I need a 1-based array; I am implementing a
> binary heap, and the formulas for navigating a binary heap become more
> efficient if indexes for the underlying array start at 1 instead of 0.
> I could use a 0-based array and just leave the first element unused,
> but I much prefer the cleaner q = p - 1 solution if it is available.
I would suggest that you just define a wrapper structure that performs
the index mapping, e.g.:
template<class T, ptrdiff_t IndexOffset = 0>
class ArrayReference {
T* addr;
public:
template<size_t M>
explicit ArrayReference(T (&array)[M]) : addr(array) {}
T& operator[](ptrdiff_t idx) const {
return addr[idx - IndexOffset];
}
};
Several changes are possible, including the option to allow for
constructing an ArrayReference object directly from a T*.
This realizes what you want without unnecessary provoking undefined behaviour.
HTH & Greetings from Bremen,
- Daniel Krügler
Francis Glassborow
On 01/07/2011 09:46, Bjarke Hammersholt Roune wrote:
>
> I need a 1-based array, i.e. an array where the first element is at
> index 1 instead of 0. If p points to a usual 0-based C++ array, then q
> = p - 1 will act as a 1-based array since p[0] can be accessed as
> q[1]. However now q points outside the allocated array and it is not
> one past the end. It is my understanding that this implies that just
> computing the value p - 1 invokes undefined behavior. Is that true? If
> so, how likely am I to ever run into a problem by implementing a 1-
> based array using this technique anyway? Also, is there a good
> rationale for the standard to disallow this technique?
>
> If you are wondering why I need a 1-based array; I am implementing a
> binary heap, and the formulas for navigating a binary heap become more
> efficient if indexes for the underlying array start at 1 instead of 0.
> I could use a 0-based array and just leave the first element unused,
> but I much prefer the cleaner q = p - 1 solution if it is available.
>
>
In what sense is q=p-1 cleaner than just declaring the array with a
dimension of n+1 and then ignoring element 0?
That seems clean ot me and, as you are concerned about efficiency,
efficient as well. You have bought efficiency for your algorithms
(assuming this is actually the case -- it surprises me a bit) At the
cost of wasting storage for a single element. Note that you never then
have to compute p-1. The problem with that computation is that if ever
a zero value is used for q you are in deem trouble. Do not risk
accidents unless there is no reasonable alternative.
Finally, this is C++ so you are free to define an array class type
(not called array because C++0x has such a type) and provide pointer
like functionality for it. That will be fine and potentially efficient
as long as you are also implementing the code that uses it.
While writing the above, it struck me that you should probably be
implementing your heap management as a class. Now you can hide away
all the potentially risky stuff in private members. Nonetheless I
think I would still use an n+1 array and ignore element 0.
Francis