CODEWITHSUNDEEP
c++pointersconstantstransitive-const
Ruifeng Xie
Ruifeng Xie

Reputation: 906

How to make a deep-const pointer

Let's say I want to represent a binary tree in C++. Usually, I want a Node struct like this:

struct Node {
  Node* left
  Node* right;
};

(Here I use struct and raw pointers just for simplicity. I know I should use smart pointers for memory management.)

This representation has a problem: I can never have a deep-const tree. (Correct me if I can.) I may mark a single Node const, but its children is hard-coded as non-const in the Node struct.

(I may use some template hack to make left and right optionally const, but this makes the const Node and non-const Node incompatible.)

Soon I found out, if I magically had some deep-const pointer (say deep_const_pointer, which makes constness transitive), I can use that pointer in Node so that having a const node automatically means having a const sub-tree.

I tried to write a deep-const pointer class, and here is what I end up with:

template <typename T>
class deep_const_pointer {
public:
  explicit deep_const_pointer(const T* p_)
    : p{const_cast<T*>(p_)} {}

  const T& operator*() const { return *p; }
  T& operator*() { return *p; }

  const T* operator->() const { return p; }
  T* operator->() { return p; }

  // etc.

private:
  T* p;
};

Here I cast out the const in the constructor and optionally add it back according to the constness of this pointer-like object. However, this implementation allows the following:

const int i = 42;
deep_const_pointer<int> p{&i};
*p = 0; // Oops!

So it depends on the user to correctly mark whether the pointer is const or not.

How should I build a deep-const pointer class? Ideally, I want the const check happen at compile-time, and that pointer class takes as much memory as a raw pointer. (Which rules out the solution to save the constness to a bool member variable and check on each access.)

EDIT: I checked std::experimental::propagate_const, and it is indeed not a "deep-const" pointer from my perspective. What I meant by deep-const pointer P is:

  1. Constant P is pointer-to-const;
  2. Mutable P is pointer-to-mutable;
  3. A const reference to a non-const P is treated as if it were a const P;
  4. Since pointer-to-const has value semantics, a const P should be trivially copyable.

propagate_const fails to match the requirement because:

  1. It never accepts a pointer-to-const;
  2. It is not copyable (copy constructors explicitly deleted);

From the comments and answer I received, I guess such a P is not implementable in C++.

Upvotes: 3

Views: 495

Answers (1)

Deduplicator
Deduplicator

Reputation: 45684

Writing a transitive-const smart pointer is a solved problem, just look up std::experimental::propagate_const<>. It shouldn't be too hard to find appropriate implementations.

In your own try, you got constructing from a raw pointer wrong. You should not add const to the pointee-type, nor strip it out with a cast.
Fixed:

explicit deep_const_pointer(T* p_)
    : p{p_} {}

Upvotes: 0

Related Questions