Список Deque с промежуточным замком среди них

Question

Я хочу спроектировать структуру данных, в которой у меня есть промежуточные объекты блокировки среди элементов. Эти замки являются общими для двух соседних элементов.

E (i) - deque, где добавление элемента к нему контролируется B(i) и B(i+1). Е можно разделить. E (i) и E(i+1) могут быть объединены в E (i) с удалением B(i+1). Удаление E запрещено.

Какова будет лучшая структура данных для этого в C++.

Answer 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. До тех пор вы должны будете реализовать самостоятельно или зависеть от третьей стороны.

Проблема этого подхода заключается в том, что структура данных по своей сути не обеспечивает инвариант ребер, соседствующих только с узлами, а узлы только с соседними ребрами, поэтому вам все равно придется реализовать свой собственный набор алгоритмов.

---

Параллельные структуры для ребер и узлов являются типичным способом реализации графа. Ваш список - это просто особый случай графа, который имеет ровно два ребра для каждого узла.