Darin Minamoto

Home About Github

Date: July 20, 2026

Abstracting over pointer types in C++ and Rust

Pointers have a very general interface. You can get a pointer to something by taking its address, and you can dereference a pointer to access the data at the address. Pointers don’t specify whether the underlying data came from the stack or the heap, whether the data was allocated in an arena allocator or a general free-list allocator, or whether the pointer should be freed or not. For example, here’s a tree data structure in C:

typedef struct node node;
struct node {
    int32_t data;
    node *left;
    node *right;
};

From this type definition, it isn’t clear if a node is responsible for cleaning up its left and right pointers before being deallocated (aka node owns its left and right pointers), or if the left and right pointers will be deallocated separately. We can look for a free function for node:

void node_free(node *node)
{
    if (node->left) {
        node_free(node->left);
    }
    if (node->right) {
        node_free(node->right);
    }
    free(node);
}

This looks like node owns its left and right pointers… as long as the node_free function is called on a node. In C you can simply not call a free function for a type and that could mean that a node is not intended to own its left and right pointers. Or it could be a mistake and result in a memory leak. You will have to carefully read both the code that uses a node and the various helper functions for node to get a full understanding of what is happening.

C++ and Rust attempt to make this process easier by having special types for owned pointers. In C++, the example can be written as:

struct Node {
  int32_t data;
  std::unique_ptr<Node> left;
  std::unique_ptr<Node> right;
};

std::unique_ptr is a container that automatically deallocates its contained data when its destructor is called. Having left and right as std::unique_ptrs makes it explicit that Node will always own its left and right pointers.

However encoding ownership and other low-level details in the type system has a cost. In C, you can write a function that takes in nodes and the function will work with all nodes regardless of ownership.

void print_node(const node *node)
{
    if (node == NULL) {
        return;
    }
    printf("%d\n", node->data);
    print_node(node->left);
    print_node(node->right);
}
// Individual allocations through malloc
{
    node *root = node_alloc(1);
    node *left = node_alloc(2);
    node *right = node_alloc(3);
    assert(root && left && right && "allocation failed");
    root->left = left;
    root->right = right;
    print_node(root);
    node_free(root);
}

// Stack allocation
{
    node nodes[] = {{.data = 1}, {.data = 2}, {.data = 3}};
    nodes[0].left = &nodes[1];
    nodes[0].right = &nodes[2];
    print_node(&nodes[0]);
}

// Arena allocation
{
    arena r = arena_get();
    node *root = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
    node *left = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
    node *right = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
    assert(root && left && right && "allocation failed");
    *root = (node){.data = 1, .left = left, .right = right};
    *left = (node){.data = 2};
    *right = (node){.data = 3};
    print_node(root);
}

Whereas functions that take in nodes using owned container types won’t work with other types. Because C++ and Rust heavily favor using owned types, its easy to start off with them but when you want to switch to an arena allocator, it can be difficult to refactor all the types to a non owned type. And if you want a function to work with multiple pointer types, you may end up manually duplicating the function for each type.

It doesn’t have to be that way though. C++ and Rust are powerful enough to be able to abstract over various smart pointer types as well as raw pointers. Starting with C++, a single template parameter can be used to generically print any type with a printable data field and left and right fields that dereference to the same type as node:

template <typename Node> void printNode(const Node &node) {
  std::cout << node.data << "\n";
  if (node.left) {
    printNode(*node.left);
  }
  if (node.right) {
    printNode(*node.right);
  }
}
struct Node {
  int32_t data;
  std::unique_ptr<Node> left;
  std::unique_ptr<Node> right;
};

struct Node2 {
  int32_t data;
  Node2 *left;
  Node2 *right;
};

int main() {
  auto n1 = std::make_unique<Node>(
      Node{1, std::make_unique<Node>(Node{2, nullptr, nullptr}),
           std::make_unique<Node>(Node{3, nullptr, nullptr})});
  printNode(*n1);

  Node2 left{2, nullptr, nullptr};
  Node2 right{3, nullptr, nullptr};
  Node2 n2{1, &left, &right};
  printNode(n2);
}

To prevent duplicating the Node struct, a template can be used to abstract over the pointer type in the struct definition:

template <typename T> using raw_ptr = T *;

template <template <class> class Ptr = std::unique_ptr> struct Node {
  int32_t data;
  Ptr<Node<Ptr>> left;
  Ptr<Node<Ptr>> right;
};

int main() {
  auto n1 = std::make_unique<Node<>>(
      Node<>{1, std::make_unique<Node<>>(Node<>{2, nullptr, nullptr}),
             std::make_unique<Node<>>(Node<>{3, nullptr, nullptr})});
  printNode(*n1);

  Node<raw_ptr> left{2, nullptr, nullptr};
  Node<raw_ptr> right{3, nullptr, nullptr};
  Node<raw_ptr> n2{1, &left, &right};
  printNode(n2);
}

Finally, we don’t have to hardcode the node’s data as a int32_t, that was only to make the C declaration simpler. In C++, it can be generic with another template parameter:

template <typename T, template <class> class Ptr = std::unique_ptr>
struct Node {
  T data;
  Ptr<Node<T, Ptr>> left;
  Ptr<Node<T, Ptr>> right;
};

int main() {
  auto n1 = std::make_unique<Node<int32_t>>(Node<int32_t>{
      1, std::make_unique<Node<int32_t>>(Node<int32_t>{2, nullptr, nullptr}),
      std::make_unique<Node<int32_t>>(Node<int32_t>{3, nullptr, nullptr})});
  printNode(*n1);

  Node<int32_t, raw_ptr> left{2, nullptr, nullptr};
  Node<int32_t, raw_ptr> right{3, nullptr, nullptr};
  Node<int32_t, raw_ptr> n2{1, &left, &right};
  printNode(n2);
}

In Rust, abstracting over nodes also possible, but it isn’t as simple as C++. C++ templates essentially copy and paste the specialized type where the template is in the function and check if the result compiles. In Rust, you have to specify the behavior that you want to abstract over using a trait. For our example, we would use trait methods for getting the left, right, and data fields of the type implementing our trait:

trait NodeOps<T> {
    fn data(&self) -> &T;
    fn left(&self) -> &Option<impl Deref<Target = Self>>;
    fn right(&self) -> &Option<impl Deref<Target = Self>>;
}

To abstract over pointer-like types, we use impl Deref in the return types of left() and right(). That will work with Box, Rc, bumpalo::boxed::Box, &'a T, etc.

Now that we have our node trait, we can write our function:

fn print_node<T: Debug, Node: NodeOps<T>>(node: &Node) {
    println!("{:?}", node.data());
    if let Some(left) = node.left() {
        print_node(left.deref());
    }
    if let Some(right) = node.right() {
        print_node(right.deref());
    }
}

And for each node type, if we implement NodeOps we can use print_node with them.

struct Node<T> {
    data: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> NodeOps<T> for Node<T> {
    fn data(&self) -> &T {
        &self.data
    }

    fn left(&self) -> &Option<impl Deref<Target = Self>> {
        &self.left
    }

    fn right(&self) -> &Option<impl Deref<Target = Self>> {
        &self.right
    }
}

struct Node2<'a, T> {
    data: T,
    left: Option<&'a Node2<'a, T>>,
    right: Option<&'a Node2<'a, T>>,
}

impl<'a, T> NodeOps<T> for Node2<'a, T> {
    fn data(&self) -> &T {
        &self.data
    }

    fn left(&self) -> &Option<impl Deref<Target = Self>> {
        &self.left
    }

    fn right(&self) -> &Option<impl Deref<Target = Self>> {
        &self.right
    }
}

But what if we don’t want to duplicate the node type for each pointer type? In C++ we used template<class> class for template parameters that themselves take in a template parameter. How do we do this in Rust?

In other languages like Haskell, higher kinded types are used to abstract over containers of types.

data Node a f = Node
    { nodeData  :: a
    , nodeLeft  :: Maybe (f (Node a f))
    , nodeRight :: Maybe (f (Node a f))
    }

In this Haskell code f is a type of kind Type -> Type compared to a which has kind Type, so we can pass types that take types as parameters like Maybe and Either () instead of Int and String.

In Rust we can simulate higher kinded types with generic associated types, which are associated types that take in type parameters. Unlike higher kinded types, generic associated types are attached to a trait, so instead of passing in a type directly like Option, you would have to create a new type and then implement the trait for the type with its associated type set to Option<T>. This is more cumbersome, but since Rust doesn’t have proper higher kinded types, this is the best we can do.

Our pointer trait that contains T which is the generic associated type that stands for any dereferenceable pointer-like type like Box, bumpalo::boxed::Box, &'a T, etc. is shown below.

trait Ptr {
    type T<'a, U: 'a>: Deref<Target = U>;
}

Because bumpalo::boxed::Box and &'a T contain a lifetime parameter, the associated type also has to contain a lifetime parameter 'a so it can work with these types and still compile. For other types like Box, the lifetime parameter is ignored.

The associated type has a bound of Deref and not Deref + DerefMut because &'a doesn’t implement DerefMut. T’s constraints should be the minimum set of constraints, more can be added later in the where clause of functions if needed.

Now that we have our pointer trait, we can write our generic Node struct:

struct Node<'a, T: 'a, P: Ptr + 'a> {
    data: T,
    left: Option<P::T<'a, Node<'a, T, P>>>,
    right: Option<P::T<'a, Node<'a, T, P>>>,
}

Because Node is generic, we no longer need our NodeOps trait and can write the print function directly on Node:

impl<'a, T: Debug, P: Ptr> Node<'a, T, P> {
    fn print(&self) {
        println!("{:?}", self.data);
        if let Some(ref left) = self.left {
            left.print();
        }
        if let Some(ref right) = self.right {
            right.print();
        }
    }
}

If you want to write a function that mutates a linked left or right node, DerefMut needs to be added as a constraint to Ptr::T in a where clause:

impl<'a, P: Ptr> Node<'a, i32, P>
where
    P::T<'a, Self>: DerefMut<Target = Self>,
{
    fn incr(&mut self) {
        self.data += 1;
        if let Some(ref mut left) = self.left {
            left.incr();
        }
        if let Some(ref mut right) = self.right {
            right.incr();
        }
    }
}

Now in order to use these functions, new types are created to implement Ptr for each type we want to abstract over. Below are the implementations for Box and &'a T:

struct BoxPtr;
impl Ptr for BoxPtr {
    type T<'a, U: 'a> = Box<U>;
}

struct RefPtr;
impl Ptr for RefPtr {
    type T<'a, U: 'a> = &'a U;
}

fn main() {
    let mut node: Node<i32, BoxPtr> = Node {
        data: 0,
        left: None,
        right: Some(Box::new(Node {
            data: 1,
            left: None,
            right: None,
        })),
    };
    node.incr(); // incr works with BoxPtr, not RefPtr
    node.print();
    let node: Node<i32, RefPtr> = Node {
        data: 3,
        left: Some(&Node {
            data: 4,
            left: None,
            right: None,
        }),
        right: Some(&Node {
            data: 5,
            left: None,
            right: None,
        }),
    };
    node.print();
}

The Ptr trait works well with trees like abstract syntax trees, but doesn’t work as well with cyclical data structures like graphs. A wrapper around raw pointers like *mut T that implements Deref and DerefMut can work, but that would expose unsafe code and is unidiomatic in Rust.

If we want our Ptr trait to also work with cyclical graphs in Rust, we should first list the most common ways that we can safely encode cycles in Rust:

One way to work with graphs is to treat links or “pointers” as indices into a Vec of nodes. Then given the index, you can access the data through borrowing the Vec either immutably or mutably. Because indices are essentially integers, they don’t have lifetimes of the referenced data attached to them and can be copied around freely.

Another way is to use GhostCell which controls access through a GhostToken type. The GhostCell can be borrowed immutably but still allow mutable access to its data if the passed in GhostToken is borrowed mutably. This allows for multiple immutable borrows of the same GhostCell that can still be mutably borrowed through the token.

Finally, reference counted types like Rc<RefCell<T>> can be used for links in graph structures. Borrowing doesn’t require passing in a token, but it is done through a borrow() method which does runtime checking.

The GhostToken interface that passes in a token when borrowing can work with all three types. With the index into Vec approach, the Vec is required to borrow using the index, so the Vec can be thought of as the “token” similar to the token passed into the borrow methods of GhostCell. Rc<RefCell<T>> uses a borrow method with no arguments so its token can be the unit type ().

So instead of our Ptr trait having a Deref constraint, we need a more general interface for borrowing from the pointer type with a token parameter. The Borrow and BorrowMut traits below are general enough to work with all of the types mentioned above.

trait BorrowSuper {
    type Ref<'a, U: 'a>: Deref<Target = U>;
}
trait Borrow: BorrowSuper {
    type Token;
    type Target;
    fn get<'a>(&'a self, token: &'a Self::Token) -> Self::Ref<'a, Self::Target>;
}

trait BorrowMutSuper {
    type RefMut<'a, U: 'a>: Deref<Target = U> + DerefMut<Target = U>;
}
trait BorrowMut: BorrowMutSuper + Borrow {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> Self::RefMut<'a, Self::Target>;
}

trait Ptr {
    type T<'a, 'b: 'a, U: 'a>: Borrow<Target = U>;
}

The main differences from the previous pointer trait is that T needs an additional lifetime for the GhostCell’s brand lifetime, Borrow has an associated type for the type of the token to be passed in, and Borrow also needs to abstract over returned reference types because RefCell’s borrow() doesn’t return a borrow but a std::cell::Ref type.

Borrow only splits off its Ref into BorrowSuper to work around issue #87479 which forces a Self: 'a constraint. If this issue didn’t exist we could put Ref directly inside Borrow without any problems.

Now that we have a new pointer trait, the previous tree types and functions can be modified to work with it:

struct Node<'a, 'b: 'a, T: 'a, P: Ptr + 'a> {
    data: T,
    left: Option<P::T<'a, 'b, Node<'a, 'b, T, P>>>,
    right: Option<P::T<'a, 'b, Node<'a, 'b, T, P>>>,
}

impl<'a, 'b, T: Debug, P: Ptr> Node<'a, 'b, T, P> {
    fn print(&self, token: &'a <P::T<'a, 'b, Self> as Borrow>::Token) {
        println!("{:?}", self.data);
        if let Some(ref left) = self.left {
            left.get(token).print(token);
        }
        if let Some(ref right) = self.right {
            right.get(token).print(token);
        }
    }
}

But now cyclical types like graphs can also work:

struct GraphNode<'a, 'b: 'a, T: 'a, P: Ptr + 'a> {
    data: T,
    edges: Vec<P::T<'a, 'b, GraphNode<'a, 'b, T, P>>>,
}

impl<'a, 'b, T: Copy + AddAssign<T>, P: Ptr> GraphNode<'a, 'b, T, P>
where
    P::T<'a, 'b, Self>: BorrowMut<Target = Self> + Clone,
{
    fn incr(this: P::T<'a, 'b, Self>, token: &mut <P::T<'a, 'b, Self> as Borrow>::Token) {
        let data = this.get(token).data;
        let edges = this.get(token).edges.clone();
        for edge in edges.clone() {
            edge.get_mut(token).data += data;
        }
        for edge in edges {
            Self::incr(edge, token);
        }
    }
}

The incr method runs forever with cyclical edges until it overflows the stack. A way to fix that would be to have a hashmap track the visited nodes, but the code right now is sufficient for showing that the Rust compiler will allow working with cyclical edges without errors.

Note that clone is called twice, which is something that would not be necessary if working directly with integer indices. That is because P::T is Clone not Copy. In Rust, Copy doesn’t just mean that you can copy a type like in C++, it also means that a type doesn’t implement Drop. Not having Drop, which is similar to destructors in C++, would simplify the lifetimes of edge in the function, but we can’t use it because some of the pointer types don’t implement Copy, and a custom implementation cannot be provided. So we have to call clone twice in order for it to compile.

Finally we need to implement Borrow and Ptr for our types. Starting off with GhostCell which is the simplest of the three to implement. Borrowing from the token calls the related borrow() function from the GhostCell:

impl<T> BorrowSuper for &GhostCell<'_, T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<'brand, T> Borrow for &GhostCell<'brand, T> {
    type Token = GhostToken<'brand>;
    type Target = T;

    fn get<'a>(&'a self, token: &'a Self::Token) -> &'a Self::Target {
        self.borrow(token)
    }
}

impl<T> BorrowMutSuper for &GhostCell<'_, T> {
    type RefMut<'a, U: 'a> = &'a mut U;
}
impl<'brand, T> BorrowMut for &GhostCell<'brand, T> {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> &'a mut Self::Target {
        self.borrow_mut(token)
    }
}

struct GhostCellPtr;
impl Ptr for GhostCellPtr {
    type T<'a, 'b: 'a, U: 'a> = &'a GhostCell<'b, U>;
}

For the index into Vec approach, the slotmap crate is used for convenience. The key type contains the index into the graph. Since we work with the keys as if they are pointers to nodes in the graph, the key type must be parametrized by the node type.

new_key_type! { struct GraphId; }
struct GraphKey<T> {
    id: GraphId,
    _phantom: PhantomData<T>,
}
type GraphMap<T> = SlotMap<GraphId, T>;

Now we can implement Borrow and BorrowMut for GraphKey using the slotmap as the token. Borrowing from the index borrows from the token (GraphMap) using the key (GraphId), which is the opposite from GhostCell, which borrows from the key (GhostCell) using the token (GhostToken):

impl<T> BorrowSuper for GraphKey<T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<T> Borrow for GraphKey<T> {
    type Token = GraphMap<T>;
    type Target = T;

    fn get<'a>(&'a self, token: &'a Self::Token) -> &'a Self::Target {
        token.get(self.id).unwrap()
    }
}
impl<T> BorrowMutSuper for GraphKey<T> {
    type RefMut<'a, U: 'a> = &'a mut U;
}
impl<T> BorrowMut for GraphKey<T> {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> &'a mut Self::Target {
        token.get_mut(self.id).unwrap()
    }
}

struct GraphKeyPtr;
impl Ptr for GraphKeyPtr {
    type T<'a, 'b: 'a, U: 'a> = GraphKey<U>;
}

Finally, in order to implement Borrow and BorrowMut for Rc<RefCell<T>>, we have to have std::cell::Ref implement Clone. The type already allows for cloning but the trait isn’t implemented because it copies the reference, not the data inside which can be confusing. We implement Clone by creating a newtype CellRef that wraps std::cell::Ref:

struct CellRef<'a, T>(std::cell::Ref<'a, T>);
impl<T> Deref for CellRef<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        self.0.deref()
    }
}
impl<T> Clone for CellRef<'_, T> {
    fn clone(&self) -> Self {
        Self(std::cell::Ref::clone(&self.0))
    }
}

Now we can implement Borrow and BorrowMut that call the RefCell’s borrow() and borrow_mut() methods:

impl<T> BorrowSuper for Rc<RefCell<T>> {
    type Ref<'a, U: 'a> = CellRef<'a, U>;
}
impl<T> Borrow for Rc<RefCell<T>> {
    type Token = ();
    type Target = T;

    fn get<'a>(&'a self, _token: &'a Self::Token) -> Self::Ref<'a, Self::Target> {
        CellRef(self.borrow())
    }
}
impl<T> BorrowMutSuper for Rc<RefCell<T>> {
    type RefMut<'a, U: 'a> = std::cell::RefMut<'a, U>;
}
impl<T> BorrowMut for Rc<RefCell<T>> {
    fn get_mut<'a>(&'a self, _token: &'a mut Self::Token) -> Self::RefMut<'a, Self::Target> {
        self.borrow_mut()
    }
}
struct RcRefCellPtr;
impl Ptr for RcRefCellPtr {
    type T<'a, 'b: 'a, U: 'a> = Rc<RefCell<U>>;
}

With these implementations, we can get the print() and incr() methods to compile with ghostcells, slotmaps, and reference counted pointers. The code for testing each implementation is shown here.

It may seem like the Ptr, Borrow, and BorrowMut traits are capable of working with every possible way to encode mutable cyclical data. However, there is another way to work with cycles in Rust. The Cell type allows for the data inside to be mutated through an immutable reference as long as the inner data implements Copy. Here are some examples of defining our previously used tree and graph node types using Cell:

struct Node<'a, T: Copy> {
    data: Cell<T>,
    left: Cell<Option<&'a Node<'a, T>>>,
    right: Cell<Option<&'a Node<'a, T>>>,
}

struct GraphNode<'a, T: Copy> {
    data: Cell<T>,
    edges: Cell<StackVec<&'a GraphNode<'a, T>, 100>>,
}

impl<'a, T: Copy + Add<Output = T>> GraphNode<'a, T> {
    fn incr(&self) {
        let data = self.data.get();
        let edges = self.edges.get();
        for i in 0..edges.len() {
            edges.get(i).data.update(|v| v + data);
        }
        for i in 0..edges.len() {
            edges.get(i).incr();
        }
    }
}

Some things to notice about these examples:

The structure of mutable cyclical types with Cell is fundamentally different from the other pointer-like types. So although the Ptr trait can work with many common types used for cyclical structures, it doesn’t work with Cell.

Conclusion

Is it worth it to go through the effort to abstract out pointer-like types in this manner? For things like abstract syntax trees, I think so. Using tracked separate allocations for the recursive children of a tree node with something like Rust’s Box is often the easiest way to get started, but it’s common to run into issues like the destructor overflowing the stack for large ASTs or time being spent dropping each node when the whole AST can be dropped at once. I inevitably end up moving to an arena allocation strategy for AST nodes, and a little time spent upfront abstracting the pointer children types can save a lot of time with this refactor. For graphs, I think this technique is less useful. It’s pretty uncommon to change the childen pointer types for graph nodes and even the abstracted type won’t support Cell which is common for cyclical types.

Although this technique seems pretty useful to me for certain use cases, it would be pretty difficult to use this in a production setting because it looks complicated, and you generally only get benefits if you opt into it from the very beginning. Most engineers have a YAGNI (you aren’t going to need it) mindset which would make it very difficult for anyone to sign on to this idea from the very beginning of a project. Because of this, I actually think that only having a single pointer type like C is the most practical way to write code that is reusable across different allocation strategies, because most code that works with pointers and doesn’t call specific memory management functions like free can be reused out of the box. With C++ and Rust, people would most likely hardcode their project to a specific memory management type and then use AI to rewrite the project if their assumptions change. Still, I think its interesting that these languages have powerful enough type systems to allow this kind of abstraction.