Suppose I'm building a program that will hold a graph defined by Edge and Vertex objects, each with their own data and functionality. The edges and vertices are each stored in a vector of pointers, and since we want to do modern C++ these will be shared pointers, not naked pointers. Each edge is defined by two vertices and must include pointers to those vertices, and each vertex must also contain a list of all edges connected to it.
The complication is that I would like these relationships to be automatic and unavoidable: you cannot create an edge without associating it with two vertices nor without associating the two vertices to the new edge.
With a vector of naked pointers I feel like this is very easy:
#include <vector>
using std;
class Edge;
class Vertex {
public:
Vertex=default;
void addEdge(Edge* p_edge) { m_edges.push_back(p_edge); }
private:
vector<Edge*> m_edges;
};
class Edge {
public:
Edge(Vertex* p_vertex0, Vertex* p_vertex1):
m_vertices{p_vertex0, p_vertex1}
{
//Associate each vertex with the new edge everytime ctor is called
p_vertex0->addEdge(this);
p_vertex1->addEdge(this);
}
private:
std::pair<Vertex*,Vertex*> m_vertices;
};
int main() {
vector<Vertex*> vertexList;
//...Initialize list of vertices...
//Add an edge
int index0 = 0, index1 = 1; //arbitrary
vector<Edge*> edgeList;
edgeList.push_back(new Edge(vertexList[index0], vertexList[index1]));
}
But when using shared pointers, what I want the vertices to have is the shared pointer for the edge, not the naked pointer, but when the ctor for the Edge is called the shared pointer doesn't exist yet, and I'm left doing this:
#include <memory>
#include <vector>
using std;
class Edge;
class Vertex {
public:
Vertex=default;
void addEdge(shared_ptr<Edge> p_edge) { m_edges.push_back(p_edge); }
private:
vector<shared_ptr<Edge>> m_edges;
};
class Edge {
public:
Edge(shared_ptr<Vertex> p_vertex0, shared_ptr<Vertex> p_vertex1):
m_vertices{p_vertex0, p_vertex1}
{
//Cannot add edge to vertices here because we don't have the shared_ptr yet
}
private:
pair<shared_ptr<Vertex>,shared_ptr<Vertex>> m_vertices;
};
int main() {
vector<shared_ptr<Vertex>> vertexList;
//...Initialize list of vertices...
//Add an edge
vector<shared_ptr<Edge>> edgeList;
int index0 = 0, index1 = 1; //arbitrary
edgeList.push_back(make_shared<Edge>(vertexList[index0], vertexList[index1]));
//Manually associate each vertex with new edge
auto vertex0 = vertexList[index0];
(*vertex0)->addEdge(edgeList.back());
auto vertex1 = vertexList[index1];
(*vertex1)->addEdge(edgeList.back());
}
This "works", but it is very unsecure in that it's easy to end up with onesided or mismatched relationships if you don't remember to make those calls every time you create a new edge.
So is there some way to ensure that everytime a shared_ptr is created, anywhere, anytime, that the associated vertices are given the shared_ptr corresponding to the new edge?
Manual overhead notwithstanding, your Edges and Vertices have shared_ptr's into each other. That means they will very likely leak unless you take manual precaution.
This indicates that shared_ptr might not be the most suitable tool here. Also, it requires each vertex and edge to be allocated separately, which is not great.
I would recommend a more lightweight design:
std::vector<std::optional<Vertex>> vertices;
std::vector<std::optional<Edge>> edges;
std::vector<std::size_t> freeListV; // unused vertex-slots
std::vector<std::size_t> freeListE; // unused edge-slots
struct Vertex {
std::vector<std::size_t> neighbours; // index into edges vector
};
struct Edge {
std::array<std::size_t, 2> vertices; // indices into vertices vector
WeightType w;
};
void addEdge(std::size_t i0, std::size_t i1, WeightType w) {
// make sure no such edge exists
if (freeListE.empty()) {
freeListE.push_back(edges.size());
edges.push_back(std::nullopt);
}
auto const eid = freeListE.back();
freeListE.pop_back();
auto& edge = edges[eid];
edge = Edge{std::array{i0,i1}, std::move(w)};
vertices[i0].push_back(eid);
vertices[i1].push_back(eid);
}
You can delete an edge/vertex by assigning std::nullopt to its slot in the corresponding vector. Make sure no vertex/edge points to it before nulling it. If you don't need to ever delete an edge/vertex, you can completely do without the freeLists.
The advantage: much less indirection, cache-locality, no danger of leaks.