I'm faced with a design choice for a singly linked list class. The rough idea is this:
template<typename T>
class List {
public:
...
private:
struct Node {
std::shared_ptr<const T> value;
std::shared_ptr<const Node> next;
};
std::shared_ptr<const Node> node_;
};
Yes I know there are a lot of shared_ptrs wandering around, but that's because List is a functional persistent data structure that needs as much structural sharing as possible. In this implementation, for example, reversing a list does not require copying any elements, and multiple lists can share a common sub-list (by pointing to a same shared_ptr tail).
That being said, I still feel there are perhaps too many shared_ptrs. Is there anyway to reduce the number of shared_ptrs used while still enabling structural sharing? Something like combining the two shared_ptrs inside a Node to reduce the overhead of control blocks... I don't know, maybe there isn't a way, or maybe there is. Any idea is welcome, even about redesigning the List class altogether.
