4
\$\begingroup\$

Playing around with pointers in C++, implemented an adjacency list graph.

Am I going too far/extreme trying to place data onto the heap?

graph.h

#include <memory>
#include <unordered_map>
#include <forward_list>
#include <utility>

template <typename TKey, typename TWeight>
class Graph{

    struct Adjacent {
        TKey key;
        TWeight weight;
        Adjacent(const TKey key, const TWeight weight): key(key), weight(weight) {};
    };

    struct Vertex {
        TKey value;
        std::unique_ptr<std::forward_list<Adjacent>> adjVertexList;
        explicit Vertex(const TKey value){
            this->value = value;
            adjVertexList = std::make_unique<std::forward_list<Adjacent>>();
        }
    };

private:
    // Since keys can be non-numeric,
    // use a hashmap to index into individual adj lists
    std::unordered_map<TKey, std::unique_ptr<Vertex>> vertices;

public:
    void addVertex(TKey value);

    // Everything other than addDirectedEdge is just for a nicer API
    void addDirectedEdge(TKey src, TKey dst, TWeight weight);
    void addUndirectedEdge(TKey src, TKey dst, TWeight weight);
    void addDirectedEdge(TKey src, TKey dst);
    void addUndirectedEdge(TKey src, TKey dst);

};

graph.cpp

#include <stdexcept>
#include "graph.h"

template <typename TKey, typename TWeight>
void Graph<TKey, TWeight>::addVertex(TKey value) {
    vertices.insert(std::make_pair(value, std::make_unique<Vertex>(value)));
}

template <typename TKey, typename TWeight>
void Graph<TKey, TWeight>::addDirectedEdge(TKey src, TKey dst, TWeight weight) {

    auto srcPtr = vertices.find(src);

    if(srcPtr == vertices.end())
        throw std::invalid_argument("Cannot find source");
    else if(vertices.find(dst) == vertices.end())
        throw std::invalid_argument("Cannot find destination");

    Vertex* vertex = srcPtr->second.get();
    vertex->adjVertexList->push_front(Adjacent(dst, weight));

}

template <typename TKey, typename TWeight>
void Graph<TKey, TWeight>::addUndirectedEdge(TKey src, TKey dst, TWeight weight) {
    addDirectedEdge(src, dst, weight);
    addDirectedEdge(dst, src, weight);
}

template <typename TKey, typename TWeight>
void Graph<TKey, TWeight>::addDirectedEdge(TKey src, TKey dst) {
    addDirectedEdge(src, dst, 0);
}

template <typename TKey, typename TWeight>
void Graph<TKey, TWeight>::addUndirectedEdge(TKey src, TKey dst){
    addUndirectedEdge(src, dst, 0);
}
```
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Am I going too far/extreme trying to place data onto the heap?

Yes. Containers like std::unordered_map and std::forward_list already store contents on the heap. If you declare a std::unordered_map on the stack, only a little bit of administrative data goes on the stack. But the same happens with std::unique_ptr. So in your code, the use of std::unique_ptr is superfluous and only increases indirection, which might be bad for performance. So just write:

template <typename TKey, typename TWeight>
class Graph {
    ...
    struct Vertex {
        ...
        std::forward_list<Adjacent> adjVertexList;
        ...
    };
    ...
    std::unordered_map<TKey, Vertex> vertices;
    ...
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.