On would–be const constructors

In this post I would like to discuss the idea of having constructors, or some equivalent, designed to build only objects that are const. My motivating example is an attempt to implement matrices and matrix views. I believe this is a canonical example where temptation to have const constructors appears in const methods of the principal class, the chief context in which one has limited data that suffice to only build a const–restricted object. I will try to be clever implementing them, and then show why it does not really work, and what lessons should be learnt from that exercise.

Matrices and matrix views


Matrix views are notionally also matrices, but they represent a subset of the original matrix (think chosen rows and columns), and should allow changes to the original matrix through changes in the view. So I would expect them to work like in the following example:

auto main(void) -> int
  {
  full_matrix m(3,3,0);
  matrix_view mv = m.column(3);
  mv[{3,1}] = 17;
  assert(m[{3,3}]==17);
  return 0;
  }

So I created a 3–by–3 matrix m filled with zeros, took a view mv of its third column, modified the bottom entry of that view, and made sure the modification made its way back into m at coordinates 3,3.

Naïve solution


A first attempt at declarations to allow that is easy:

class matrix_view;
typedef std::size_t index_type;
typedef float value_type;

struct coord
  {
  index_type y=1;
  index_type x=1;
  coord(index_type yy, index_type xx) 
    : y(yy), 
      x(xx) 
    {}
  };

class full_matrix
  {
  public:
    auto column(index_type ind) -> matrix_view;
    auto operator[](coord c) -> value_type&;
  };

class matrix_view
  {
  public:
    auto operator[](coord c) -> value_type&;
  };

auto main(void) -> int
  {
  full_matrix m(3,3,0);
  matrix_view mv = m.column(3);
  mv[{3,1}] = 17;
  assert(m[{3,3}]==17);
  return 0;
  }

(I will not be implementing much of the solution in this blog post, just what I need to make the point). Now, the above solution works only in the case when the original matrix m is not const.

The const dillema


What is the usual way of providing for that in the case of operator[]? We need to have another overload of method operator[], this time with the const constraint on the object argument, and returning something immutable, possibly const value_type&. It could have been value_type by value, but let’s assume this may grow heavier than just float, so the latter would be suboptimal. We will also need another column method, and taking operator[] as model, we would get something like the following:

class full_matrix
  {
  public:
    auto column(index_type ind) -> matrix_view;
    auto column(index_type ind) const -> const matrix_view;
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };
class matrix_view
  {
  public:
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };

So for now, the design choice was to return a const matrix_view when asked for a submatrix of a const matrix, that seems analogous to the choice for operator[], and leverages the fact that matrix_view already has two such operators doing the right thing, that is, operations on the const matrix_view object only get to use its const interface. Let me try to investigate the options for implementation of that choice.

Objects of class matrix_view need to carry information about the original matrix, to be able to act on its coefficients. The standard way of achieving that is to have a pointer–type attribute (reference–type attributes disallow assignments of objects carrying them, as references cannot be rebound). So if we look only at the mutable part of the matrix and matrix_view duo, things are easy:

class full_matrix
  {
  public:
    auto column(index_type ind) -> matrix_view;
    auto operator[](coord c) -> value_type&;
  };

class matrix_view
  {
    full_matrix* original_matrix_;
  public:
    explicit matrix_view(full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(original_matrix)
      {}
    auto operator[](coord c) -> value_type&
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
  };

auto full_matrix::column(index_type ind) -> matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

But now we need to provide implementation for the const counterparts. The main difficulty here is that in the const column method of class matrix the this pointer is of type const matrix, so we cannot give it to the constructor of matrix_view.

A const_cast solution


The first option that comes to mind is to use const_cast:

class full_matrix
  {
  public:
    auto column(index_type) -> matrix_view;
    auto column(index_type) const -> const matrix_view;
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };

class matrix_view
  {
    full_matrix* original_matrix_;
  public:
    explicit matrix_view(full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(original_matrix)
      {}
    auto operator[](coord c) -> value_type&
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
    auto operator[](coord c) const -> const value_type&
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
  };

auto full_matrix::column(index_type) -> matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

auto full_matrix::column(index_type) const -> const matrix_view
  {
  return matrix_view(const_cast<full_matrix*>(this) /*maybe other data*/);
  }

but this is dangerous. We cannot know in const method column if the class full_matrix object it was called on was actually const or not. If it was, it is illegal to modify the const object by means of a pointer with const casted away. So if you complete the code in Listing 5 by

auto main(void) -> int
  {
  const full_matrix m(3,3,0);
  matrix_view mv = m.column(3);
  mv[{3,1}] = 17;  // undefined behaviour
  return 0;
  }

you’re in for trouble.

const constructors


Then, maybe, before doing the right thing, we could explore some ways of being clever? We had a generic constructor for matrix_view above, and to use it we had to do a dangerous thing. So, maybe we should have different constructors for each occasion? Enter const constructors. But what should the new one do? Well, since we can only give it a const full_matrix* pointer, so be it:

class full_matrix
  {
  public:
    auto column(index_type) -> matrix_view;
    auto column(index_type) const -> const matrix_view;
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };

class matrix_view
  {
    full_matrix* original_matrix_;
    const full_matrix* const_original_matrix_;
    // constructor intended for mutable matrix_views
    explicit matrix_view(full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(original_matrix),
        const_original_matrix_(original_matrix)
      {}
    // constructor intended for const matrix_views
    explicit matrix_view(const full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(nullptr),
        const_original_matrix_(original_matrix)
      {}
    friend class full_matrix;
  public:
    auto operator[](coord c) -> value_type&
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
    auto operator[](coord c) const -> const value_type&
      {
      return (*const_original_matrix_)[/*some transform of*/c];
      }
  };

auto full_matrix::column(index_type) -> matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

auto full_matrix::column(index_type) const -> const matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

The matrix_view class now sports two pointers, one of type full_matrix* used in the mutable part of the interface of the view, and the other one of type const full_matrix*, used in the const interface. Clearly, there is nothing to prevent the inadvertent user from using objects built with the constructor with const full_matrix* parameter as regular non–const objects, which is asking for disaster, as these are semi–zombies, so I put the constructors as private, in the hope at least the maintainer understands what is going on. Unfortunately, this solution is still vulnerable to the problem of Listing 5, let me repeat it here:

auto main(void) -> int
  {
  const full_matrix m(3,3,0);
  matrix_view mv = m.column(3);
  mv[{3,1}] = 17;  // undefined behaviour or some assert, see below
  return 0;
  }

One could replace the inner full_matrix* original_matrix_ pointer with some sort of a checked pointer, for example an instance of

    template<class T>
class checked_ptr
  {
    T* t_;
  public:
    explicit checked_ptr(T* t=nullptr)
      : t_(t)
      {}
    auto operator*(void) const -> T&
      {
      assert(t_);
      return *t_;
      }
    auto operator->(void) const -> T*
      {
      assert(t_);
      return t_;
      }
    auto get(void) const -> T*
      {
      return t_;
      }
    explicit operator bool(void) const
      {
      return t_;
      }
  };

but this is going to flag problems only at runtime, which is better than the undefined behaviour of the const_cast solution, but only by so much.

Lesson one

Problems with both ideas discussed above resulted from the fact that the const matrix_view object got copied onto a non–const matrix_view. To put it short, we should remember that

Returning custom–built const objects (and hence the need for custom const constructors) is incompatible with standard copy semantics.

Can we keep the main idea but improve the situation by subverting the type system somehow? I don’t see a fully satisfactory solution. Once a copy or move constructor that accepts const objects is made public, the thing goes out of hand as we have no way of controlling whether the newly constructed object is const itself. A half–good solution would be to provide a public copy constructor for non–const objects only, this goes against common usage, and not without extra quirks:

class full_matrix
  {
  public:
    auto column(index_type) -> matrix_view;
    auto column(index_type) const -> const matrix_view;
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };

class matrix_view
  {
    full_matrix* original_matrix_;
    const full_matrix* const_original_matrix_;
    explicit matrix_view(full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(original_matrix),
        const_original_matrix_(original_matrix)
      {}
    explicit matrix_view(const full_matrix* original_matrix /*maybe other data*/)
      : original_matrix_(nullptr),
        const_original_matrix_(original_matrix)
      {}
    friend class full_matrix;
  public:
    matrix_view(matrix_view& mv)
      : original_matrix_(mv.original_matrix_),
        const_original_matrix_(mv.original_matrix_)
      {}
    matrix_view(matrix_view&& mv)
      : original_matrix_(mv.original_matrix_),
        const_original_matrix_(mv.original_matrix_)
      {}
    auto operator[](coord c) -> value_type&
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
    auto operator[](coord c) const -> const value_type&
      {
      return (*const_original_matrix_)[/*some transform of*/c];
      }
  };

auto full_matrix::column(index_type) -> matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

auto full_matrix::column(index_type) const -> const matrix_view
  {
  return matrix_view(this /*maybe other data*/); // this uses non-const move
  }

You need matrix_view(matrix_view&& mv), because the non–const l-value reference of matrix_view(matrix_view& mv) will not bind to temporaries, like those in return statements of the column methods, (before c++11, the infamous auto_ptr had to go through additional hops and bounces to allow for that), and you need the latter if you want to copy from genuine l-value views (see example below), as otherwise, having just the move constructor results in the default copy constructor being declared as deleted. What about the const matrix_view objects returned by const column? They cannot be copied or moved from, so if you need the result of such a call to live longer than a temporary, you may use the fact that the lifetime of temporaries to which a reference is bound is extended for as long as that reference lives.

auto main(void) -> int
  {
  const full_matrix m(3,3,0);
  //matrix_view mv = m.column(3); // will not compile
  const matrix_view& mv = m.column(3); // result lives as long as mv
  //mv[{3,1}] = 17;  // will not compile
  double d = mv[{3,1}]; // ok
  full_matrix n(2,2,0);
  matrix_view nv = n.column(1); // ok
  matrix_view nv2 = nv; // need copy constructor for that
  return 0;
  }

Hackish as this may seem, we need to acknowledge that we produced a cripple. The custom const objects can only be produced by methods of a friend class and they can only live for the remaining part of the scope they are created in (the life extension with reference is not transitive, so it will not work across a function return, for instance).

Towards a correct solution

What I have been trying to produce until now is in fact an indirection, that is, a class whose objects refer to objects of some other class. There are two such constructs built directly into the language, pointers and references, and some more in the standard library, known as iterators. Since iterators are generalized pointers while references stand out somewhat, let’s first take a closer look at pointers. What is special about pointers, and relevant in this context, is their dual const–semantics. There is a distinction between a const pointer (that cannot be rebound) and a pointer to const (whose pointee object is const). That gives us two places to put const, resulting in four possibilities (unless your pointee’s type is pointer again, then it is three places and eight possibilities, and you can carry that further on, but let me spare that fun for some other time):

full_matrix* fmp;              // variable pointer to variable object
const full_matrix* cfmp;       // variable pointer to const object
full_matrix*const fmcp;        // const pointer to variable object
const full_matrix*const cfmcp; // const pointer to const object

A reference is always const, as it cannot be rebound, but the referenced object may or may not be:

full_matrix& rfm;        // reference to variable
const full_matrix& rcfm; // reference to const 

What we have been subject to in this post is a fallacy resulting from a visual similarity in code. Namely, as you see above, putting const in front of a declaration of a pointer or of a reference results in const pointee, but putting const in front of a declaration of an object, like we did in the const column method, produces a const object. A convincing example can be built with typedefs:

typedef full_matrix& fm_ref;
typedef full_matrix* fm_ptr;

// const ignored, reference is const anyway:
static_assert(std::is_same<const fm_ref, fm_ref>::value, ""); 

// see where const ends up:
static_assert(std::is_same<const fm_ptr, full_matrix*const>::value, ""); 

In the case of the const matrix_view indirection object we picked the wrong side of things. How to do it properly? The model answer lies with library iterators. When you use begin on a variable container object, an iterator object is returned, when you do that on a const container object, a const_iterator is given. So we need two distinct classes, matrix_view and const_matrix_view.

Lesson two

Let me summarize the findings of the above section.

Recognize indirections. Understand and leverage their dual const semantics.

Bonus

Implementing two classes seems like more work to do, but it need not be so. Moreover, there’s a bonus waiting for us. Until now we’ve been having two almost identical copies of operator[] in class matrix_view, and although sometimes there seems to be no better way (such as in full_matrix), we should better avoid boilerplate repetitions if possible. That, alas, comes at the cost of some syntactic sugar, but I think it is worth it:

class full_matrix;

    template<class VType, class FullMatrix>
class matrix_view_t;

using matrix_view = matrix_view_t<value_type,full_matrix>;
using const_matrix_view = matrix_view_t<const value_type,const full_matrix>;

class full_matrix
  {
  public:
    auto column(index_type) -> matrix_view;
    auto column(index_type) const -> const_matrix_view;
    auto operator[](coord c) -> value_type&;
    auto operator[](coord c) const -> const value_type&;
  };

    template<class VType, class FullMatrix>
class matrix_view_t
  {
    FullMatrix* original_matrix_;
  public:
    friend const_matrix_view;

    explicit matrix_view_t(FullMatrix* original_matrix /*maybe other data*/)
      : original_matrix_(original_matrix)
      {}
    matrix_view_t(const matrix_view& mv)            // strange
      : original_matrix_(mv.original_matrix_)
      {}
    auto operator[](coord c) const -> VType& // completed with const 2016-02-19
      {
      return (*original_matrix_)[/*some transform of*/c];
      }
    friend auto operator==
        (const const_matrix_view& cmv1, 
         const const_matrix_view& cmv2
        ) -> bool;
    friend auto operator!=
        (const const_matrix_view& cmv1, 
         const const_matrix_view& cmv2
        ) -> bool;
  };

auto operator==
    (const const_matrix_view& cmv1, 
     const const_matrix_view& cmv2
    ) -> bool
  {
  return cmv1.original_matrix_ == cmv2.original_matrix_; // && more expressions
  }

auto operator!=
    (const const_matrix_view& cmv1, 
     const const_matrix_view& cmv2
    ) -> bool
  {
  return !(cmv1==cmv2);
  }

auto full_matrix::column(index_type) -> matrix_view
  {
  return matrix_view(this /*maybe other data*/);
  }

auto full_matrix::column(index_type) const -> const_matrix_view
  {
  return const_matrix_view(this /*maybe other data*/);
  }

auto main(void) -> int
  {
  const full_matrix m(3,3,0);
  //matrix_view mv = m.column(3); // will not compile
  const_matrix_view mv = m.column(3); // regular lifetime, can be returned
  //mv[{3,1}] = 17;  // will not compile
  double d = mv[{3,1}]; 
  full_matrix n(2,2,0);
  matrix_view nv = n.column(1); 
  matrix_view nv2 = nv; 
  bool e=(nv!=mv); // ok, can compare symmetrically 
  bool f=(mv!=nv); // ok, can compare symmetrically
  mv = nv;   // ok, can copy view of variable onto view of const
  //nv = mv; // the converse would be dangerous, will not compile
  return 0;
  }

At the cost of the declaration tangle preceding full_matrix we get unique definition of operator[] for matrix_view, but also convenient conversion semantics between the matrix_view and const_matrix_view classes. The strange constructor in the template is going to act as a copy constructor for matrix_view and as a conversion constructor from matrix_view to const_matrix_view in const_matrix_view (the latter will also have a copy constructor, though, the default one provided by the compiler). The template depends on two parameters, as I reckoned that figuring out that we need const value_type& from the fact that the full matrix is const would be too much metaprogramming for this post. Anyway, the two are supposed to be used coherently, most likely through the predefined aliases. The matrix_view version needs to declare const_matrix_view as friend, otherwise the converting constructor would be in trouble, and the relational operators need to be friend to both variants to perform their arithmetic, but this is written once and materialized through template instantiation. This const–nonconst–template technique proves useful in writing iterators and, as it turns out, in writing other indirection classes as well.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: