map <A, set<A*>> vs. set <A> где A содержит набор A *

Question

Я хотел бы представить график на C++.

Я разбираю свои входные данные, которые являются (1) узлами и (2) соединениями между узлами.

Мой вопрос о структуре данных, чтобы удерживать узлы и соединения:

Мой первый подход был своего рода связанный список, я знал, что из C, но с использованием STL контейнеров: class A держащие имя узла и std::set<A*> для хранения указателей на подключенные узлы. Что-то вроде этого (не компилируется, только проект идеи):

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

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

Моя вторая мысль была std::map<A, std::set<A*> > или даже std::map<A, std::vector<A*> > на мой взгляд, было бы лучше подход в данном случае.

Конечно, class A в этом случае будет содержать только имя:

class A 
{ 
    private: 
     std::string name; 

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

Мой график заполняется один раз с данными, никакие операции удаления/вставки/обновления будут применены после инициализации.

Если есть лучшая структура данных подход, который я не упомянул, не стесняйтесь, чтобы просветить меня :)

Answer 1

Такой подход представляется более экономичным:

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

Причины:

1. map < A, vector> должен был бы держать копию A (как ключ), тем самым вздувая требования к памяти, особенно если имена длинны и описательны.

2. При перемещении узлов, которым вы знаете текущий A в любой момент времени, и имеете прямой доступ к множеству/вектору ссылок; с картой вам придется искать набор/вектор ссылок, что было бы пустой тратой времени.