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

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，有更优雅的方法来编码此类算法（使用 lambda）。