0

我想设计一个数据结构，其中我在元素之间有中间锁实体。这些锁对于两个相邻的元素是通用的。

E(i) 是双端队列，其中添加元素由 B(i) 和 B(i+1) 控制。E 可以拆分。E(i) 和 E(i+1) 可以合并形成 E(i)，去除 B(i+1)。禁止删除 E。

在 C++ 中，最好的数据结构是什么。

图表

4

1 回答 1

1

标准库没有异构数据结构。您有三种方法：自己实现一个，使用包含标记联合类型的对象的同构结构，或使用两个并行结构。

异构列表的最小示例：

template<class T,class E>
struct node;

template<class T, class E>
struct edge {
    node<T, E> *prev, *next;
    E data;
};

template<class T, class E>
struct node {
    edge<T, E> *prev, *next;
    T data;
};

template<class T, class E>
struct fancy_list {
    edge<T, E> *head, *tail;
};

struct wagon {
    // wagon members
};
struct boundary {
    // boundary members
};

int main() {
   fancy_list<wagon, boundary> wagons;
}

这些算法的工作方式与同类列表的算法基本相同，但是您必须制定一种策略来处理节点的删除（是否删除了一条边？哪一条？或者它们是否合并？如何？）和插入（插入之前还是在现有边缘之后？将现有边缘成员复制到新边缘成员，或设置默认状态？）等。没有明确定义的用例，就没有“正确”或“最佳”解决方案。

std::variant在 C++17 中将引入标记联合实现。在此之前，您将不得不自己实施，或依赖第三方。

这种方法的问题在于，数据结构本身并没有强制执行仅与节点相邻的边和仅与相邻边相邻的节点的不变量，因此无论如何您都需要实现自己的一组算法。

边和节点的并行结构是实现图的典型方式。您的列表只是图的一个特例，每个节点恰好有两条边。

于 2017-02-07T11:31:51.197 回答