Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

If Off-The-End Pointers Are Useful, Why Not Off-The-Beginning Pointers?

May 28, 2014

Last week, I discussed off-the-end pointers, and explained why they greatly simplify the task of processing every element of an array. One important way in which programmers can make their lives easier is by generalizing, otherwise known as reducing the number of exceptional cases to consider. One important kind of generalization is symmetry — the notion that, where possible, it should be possible to work in reverse order. So, for example, if a library has a function that finds the first element of a sequence that has a particular property, it should also have a function that finds the last element of a sequence with that property; and so on.

If we use symmetry to generalize the idea of off-the-end pointers, we come up with the idea of off-the beginning pointers. Having done so, we find it reasonable to ask why C and C++ do not usually support such pointers, and whether the languages should do so. To answer that question, let's sketch out a design and see if we can understand the advantages and disadvantages of that design.

Using symmetry as a design principle makes the details easy: Every array should support an off-the-beginning pointer that points immediately before the first element; as with off-the-end pointers, deferencing an off-the-beginning pointer should yield undefined behavior. Just as we can use pointers to step forward through an N-element array with elements of type T:

 
     T *p = &array[0];
     T *q = &array[N];
     while (p != q) {
           // Do something with the element at *p
           ++p;
     }

we should be able to use pointers, including an off-the-beginning pointer, to step backward through the same array:

 
     T *p = &array[N-1];
     T *q = &array[-1];
     while (p != q) {
           // Do something with the element at *p
           --p;
     }

The advantages of being able to write code in this style should be obvious. In particular, having an off-the-beginning pointer makes it easy to take code that marches forward through an array and turn it into code that does so in the opposite order.

The disadvantages are less obvious, but more serious. Let's start with the first two statements of each example. Notice how each example uses completely different values? Suppose, for example, that instead of an array, we want to use two pointers to delineate a sequence of elements. Following the C++ library conventions, we might call those pointers begin and end, with the usual rule that begin refers to the first element (if any) and end is an off-the-end pointer. Then we would step forward through the sequence of elements this way:

 
     T *p = begin;
     T *q = end;
     while (p != q) {
           // Do something with the element at *p
           ++p;
     }

To step through the same elements backward, we would have to write the code this way:

 
     T *p = end-1;
     T *q = begin-1;
     while (p != q) {
           // Do something with the element at *p
           --p;
     }

This tactic of subtracting 1 from each of the bounds is hardly symmetric! Moreover, it does two unnecessary computations, which we can avoid this way:

 
     T *p = end;
     T *q = begin;
     while (p != q) {
           --p;
           // Do something with the element at *p
     }

By changing the loop so that it decrements p at the beginning rather than at the end, we can avoid both of those extra subtractions. Moreover, we have simplified the code in an important way: Now, the same bounds, begin and end, can stand for the same sequence of elements regardless of direction. We merely have to remember to swap the bounds (which we would have had to do anyway) and decrement at the beginning of the loop rather than at the end. Of course, we must also remember to change the increment to a decrement, but we had to remember to do that anyway.

While we were making these changes, an odd thing happened: We stopped having any need for the off-the-beginning pointer! This last code example still uses the off-the-end pointer, but it no longer computes the off-the-beginning pointer begin-1. Somehow, even though symmetry is usually a simplifying principle, this particular code became simpler by disregarding the principle of symmetry. We shall have more to say about this odd situation next week.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video