Why pointer_traits was introduced in C++11

In this post, I examine the pointer_traits template class in detail.  I stumbled across this class when trying to learn how allocators are handled in C++ standard library container classes.  Given that it has such a fundamental-sounding name, it seemed appropriate to gain a solid understanding of what it is and how it is used.  This led me down a long and painstaking journey that ultimately led to enlightenment.  Considering that there are most likely other folks out there that are similarly curious about this class template, I decided to share my findings.

First of all, pointer_traits is an adapter template class that provides a uniform interface to certain attributes of pointer and pointer-like types.  Before I get into the details of what this uniform interface is and how it is used, a little background is in order, regarding how this class came into existence.

Generalized Pointers

Most of the container class templates in C++ are parameterized with an allocator type and have constructors that accept an allocator object as an argument.  This provides programmers with the ability to create special allocators to handle memory allocation within a container.  For example, one common allocator that is often used with containers is an arena (or slab) allocator, which doles out allocation requests from larger pages of memory.  This kind of allocator can be much more efficient that the default allocator which allocates memory directly from the global heap.

The C++98/03 standard contains the following language in the Allocator Requirements section:

The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*, T const*, std::size_t, and std::ptrdiff_t, respectively.

While these constraints are fine for many allocators, they pose a problem for allocators that allocate from relocatable (e.g. shared) memory.  The problem arises when storing pointers to objects within the relocatable memory segment.  Figure 1 illustrates the problem.

Shared memory pointer problem

Figure 1. Shared memory pointer problem

The pointer variable (ptr), written by Process A, points to a Node structure that is stored in the shared memory segment.  This pointer contains the address 0x9c6080, which is the virtual address of the Node structure, as it appears in Process A.  In process B, however, the shared memory segment is mapped to a different starting address, 0x14ae010, which makes the Node structure appear at a different virtual address.  Within process B, address 0x9c6080 is invalid, and in fact, points to a memory location outside of the shared memory segment.

To solve this problem, the folks over at Boost have created a smart-pointer-like template class called offset_ptr.  This class provides a pointer-like interface, but instead of storing an absolute address (e.g. 0x9c6080) it stores an offset (e.g. +5000 or -200) that is relative to the address of the offset_ptr object itself.  If all pointers to objects in a shared memory segment are represented with offset_ptr, the shared memory segment can be mapped to any arbitrary virtual address and the pointers remain valid.

To allow containers to be constructed inside relocatable memory segments, the C++11 standard has removed the constraint that the pointer member type of an allocator must be T*.  This type can now be any pointer-like type such as offset_ptr.

SCARY Assignments

Generic (i.e. template) classes often use nested types as part of their interface.  These nested types implicitly depend on the parameters of the generic classes in which they are defined.  One notable example is iterators in STL containers.  Iterators don’t actually depend on comparators or allocators; they typically just traverse pointers and provide access to container values.  Consider the following code snippet:

set<int,C1,A1>::iterator i1;
set<int,C2,A2>::iterator i2 = i1;

With some C++98/03 standard library implementations, the above code will not compile.  The reason is that set<int,C1,A1>::iterator and set<int,C2,A2>::iterator are distinct types.  However, theoretically, the above code should compile because the iterators don’t actually depend on the comparators or allocators and the one parameter that they do depend on, the value type, is the same (int).  Assignments such as the above are referred to as SCARY assignments (SCARY is a highly contrived acronym derived from the problem description).  Not allowing SCARY assignments poses two problems:

  1. The compiler will generate code for both set<int,C1,A1>::iterator and set<int,C2,A2>::iterator, even though the code is identical, which leads to unnecessary code bloat.
  2. The assignments are, in fact, semantically valid and by not allowing them, it unnecessarily limits the range of problems in which compile-time polymorphism applies.

One of the goals of C++11 was to avoid these problems.  This is achieved by implementing generic classes (in the standard library) in a way that eliminates unnecessary dependencies between their members (nested types, methods) and the generic type parameters.

For complete details on SCARY assignments, see the paper presented at OOPSLA 2009, Minimizing Dependencies within Generic Classes for Faster and Smaller Programs.

Recursive Data Structures

Reviewing what we’ve covered so far, two goals of C++11 were to (1) allow generalized pointers to be used in containers (i.e. allow pointer-like class types such as offset_ptr), and (2) minimize dependencies between template class members (nested types, methods) and the generic type parameters.

So with these goals in mind, let’s take a stab at an implementation of the list container’s internal node class.  We want the class to be able to support generalized pointer types and it should not be parameterized on the allocator type.  So, how about something like the following?

typedef <class T, class NodePtr>
class list_node {
  NodePtr prev;
  NodePtr next;
  T value;
};

Unfortunately, this definition is recursive.  The list_node class is dependent on the NodePtr parameter, which is dependent on the list_node class.  To get around this problem, the NodePtr type parameter was replaced with VoidPtr and the pointer_traits class template was introduced, with a rebind member template:

namespace std {

  template <class Ptr>
  struct pointer_traits {
    template <class U> using rebind = typename Ptr::template rebind<U>;
  }

  template <class T>
  struct pointer_traits<T*> {
    template <class U> using rebind = U*;
  }
}

The pointer_traits class template with its rebind member template provides a way to transform a generalized pointer to type void, to the same generalized pointer to any other type.  With this piece of infrastructure, the list_node class can be redefined as follows:

typedef <class T, class VoidPtr>
class list_node {
  typedef pointer_traits<VoidPtr>::template rebind<list_node> pointer;
  pointer prev;
  pointer next;
  T value;
};

This solves the recursive data structure problem and maintains the goals of supporting generalized pointers and eliminating the dependency on the allocator type.

Howard Hinnant proposed this solution on the C++ libraries mailing list in a response on the thread Re: Ext pointer vs N2913. I strongly encourage you to read it, in its entirety.  It is very well written and served as the basis (both directly and indirectly) for all of the information contained in this post.

Reference: pointer_traits

The following reference information was gleaned from a perusal of the LLVM C++ Standard library implementation.

The pointer_traits class template is defined in the standard C++ library header <memory>.  It consists of two template classes, (1) a base template, and (2) a specialization for pointers of the form T*:

namespace std {

  // (1) base template
  template <class Ptr> struct pointer_traits;

  // (2) specialization
  template <class T> struct pointer_traits<T*>;

}

Member Type: pointer

Template Definition
(1) Base template typedef Ptr pointer;
(2) Specialization typedef T * pointer;

From what I can tell, this member type was added for convenience.  I couldn’t find any place, outside of the pointer_traits definition, where it was actually used.

Member Type: element_type

Template Definition
(1) Base template Ptr::element_type if present.  Otherwise T if Ptr is a template instantiation Template<T, Args…>
(2) Specialization T

There are several places in the implementation where this member type is used.  For example, there is a shared internal class template called __tree that provides the core logic for both map and set.  The __tree__iterator definition needs access to a member type, base, of the node type.  It obtains the node type from the NodePtr type parameter via the following typedef:

typedef typename pointer_traits<NodePtr>::element_type __node;

and then references the base member type as follows:

typename __node::base

Member Type: difference_type

Template Definition
(1) Base template Ptr::difference type if present, otherwise std::ptrdiff_t
(2) Specialization std::ptrdiff_t

This member type appears to exist to support the required difference_type property of iterators, which is the type that can be used to express the result of subtracting one iterator from another.  The iterator_traits adapter uses Iterator::difference_type by default.  So, for example, in the iterator definition for list, you’ll see the following type definition:

typedef typename pointer_traits<NodePtr>::difference_type difference_type;

Member Alias Template: rebind

Template Definition
(1) Base template Ptr::rebind<U> if exists, otherwise Template<U, Args...> if Ptr is a template instantiation Template<T, Args...>
(2) Specialization template< class U > using rebind U*

Given a pointer or pointer-like type that points to a value of type T, this member template allows you to create a similar pointer or pointer-like type, the only difference being that it points to a value of type U.

Static Member Function: pointer_to

This static member function has the following prototype:

static pointer pointer_to( element_type& r );

Given a reference to an object r, this function will return a pointer to it of type pointer. The base template version returns Ptr::pointer_to(r), while the specialization returns std::addressof(r).  The std::addressof template function returns the actual address of its argument, even if operator& is overloaded.

This is used in many places throughout the c++ standard library headers.  One notable usage is in the implementation of the operator->() function of the iterator types, where a pointer to the value is returned.  The implementation of these functions looks something like the following:

pointer operator->() const {
  return pointer_traits<pointer>::pointer_to(node->value);
}

Conclusion

So there you have it.  Everything you ever wanted to know about pointer_traits.  While the name has a very fundamental ring to it, it belies its somewhat esoteric origin and usage.  In other words, you probably won’t bomb your C++ technical interviews if you don’t know what it is, but it certainly won’t hurt. ☺

Posted in C++ | Tagged | 1 Comment