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

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

Re: 1-based arrays and pointer arithmetic

Show all headers | View raw

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



--
[ 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 | 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