C++: Pointer vs. Reference Design Question

Background

I constantly struggle with when to use pointers versus references in good software design. I'm hoping an example taken from the code I'm writing will help me solidify best practices through peoples' answers.

I have the following classes. Assume public getters for all fields that return the same type as the fields are declared with. For reasons I'd rather not get into, know that I also cannot easily combine the geometry and node classes. Also, ignore the fact that pointers are raw pointers. That's just for simplicity in the example.

// A 2D point
class Point {
private:
    double _x;
    double _y;
};

// A 2D edge. Edges refer to any trapezoids above and below themselves.
class Edge {
private:
    Point* _point1;
    Point* _point2;
    Trapezoid* _above;
    Trapezoid* _below;
};

// A 2d Trapezoid. Trapezoids refer to their place in the tree structure
class Trapezoid {
private:
    Point* _left;
    Point* _right;
    Edge* _top;
    Edge* _bottom;
    TrapezoidNode* _graphNode;
};

// Abstract Node
class Node {
protected:
    Node* _leftChild;
    Node* _rightChild;
};

// Node representing a point
class PointNode : public Node {
private:
    Point* _point;
};

// Node representing an edge
class EdgeNode : public Node {
private:
    Edge* _edge;
};

// Node representing a trapezoid
class TrapezoidNode : public Node {
private:
    Trapezoid* _trap;
};

The algorithm I'm writing takes in a starting Trapezoid and initializes a tree structure with a single TrapezoidNode representing that trapezoid. It also stores that Trapezoid in an unordered_set so that I can easily know what trapezoids exist in the tree at any point in time. From there, I begin breaking down nodes in the tree, replacing them with smaller subtrees consisting of PointNodes, EdgeNodes, and TrapezoidNodes. This process involves the creation of new Points, Edges, and Trapezoids that those nodes refer to. I also keep the unordered_set up-to-date with any new trapezoids that get created.

Key Questions

1. For the Edge and Trapezoid classes, would it make more sense to use references to Points and Edges (respectively) instead of pointers?

   • The main problem is the lifetime of some of these objects. There are some edges whose life extends beyond that of the trapezoids they become a part of. This suggests the use of pointers, since the trapezoid does not own those edges. Other edges, however, are created for the sole purpose of creating a new trapezoid with limited lifetime. This suggests the use of references, since the lifetime of these edges are tied to the trapezoid that contains them.

2. For my set of trapezoids, it better design to:

   • A) Use an unordered_set<Trapezoid> and make sure when I create TrapezoidNodes, that I am pointing to the heap memory managed by that set... or

   • B) Manually allocate heap memory for new Trapezoids and use an unordered_set<Trapezoid*> (which requires me to write a hashing function for Trapezoid* instead of Trapezoid

As shown above, my current implementation is to use pointers everywhere.