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, ... 
}; 

My圖表與數據，不刪除/插入/更新操作將初始化後應用充滿一次。

如果有更好的數據結構的方法，我不提，隨時賜教:)

Answer 1

這種做法似乎更經濟：

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

的原因：

1. map < A，vector>必須保存A（作爲關鍵字）的副本，因此會擴大內存需求，特別是如果名稱長且具有描述性。

2. 在遍歷節點時，您在任何給定時間都知道當前的A，並且可以直接訪問鏈接的集合/矢量;在地圖上你必須查看鏈接的集合/向量，這將浪費時間。