Author: Bjarke Hammersholt Roune <bjarke.roune@gmail.com>

Date: Fri, 1 Jul 2011 02:46:57 CST

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

Author: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= <daniel.kruegler@googlemail.com>

Date: Sat, 2 Jul 2011 01:16:21 CST

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 ]

Author: Francis Glassborow <francis.glassborow@btinternet.com>

Date: Sat, 2 Jul 2011 01:16:57 CST

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 ]