Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!news.alt.net From: Francis Glassborow Newsgroups: comp.std.c++ Subject: Re: 1-based arrays and pointer arithmetic Date: Sat, 2 Jul 2011 01:16:57 CST Organization: unknown Lines: 52 Sender: std-cpp-request@vandevoorde.com Approved: james.dennett@gmail.com Message-ID: References: Content-Type: text/plain; charset=ISO-8859-1; format=flowed To: undisclosed-recipients:; Return-Path: X-Original-Date: Fri, 01 Jul 2011 11:37:39 +0100 X-Submission-Address: std-c++-submit@vandevoorde.com Xref: x330-a1.tempe.blueboxinc.net comp.std.c++:191 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 ]