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

Question

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

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

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

Answer 1

Стандартная библиотека не имеет неоднородные структуры данных. У вас есть три подхода: выполните одно из них, используйте однородную структуру, содержащую объекты с тегом union type, или используйте две параллельные структуры.

Минимальный пример гетерогенного списка:

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

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

---

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