List of Deque with intermediate lock among them

Question

I want to design a data structure where I have intermediate lock entities among elements. These locks are common to the two adjacent elements.

E(i) are deque where addition of element to it controlled by B(i) and B(i+1). E can be split. E(i) and E(i+1) could be merged to form E(i) with removal of B(i+1). Removal of E is forbidden.

What will be the best data structure for this in C++.

Answer 1

Standard library has no heterogeneous data structures. You have three approaches: Implement one yourself, use a homogeneous structure that contains objects of a tagged union type, or use two parallel structures.

A minimal example of a heterogeneous list:

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;
}

The algorithms will work mostly the same way as algorithms for homogeneous lists, but you will have to develop a strategy for dealing with removal of nodes (Is one edge removed? Which one? Or are they merged? How?) and insertion (insert before or after existing edge? Copy existing edge members to the new one, or set a default state?) etc. There are no "right" or "best" solutions without a well defined use case.

---

A tagged union implementation std::variant will be introduced in the C++17. Until then you will have to implement your own, or depend on a third party.

The problem with this approach is that the data structure doesn't inherently enforce the invariant of edges neighboring only nodes and nodes only neighboring edges, so you will need to implement your own set of algorithms anyway.

---

The parallel structures for edges and nodes is a typical way of implementing a graph. Your list is simply a special case of graph that has exactly two edges for each node.