Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.std.c++ > #189

Re: 1-based arrays and pointer arithmetic

Show all headers | View raw

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



--
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Back to comp.std.c++ | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

1-based arrays and pointer arithmetic Bjarke Hammersholt Roune <bjarke.roune@gmail.com> - 2011-07-01 02:46 -0600
  Re: 1-based arrays and pointer arithmetic Daniel Krügler <daniel.kruegler@googlemail.com> - 2011-07-02 01:16 -0600
  Re: 1-based arrays and pointer arithmetic Francis Glassborow <francis.glassborow@btinternet.com> - 2011-07-02 01:16 -0600

csiph-web