|
Preserving constness where you want it is a little easier with templates, but it's still rife with complexities.
May 01, 1999
URL:http://drdobbs.com/c-theory-and-practice/184403650
// deep.h
#ifndef DEEP_H_INCLUDED
#define DEEP_H_INCLUDED
template <typename T>
class deep_pointer
{
public:
T *&value();
T const *const &value() const;
private:
T *actual_pointer;
};
template <typename T>
inline
T *&deep_pointer<T>::value()
{
return actual_pointer;
}
template <typename T>
inline
T const *const &
deep_pointer<T>::value() const
{
return actual_pointer;
}
#endif
// deep.h
#ifndef DEEP_H_INCLUDED
#define DEEP_H_INCLUDED
template <typename T>
class deep_pointer
{
public:
T *&operator()();
T const *const &operator()() const;
private:
T *actual_pointer;
};
template <typename T>
inline
T *&deep_pointer<T>::operator()()
{
return actual_pointer;
}
template <typename T>
inline
T const *const &
deep_pointer<T>::operator()() const
{
return actual_pointer;
}
#endif
// deep.h
#ifndef DEEP_H_INCLUDED
#define DEEP_H_INCLUDED
template <typename T>
class deep_pointer
{
public:
deep_pointer();
deep_pointer(T *p);
operator T *&();
operator T const *const &() const;
private:
T *actual_pointer;
};
template <typename T>
inline
deep_pointer<T>::deep_pointer()
{
}
template <typename T>
inline
deep_pointer<T>::deep_pointer(T *p)
{
actual_pointer = p;
}
template <typename T>
inline
deep_pointer<T>::operator T *&()
{
return actual_pointer;
}
template <typename T>
inline
deep_pointer<T>::operator T const *const &() const
{
return actual_pointer;
}
#endif
// table.h
#include <stdio.h>
#include "deep.h"
class cross_reference_table
{
public:
cross_reference_table();
void add(char const *w, unsigned n);
void put() const;
private:
struct tree_node;
static tree_node *add_tree
(tree_node *t, char const *w, unsigned n);
static void put_tree(tree_node const *t);
deep_pointer<tree_node> root;
};
inline
cross_reference_table::cross_reference_table()
{
root = NULL;
}
inline
void
cross_reference_table::add(char const *w, unsigned n)
{
root = add_tree(root, w, n);
}
inline
void cross_reference_table::put() const
{
put_tree(root);
}
// deep.h
#ifndef DEEP_H_INCLUDED
#define DEEP_H_INCLUDED
template <typename T>
class deep_pointer
{
public:
deep_pointer();
deep_pointer(T *p);
operator T *();
operator T const *() const;
T *operator->();
T const *operator->() const;
private:
T *actual_pointer;
};
template <typename T>
inline
deep_pointer<T>::deep_pointer()
{
}
template <typename T>
inline
deep_pointer<T>::deep_pointer(T *p)
: actual_pointer(p)
{
}
template <typename T>
inline
deep_pointer<T>::operator T *()
{
return actual_pointer;
}
template <typename T>
inline
deep_pointer<T>::operator T const *() const
{
return actual_pointer;
}
template <typename T>
inline
T *deep_pointer<T>::operator->()
{
return actual_pointer;
}
template <typename T>
inline
T const *deep_pointer<T>::operator->() const
{
return actual_pointer;
}
#endif
// table.cpp
#include <stdio.h>
#include <string.h>
#include "deep.h"
#include "table.h"
struct list_node
{
unsigned number;
deep_pointer<list_node> next;
};
struct cross_reference_table::tree_node
{
deep_pointer<char> word;
deep_pointer<list_node> first, last;
deep_pointer<tree_node> left, right;
};
cross_reference_table::tree_node *
cross_reference_table::add_tree
(tree_node *t, char const *w, unsigned n)
{
int cmp;
if (t == NULL)
{
t = new tree_node;
t->word = new char [strlen(w) + 1];
strcpy(t->word, w);
t->first = new list_node;
t->first->number = n;
t->first->next = NULL;
t->last = t->first;
t->left = t->right = NULL;
}
else if ((cmp = strcmp(w, t->word)) < 0)
t->left = add_tree(t->left, w, n);
else if (cmp > 0)
t->right = add_tree(t->right, w, n);
else if (n != t->last->number)
{
t->last->next = new list_node;
t->last = t->last->next;
t->last->number = n;
t->last->next = NULL;
}
return t;
}
void
cross_reference_table::put_tree
(tree_node const *t)
{
if (t != NULL)
{
put_tree(t->left);
printf("%12s:", t->word);
list_node const *p = t->first;
for (; p != NULL; p = p->next)
printf(" %4d", p->number);
printf("\n");
put_tree(t->right);
}
}
Preserving constness where you want it is a little easier with templates, but it's still rife with complexities.
Copyright © 1999 by Dan Saks
Last month, I described a problem with the semantics of the const qualifier. I also presented a programming technique that helps correct the problem. However, the technique is so cumbersome that I really can't recommend it. (See "C++ Theory and Practice: Thinking Deeply," CUJ, April 1999.)
I have a solution that appears to be much more viable. It's rather involved and requires more than one article to explain it all. It's a bit of a digression from the program design issues I've been discussing, but I think it's pretty neat and I'd like to share it with you. As I cautioned last month, I haven't tested this technique very thoroughly, so it may have a few kinks in it. My hope is that some of you will use it (or at least try to use it) and provide feedback that will help me improve the technique or convince me that it isn't viable after all.
The problem I'm addressing is in the semantics of const-qualified class objects that have data members of pointer or reference types. xr, my cross-reference generator program, provides code that illustrates the problem. (See "C++ Theory and Practice: Partitioning with Classes," CUJ, February 1999 and "C++ Theory and Practice: Trimming Excess Fat," CUJ, March 1999, for background on xr.)
xr represents a cross-reference table as an object of class cross_reference_table, which in turn, implements the table as a binary tree. Each node in the tree is an object of the nested type tree_node. The cross_reference_table class has a private data member root, which holds the address of the tree's root node. The relevant parts of the class definition are:
class cross_reference_table
{
public:
...
private:
struct tree_node;
...
tree_node *root;
};
The definition for nested type tree_node appears outside the cross_reference_table class as:
struct
cross_reference_table::tree_node
{
char *word;
list_node *first, *last;
tree_node *left, *right;
};
As I did last month, I will try to simplify the discussion by ignoring the enclosing class name for the time being (writing cross_reference_table::tree_node as just tree_node), and rewrite tree_node with each member defined on a separate line:
struct tree_node
{
char *word;
list_node *first;
list_node *last;
tree_node *left;
tree_node *right;
};
Class cross_reference_table has a static member function named put_tree declared as:
void put_tree(tree_node const *t);
Parameter t points to the root node of a tree. put_tree writes the contents of that tree to standard output. put_tree shouldn't alter the tree in the course of writing it out. Hence, the parameter declaration has a const qualifier so that t has type "pointer to const tree_node".
In this example, every node in the tree, not just the root node, should be const. Unfortunately, that's not the way C++ sees it. Rather, an object declared as:
const_tree_node *t
behaves as if you had declared another type:
struct const_tree_node
{
char *const word;
list_node *const first;
list_node *const last;
tree_node *const left;
tree_node *const right;
};
and then declared t as:
const_tree_node *t
In other words, although every pointer member is const, they point to objects that are not const. Thus, t points to a tree in which only the root node is const. This is what I mean when I say that "const is shallow." const is shallow in C as well as in C++.
In this situation, const should be deep. put_tree's parameter t should behave as if it pointed to an object of type const_tree_node, defined as:
struct const_tree_node
{
char const *const word;
list_node const *const first;
list_node const *const last;
tree_node const *const left;
tree_node const *const right;
};
A tree composed of these nodes is "deeply const." Every node in the tree is const, not just the root.
Thus, the problem is getting const tree_node objects to act like const_tree_node objects, which preserve deep constness.
Last month, I introduced a technique for enforcing deep constness. The technique is conceptually simple but rather tedious. For each non-static data member of pointer type, you add a pair of member functions overloaded as const and non-const member functions. The const member returns a reference to the pointer data member with const qualifiers added to the return type to produce deep const behavior. The non-const member function returns a reference to the pointer data member with no added const qualifiers. For non-const objects, the return value of the non-const member function acts just like the data member itself.
For example, applying this technique to tree_node's data member named word transforms:
struct tree_node
{
char *word;
...
};
into:
struct tree_node
{
public:
char *&word();
char const *const &word() const;
...
private:
char *_word;
};
You must do this for every other pointer member as well. That's how it gets tedious in a hurry. In C++, the common cure for such tedium is a template.
Let's consider implementing a template for a class that I'll call deep_pointer. deep_pointer bears some similarity to the standard auto_ptr class template, but unlike auto_ptr, which provides dynamic memory deallocation, deep_pointer provides no run-time functionality beyond that of a built-in pointer type. (For more information on auto_ptr, see selected installments of Bobby Schmidt's old "Learning C/C++urve" column [1] and P.J. Plauger's "Standard C/C++" column [2].)
Ideally, a deep_pointer<T> should behave exactly like a true "pointer to T", except that a deep_pointer<T> preserves deep constness. In other words, an object declared as:
deep_pointer<T> p;
should behave just like an object declared as:
T *p;
However, an object declared as:
deep_pointer<T> const p;
should behave exactly like an object declared as:
T const *const p;
Syntactically, deep_pointer<T> and const are both declaration-specifiers. You can write them in either order. Thus,
deep_pointer<T> const p; const deep_pointer<T> p;
are equivalent. I prefer the former for purely stylistic reasons.
More than one declaration-specifier can appear in a template type argument (inside the < >), so that:
deep_pointer<T const> p; deep_pointer<const T> p;
are also equivalent. Again, I prefer the former.
Be aware that:
deep_pointer<T> const p;
is different from:
deep_pointer<T const> p;
The former is a "const deep_pointer to T" while the latter is a "deep_pointer to const T".
The header deep.h appearing in Listing 1 contains my first attempt at a deep_pointer class template. The template employs a technique that's remarkably similar to the brute force technique I described earlier, but because it's a template, it eliminates much of the tedium.
The template implements a deep_pointer<T> as a single private member of type T * called actual_pointer. The class also provides two overloaded member functions named value, each of which returns a reference to the actual pointer. The functions are overloaded as const and non-const members. As in the brute force technique, the const member returns a reference to the actual pointer with const-qualifiers added to the return type to produce deep const behavior. The non-const member function returns a reference to the actual pointer with no added const qualifiers.
Using this template, the tree_node's definition is almost as concise as it was when using built-in pointers:
struct
cross_reference_table::tree_node
{
deep_pointer<char> word;
deep_pointer<list_node>
first, last;
deep_pointer<tree_node>
left, right;
};
That's the good part. On the other hand, the code that uses these deep_pointers can't refer to them as if they were built-in pointers. That's the bad part.
For example, cross_reference_table::put_tree contains the recursive call:
put_tree(t->left);
put_tree's parameter has type tree_node const *. When tree_node's member left had type tree_node *, this call worked just fine. However, now that left has type deep_pointer<tree_node> const, you must write the call as:
put_tree(t->left.value());
to transform t->left to a true pointer type.
You can make the conversions from deep pointers to true pointers less obtrusive by changing the conversion function names from valve to operator(). That is, you change the declarations of deep_pointer's member functions:
T *&value(); T const *const &value() const;
to:
T *&operator()(); T const *const &operator()() const;
respectively. Change the corresponding member definitions, too.
The revised header deep.h appears in Listing 2. Using this version of deep_pointer<T>, a call such as:
put_tree(t->left.value());
becomes:
put_tree(t->left());
This call appears exactly as it did in the version of the program I presented last month using the "brute force" technique. The parentheses are less obtrusive, but they're still a nuisance.
Mercifully, you don't have to change every occurrence of expressions such as p->m into p->m(). An assignment such as:
t->left = t->right;
still compiles and works correctly because members left and right have the same type, namely, deep_pointer<tree_node>. The compiler uses the generated copy assignment operator:
deep_pointer<tree_node> &operator=
(deep_pointer<tree_node> const &);
In this case, you need not rewrite the assignment as:
t->left() = t->right();
Still, the program has more than thirty places where expressions that had the form p->m now look like p->m(). Let's see about getting rid of those pesky parentheses so that, aside from their declarations, deep pointers can look just like ordinary pointers.
If you change some of the other pointers in the program into deep_pointers, types should match up so that you don't need to write the function call parentheses to convert deep_pointers into ordinary pointers. Anyway, that's the hope. For example, the type of an expression such as t->left is the type of left, which in this example is deep_pointer<tree_node>. Thus, if we change put_tree's declaration from:
void put_tree(tree_node const *t);
to:
void put_tree
(deep_pointer<tree_node> const t);
then:
put_tree(t->left);
should work in place of:
put_tree(t->left());
Unfortunately, it doesn't. Since this call to put_tree is recursive, the t in t->left is the same t as the t in put_tree's parameter list. t is a deep_pointer<tree_node>, which cannot be the left operand of an arrow, at least not yet. Therefore, you must write the call as:
put_tree(t()->left);
which is really no better than:
put_tree(t->left());
Let's leave put_tree's parameter type as tree_node const * and see if we can eliminate the parentheses another way.
You can eliminate some of the function call parentheses by providing implicit conversions that can convert deep pointers to or from built-in pointers. Constructors provide conversions from built-in pointers to deep pointers. Conversion operators provide conversions that go the other way — from deep pointers to built-in pointers.
Listing 3 contains a new version of deep.h in which class template deep_pointer<T> has a constructor declared as:
deep_pointer(T *p);
Of course, this constructor lets you write declarations that initialize a deep_pointer<T> object using a value of type T *, for any type T. Here's an example where T is char:
char *s = "an important message"; deep_pointer<char> p = s;
Since it can be called with exactly one argument and it's not declared with the keyword explicit, this constructor is a converting constructor. It acts as an implicit conversion from type T * to type deep_pointer<T>.
For example, Listing 4 contains header table.h, which defines the cross_reference_table class and its corresponding inline member functions. The definition for the default constructor contains the single statement:
root = NULL;
which uses the converting constructor to convert NULL to a deep pointer.
NULL is actually an integer constant expression with value zero. The program converts NULL to tree_node *, and then passes the resulting pointer to the converting constructor to obtain a temporary deep pointer. It uses the generated copy assignment to copy the temporary deep pointer to root, and then destroys the temporary.
Fortunately, all of this work is just conceptual. Compilers typically eliminate the temporary and copy the null pointer value directly into root's actual_pointer member. The resulting code is the same as if root still had type tree_node *.
The deep_pointer class template in Listing 3 also has a default constructor declared, of course, as:
deep_pointer();
The compiler won't generate this constructor because the deep_pointer class already has at least one explicitly declared constructor — the converting constructor.
The definition for cross_reference_table's default constructor doesn't specify a member initializer for data member root. Therefore, the compiler generates a call to deep_pointer's default constructor that initializes root before entering the body of cross_reference_table's default constructor. Again, the call is conceptual. deep_pointer's default constructor is an inline function with an empty body. Compilers can optimize the call away.
In this particular instance, you can eliminate the need to call deep_pointer's default constructor by rewriting cross_reference_table's constructor to specify a member initializer, as in:
inline
cross_reference_table::
cross_reference_table()
: root(NULL)
{
}
Still, the deep_pointer class should have a default constructor so that it can mimic the behavior of a built-in pointer.
The body of cross_reference_table::add in Listing 4 contains the statement:
root = add_tree(root, w, n);
add_tree's return type is tree_node *. Here again, the program uses the converting constructor, this time to transform the return value from add_tree into a deep_pointer<tree_node>, which it then assigns to root.
add_tree's first parameter also has type tree_node *, but the first argument to the call, namely root, has type deep_pointer<tree_node>. A constructor can't do this conversion. For this you need a conversion operator. Class deep_pointer<T> provides two such operators, declared in Listing 3 as:
operator T *&(); operator T const *const &() const;
Except for their names, these conversion operators are identical to the overloaded operator() functions in Listing 2.
cross_reference_table::add is a non-const member function. In the function body, root is a non-const object. Therefore, when passing root as the first argument to add_tree in:
add_tree(root, w, n);
the compiler uses the non-const conversion operator. The call behaves as if you had written the conversion explicitly using any of the following forms:
1. an old-style or C-style cast:
add_tree((tree_node *)root, w, n);
2. a new-style cast:
add_tree(static_cast<tree_node *>(root), w, n);
3. an explicit member function call:
add_tree(root.operator T *&(), w, n);
None of these is very pretty.
cross_reference_table::put is a const member function so that in its body, root is a const object. Therefore, when it passes root as the argument to put_tree in:
put_tree(root);
the compiler uses the const conversion operator. This converts root from deep_pointer<tree_node> const to tree_node const *const &. This preserves the deep constness of the tree_node addressed by root.
The body of cross_reference_table::add contains several expressions with multiple -> operators in succession. In the original xr program, which used built-in pointers instead of deep pointers, one such statement looks like:
t->first->next = NULL;
When using the deep_pointer class template that has operator() as the conversion function, that statement looks like:
t->first()->next = NULL;
This expression looks a bit odd and I rather not concede that it has to be done this way. Once again, I'd like to get rid of those parentheses.
When I changed the operator() functions to conversion operators, I briefly hoped that the compiler would once again let me write:
t->first->next = NULL;
I was thinking it would apply the conversion operator to turn member first into a pointer that would be the left operand of the second -> operator. Silly me.
Rather, you must apply the conversion operator explicitly, as in:
static_cast<list_node *>(t->first)
->next = NULL;
Clearly, deep pointers don't yet look like built-in pointers. To close this gap, define operator-> as a member of class template deep_pointer<T>. Not surprisingly, you need two such operators: one const and the other non-const.
Listing 5 contains yet another version of deep.h with a pair of members named operator->. Listing 6 contains table.cpp, the source file that defines the non-inline members for the cross_reference_table class. Using this latest version of deep.h, table.cpp can manipulate deep pointers as if they were built-in pointers, except that it can't use deep pointers to violate the deep constness of the cross-reference table. And that's good.
I've tested the code in Listing 6 using a few different compilers. One accepts the code without complaint. Another issues warnings but compiles and links the code anyway, producing an xr program that seems to run just fine. Yet another compiler rejects the code, alleging the presence of ambiguities. In the next installment, I'll tell you which one of these compilers is right.
The deep_pointer class template in Listing 5 is still only a start. It needs more operators to completely reproduce the behavior of built-in pointers. That's something else to do next time.
[1] Bobby Schmidt. "The Learning C/C++urve," C/C++ Users Journal, July-December 1997 and February-March 1998.
[2] P.J. Plauger. "Standard C/C++: The Header <memory>," C/C++ Users Journal, July 1996.
Dan Saks is the president of Saks & Associates, which offers training and consulting in C++ and C. He is active in C++ standards, having served nearly seven years as secretary of the ANSI and ISO C++ standards committees. Dan is coauthor of C++ Programming Guidelines, and codeveloper of the Plum Hall Validation Suite for C++ (both with Thomas Plum). You can reach him at 393 Leander Dr., Springfield, OH 45504-4906 USA, by phone at +1-937-324-3601, or electronically at [email protected].
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.