創建自定義圖形數據結構是否違反任何原則？

Question

我正在使用連續方法開展與電路測試相關的小型科學課程項目。該程序將解析電路定義文件，然後構建一個易於修改的圖形結構來表示電路。然後對該圖進行某些修改，並對其進行拓撲排序。排序後，圖形轉換爲一個由數組列表構成的靜態結構，每個數組對應一定的拓撲排序程度。之後，可以很容易地模擬電路，因爲您可以依賴排序順序並按順序處理模型。

現在是所有好的和邏輯，但我所提到的兩個圖是自定義的數據結構，其中：

1）不建挺到STL規範（是漫長和艱難的，我反正 - 圖比向量和列表複雜得多）

2）對於第二個圖，我假設它是不可修改的，並使用矢量向量或向量列表來獲得速度。

3）我的圖表可用的一組操作是有限的，反映了我的項目需求。

4）代碼很簡單。

現在我只是一個三年級學生的IT和軟件設計和閱讀一些現實生活中的代碼後，成就了一個療程後，我在想：

1）能夠（或者甚至可能）的代碼如此簡單？

2）不要因爲假設數據結構而違反軟件設計的數以千計的原則嗎？

3）我應該真的總是符合我在這個和未來的項目中創建的所有數據結構的STL規範嗎？

該項目使用C++。

感謝您的關注！我希望對這些問題有一個基本的和理論上的答案，以及這個問題的實際解決方案的例子。

Answer 1

1）可以（甚至可以）代碼簡單嗎？

不僅可以，它應該是。代碼不需要很複雜。

2）不要因爲假設數據結構而違反數以千計的軟件設計原則嗎？

恩，你會怎麼做。這個問題對我沒有意義。

3）我應該真的總是遵從STL規範來說明我在這個和未來的項目中創建的所有數據結構嗎？

沒有。例如，如果您不需要迭代結構，則不要提供迭代器。只實現你實際需要的東西。

Answer 2

我認爲沒有錯用一個簡單的設計是這樣的：

typedef int node_type; // or a more complex type here 
typedef std::list<node_type> node_list; 
typedef std::pair<node_list::const_iterator, node_list::const_iterator> edge_type; 
typedef std::list<edge_type> edge_list; 

struct graph 
{ 
    node_list nodes; 
    edge_list edges; 

    // Some member functions for doing specific things here 
    // for instance: 
    void remove_node(node_list::iterator i) 
    { 
     nodes.erase(i); 
     edges.remove_if(connects(i)); 
    } 
}; 

其中

struct connects 
{ 
    connects(node_list::const_iterator i) : i(i) {} 

    bool operator()(const edge_type& e) const 
    { 
     return e.first == i || e.second == i; 
    } 

private: 
    node_list::const_iterator i; 
}; 

它保持簡單，模塊化，並允許您使用標準庫就可以了。它允許你迭代節點和邊。如果你想要一個頂點的鄰接列表，你將不得不遍歷整個邊界列表，但這是設計的（如果你想快速完成這個，你需要一個更好的結構）。

例如，定義（這個人是不幸的是沒有標準）

template <typename I, typename F, typename G> 
F for_each_if(I first, I last, F f, G pred) 
{ 
    for (; first!=last; ++first) if (pred(*first)) f(*first); 
    return f; 
} 

，現在你可以做

for_each_if(g.edges.begin(), g.edges.end(), something, connects(some_node)); 

遍歷的some_node鄰接表。

使用C++ 0x有更優雅的方法來編碼這些算法（使用lambdas）。