CODEWITHSUNDEEP
c++c++11stl
SX.
SX.

Reputation: 91

map<A, set<A*>> vs. set<A> where A holds set of A*

I'd like to represent a graph in C++.

I'm parsing my input data which are (1) the nodes and (2) the connections between the nodes.

My question is about the data structure to hold the nodes and the connections:

My first approach was a kind of linked list I knew from C but using STL containers: A class A holding the name of the node and a std::set<A*> to store pointers to the connected nodes. Something like this (not compilable, just a draft of the idea):

class A
{
    private:
        std::string name;
        std::set<A*> links;

    public:
        // constr., destr., getter, setter, ...
};

My second thought was a std::map<A, std::set<A*> > or even std::map<A, std::vector<A*> > which in my opinion would be the better approach in this case.

Of course the class A in this case would hold only the name:

class A
{
    private:
        std::string name;

    public:
        // constr., destr., getter, setter, ...
};

My graph is filled once with data, no delete/insert/update operations will be applied after the initialisation.

If there is a better data structure approach I did not mention, feel free to enlighten me :)

Upvotes: 0

Views: 84

Answers (1)

Michael
Michael

Reputation: 5897

This approach seems more economical:

class A
{
    std::string name;
    std::vector<A*> links;
}

The reasons:

  1. map< A, vector > would have to hold a copy of A (as the key), thus bloating memory requirements, especially if the names are long and descriptive.

  2. When traversing the nodes you know the current A at any given time, and have direct access to the set/vector of links; with the map you'd have to look up the set/vector of links, which would be a waste of time.

Upvotes: 1

Related Questions