Sharing a `std::list` without adding a (redundant) reference to it-CodePudding

I have a conainter, lets say a std::list<int>, which I would like to share between objects. One of the objects is known to live longer than the others, so he will hold the container. In order to be able to access the list, the other objects may have a pointer to the list. Since the holder object might get moved, I'll need to wrap the list with a unique_ptr:

class LongLiveHolder { std::unique_ptr<std::list<int>> list; };
class ShortLiveObject { std::list<int>& list; };

However, I don't really need the unique_ptr wrapper. Since the list probably just contains a [unique_ptr] pointer to the first node (and a pointer to the last node), I could, theoretically, have those pointers at the other objects:

class LongLiveHolder { std::unique_ptr<NonExistentListNode<int>> back; };
class ShortLiveObject { NonExistentListNode<int>& back; };

, which would save me a redundant dereference when accessing the list, except that I would no longer have the full std::list interface to use with the shorter-lived object- just the node pointers.

Can I somehow get rid of this extra layer of indirection, while still having the std::list interface in the shorter-lived object?

CodePudding user response：

If the list owner will be moved, then you need some memory address to share somehow.

You already indicated the unique_ptr. It's a decent solution if the non-owners don't need to save it internally.

The std::shared_ptr is an obvious alternative.

Finally, you can have a std::shared_ptr in the owner object, and pass std::weak_ptr to non-owners.

CodePudding user response：

Preface

I think you may be overthinking the cost of the extra indirection from the std::unique_ptr. In general, I'd first trust my compiler to do smart things. If you want to know the cost, do performance profiling.

The main purpose of the std::unique_ptr in this use-case is just to have shared data that doesn't move when other data that references gets moved. If you use the list member of the long-lived object multiple times in a single procedure, you can possibly help your compiler to help you (and also get some nicer-to-read code) when you use the list through the long-lived object by making a variable in the scope of the procedure that stores a reference to the std::list pointed to by the std::unique_ptr like:

void fn(LongLiveHolder& holder) {
  auto& list {holder.list.get()};
  list.<some_operation_1>(...);
  list.<some_operation_2>(...);
  list.<some_operation_3>(...);
}

But again, you should inspect the generated machine code and do performance profiling if you really want to know what kind of difference it makes.

Possible Solution: Write your own List

You said:

However, I don't really need the unique_ptr wrapper. Since the list probably just contains a [unique_ptr] pointer to the first node (and a pointer to the last node), I could, theoretically, have those pointers at the other objects: [...]

I'm pretty sure a std::list can't just hold pointers to front and back nodes. For one thing, since c 11 requires that std::list::size() is O(1), std::list probably has to keep track of its size at all times in a counter member- either storing it in itself, or doing some kind of size-tracking in each node struct, or some other implementation-defined behaviour. I'm pretty sure the simplest and most performant way to have multiple moveable references (non-const pointers) to something that needs to do this kind of bookkeeping is to just add another level of indirection.

You could try to "skip" the indirection layer required by the bookkeeping for specific cases that don't require that information, which is the iterators/node-pointers approach, which I'll discuss later. I can't think of a better place or way to store that bookkeeping other than with the collection itself. Ie. If the list interface has requirements that require such bookkeeping, an extra layer of indirection for each user of the list implementation has a very strong design rationale.

If you don't care about having O(1) to get the size of your list, then you can write your own List class and make your own context-specific optimizations. That's one of the big selling-points of languages like C : You get a nice standard library that does commonly useful things, and when you have a specific scenario where some features of those tools aren't required and are resulting in unnecessary overhead, you can build your own tool/abstraction (or possibly use someone else's library).

Commentary on `std::unique_ptr` reference

Your first snippet works, but you can probably get some better implicit constructors and such for SortLiveObject by using std::reference_wrapper, since the default implicity-declared copy-assignment and default-construct functions get deleted when there's a reference member.

class LongLiveHolder { std::unique_ptr<std::list<int>> list; };
class ShortLiveObject { std::reference_wrapper<std::list<int>> list; };

Commentary on `std::shared_ptr` `std::weak_ref`

Like @Adrian Maire suggested, std::shared_ptr in the longer-lived, object which might move while the shorter-lived object exists, and std::weak_ptr in the shorter-lived object is a working approach, but it probably has more overhead (at least coming from the ref-count) than using std::unique_ptr a reference, and I can't think of any generalized pros, so I wouldn't suggest it unless you already had some other reason to use a std::shared_ptr. In the scenario you gave, I'm pretty sure you do not.

Commentary on Storing iterators/node-pointers in the short-lived object

@Daniel Langr already commented about this, but I'll try to expand.

Specifically for std::list, there is a possible standard-compliant solution (with several caveats) that doesn't have the extra indirection of the smart pointer. Caveats:

You must be okay with only having an iterator interface for the shorter-lived object (which you indicated that you are not).
The front and back iterators must be stable for the lifetime of the shorter-lived object. (the iterators should not be deleted from the list, and the shorter-lived object won't see new list entries that are pushed to the front or back by someone using the longer-lived object).

From cppreference.com's page for std::list's constructors:

After container move construction (overload (8)), references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this. The current standard makes this guarantee via the blanket statement in [container.requirements.general]/12, and a more direct guarantee is under consideration via LWG 2321.

From cppreference.com's page for std::list:

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

But I am not a language lawyer. I could be missing something important.

You replied to Daniel saying:

Some iterators get invalid when moving the container (e.g. insert_iterator) @DanielLangr

Yes, so if you want to be able to make std::input_iterators, use the std::unique_ptr reference approach and construct short-lived std::input_iterators when needed instead of trying to store long-lived ones.