C++ Pointers: Number of levels of Indirection

Question

In a C++ program that doesn't contain legacy C code, is there a guideline regarding the maximum number of levels of indirection that should be used in the source code? I know that in C (as opposed to C++), some programmers have used pointers to pointers for a multiple dimension array, but for the case of arrays, there are data structures in C++ that can be used to avoid the pointers to pointers.

Are users who still create pointers to pointers (or more than this) trying to use pointers to pointers only for performance ETC. reasons?

I have tried NOT to use any more than a pointer to a pointer, only in the case that a pointer needed modification; does anyone have any other official or unofficial guidelines or rules regarding the number of levels of indirection?

Answer 1

There are no guidelines or any practical limits on indirection. There's no good reason to place a constraint like this unless you're regularly dealing with several levels of indirection in a case indicative of a sloppy design.

That is to say that there are valid cases where 4, 5, 6, or more levels of indirection is to be expected, but these are rare and should not typically appear in your code unless someone has done something terrible, not directly related to the level of indirection being employed.

If you are finding yourself using, say, 3 or more levels of indirection, then you should probably consider whether your architecture needs to be changed.

But does that mean you should never allow more than 3 levels of indirection? Absolutely not. It simply means that it might potentially be an indication that there could possibly be an inherent inefficiency in the architecture of your code. Nothing more. (Do note the deliberate vagueness of that statement: it is a mere possibility of something that could lead to a problem, not necessarily an actual problem.)

Answer 2

Note that a linked list of 42 elements contains 42 levels of indirection for accessing the last element. To get to the element of a one-element list, you use a single indirection: given a pointer to the list, you do something like p->data. To get to the second element, two indirections are required: p->next->data. Each arrow is an indirection. Only, the notation isn't just a row of ****'s. Of course, p->next is really (*p).next. So you could write that as (*(*(*p).next).next).data. If you want to see forty-two asterisks, that can be accomodated.

If the next field of the linked list is at the beginning of the structure, then at the machine level it really is just the equivalent of (***...***p).data, where only the final access to data uses an offset.

And of course, tree structures contain many levels of indirection, particularly if their fan-out is low, such as binary search trees, and particularly if they are allowed to become unbalanced.

Answer 3

According to MISRA C++:2008, rule 5-0-19:

The declaration of objects shall contain no more than two levels of pointer indirection.

Although that's only a declaration restriction. You could still access a variable though any number of indirections.

Answer 4

It is EXTREMELY rare that it is actually a good idea to write code with more than one level of indirection at any given instant.

Part of this is because prudence dictates that you check every pointer for NULL before you dereference it, and that's hard to do if you write more than one level of indirection.

Part of this is because modern processors have complicated data cache, and even more complicated memory allocation schemes, and walking multiple levels of indirection (through long pointer chains) can thrash the holy crap out of the cache.

I have seen processors that can deliver up erroneous results if you thrash the cache in certain ways. (Yes, these are hardware problems. No, the vendor is NOT going to fix them any time soon, and in any case those chips are already out in the field.) I personally fixed a problem, that smelled like one of those, on a processor for which the manufacturer had already warned about issues like this, by rewriting the code to be very careful about locality of references. (I did not do the rewrite because I suspected a thrashed cache. I found out about that issue later. I did the rewrite because the original code was an unreadable pile of spaghetti and pointers to pointers to pointers. I was mildly perturbed when the problem I was chasing just vanished swiftly and silently away.)

AND part of it is because code that is only doing one level of indirection is usually a LOT easier for the poor maintenance schlub to understand.

Answer 5

I once worked for a company that had attempted to analyse and document its business processes, and the way the approach was described to me by the author was that he had written the process documents like computer code, but in English. He was not himself a programmer.

What this meant was that there was extensive use of indirection and cross-references in the documentation, used like procedure calls would be in a programming language. This was done intentionally, to avoid writing redundant information into each document, and the possibility of update anomalies. This was not web-based with hyperlinks, it was paper-based - and as a series of separate documents, not as a bound book with a table of contents.

Unfortunately the number of levels of indirection - usually between half a dozen and a dozen - was unmanageable from a human factors point of view.

Not only unmanageable for the intended audience - trainees and similar - but even for the author. The documentation was actually riddled with circular references, or references left dangling due to the target document being updated without regard to it being a call target. My brief was to suggest ways of improvement.

My suggestion at the time was that one level of indirection would likely make this documentation baffling for new staff, and two levels would give the author no hope of maintaining the referential integrity of his own edifice.

I wonder whether the same rule of thumb is actually close to the truth for programming, that one level of indirection makes navigating the code a skilled job (a thing requiring training and experience in its own right), and two levels is where most codebases (written by average programmers on timescales considered reasonable by management) begin to feature serious defects.

This isn't meant to be taken too literally and without caveat. Simple pure functions that operate on local variables, especially those that implement mathematical operators like Math.Add, don't need to be treated as a layer of indirection. And simple helper methods, like Log.Write are typically safe enough when they do what they say on the tin.

I'm talking about methods that do the heavy lifting of describing and implementing business procedures and operating on shared data (either shared across disparate parts of the application code, or in a database and shared across applications and sessions).

So my rule of thumb is really speaking about methods that have to be investigated before it's possible to understand exactly what they do and what part they play in the system. In my view, one layer of indirection is complicated, and two risks frequent failure without above-average care and study.

And I'm speaking about indirection in executable methods, but it would equally apply to data structures. Representing simple mathematical objects like regular multi-dimensional arrays with pointers, and containing values with common meanings, might go to one or two more levels without introducing fiendish complexity. But in a database containing general business records, or in an application that manipulates them, one level of indirection in structures will make reasoning and correct coding complicated already, and two is reaching an extreme.

Answer 6

You can certainly have data structures that in order to access them you use multiple levels of indirection, beyond 2. (Though it is rare.)

But you typically do not write that directly in code - e.g., ***p1

Instead, you can either:

1. Introduce properly named accessor functions that (usually) do this step-by-step, with names that tell you what's going on.

2. Or even better, introduce properly named intermediate structures (even with only one element: the pointer to the next struct, to make his semantically clear to everyone.