隣接リストグラフの構築におけるポインタの極端な使用?

Aug 25 2020

のポインタをいじってC++、隣接リストグラフを実装しました。

データをヒープに配置しようとして、行き過ぎ/極端になりすぎていませんか?

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);
}
```

回答

5 G.Sliepen Aug 25 2020 at 02:32

データをヒープに配置しようとして、行き過ぎ/極端になりすぎていませんか?

はい。コンテナはstd::unordered_mapstd::forward_listコンテンツをヒープに保存します。std::unordered_mapスタックでを宣言すると、ほんの少しの管理データだけがスタックに送られます。しかし、同じことがstd::unique_ptr。でも起こります。したがって、コードでの使用std::unique_ptrは不要であり、間接参照を増やすだけであり、パフォーマンスに悪影響を与える可能性があります。だからただ書く:

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