创建自定义图形数据结构是否违反任何原则？

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）。