Questions on pointer type for merging of linked list problem in Elements of programming interviews.

[Paul]

Elements of Programming Interviews gives the following code for merging linked lists. My questions are: Is it ok for merge_sorted_linked_lists to use call by reference instead of call by value? Also, are std::unique_ptr or raw pointers ok besides the author's use of shared pointers? Would unique pointers be preferable?
Can we use unique pointers by simply using std::move for every assignment? For example, if we use unique pointers, do we replace tail->next = n; by tail->next = std::move(n); Does that approach work straightforwardly or are there complications, necessitating shared instead of unique pointers?
Many thanks for your help.

Paul

BEGIN QUOTE
template <typename T>
void append_node(shared_ptr<node_t<T> >& head, shared_ptr<node_t<T> >& tail,
shared_ptr<node_t<T> >& n)
{
head ? tail->next = n : head = n;
tail = n;
}

template <typename T>
void append_node_and_advance(shared_ptr<node_t<T> >& head, shared_ptr<node_t<T> >& tail,
shared_ptr<node_t<T> >& n)
{
append_node(head, tail, n);
n = n->next;
}

template <typename T>
shared_ptr<node_t<T> > merge_sorted_linked_lists(shared_ptr<node_t<T> F>, shared_ptr<node_t<T> > L)
{
shared_ptr<node_t<T> sorted_head = nullptr, tail = nullptr;

while(F&&L)
append_node_and_advance(sorted_head, tail, F->data < L->data ? F : L);
if(L)
append_node(sorted_head, tail, L);

if(F)
append_node(sorted_head, tail, F);

return sorted_head;

}

}

[Paul]

On Tuesday, July 28, 2015 at 10:39:11 PM UTC+1, Paul wrote:
> Elements of Programming Interviews gives the following code for merging linked lists. My questions are: Is it ok for merge_sorted_linked_lists to use call by reference instead of call by value? Also, are std::unique_ptr or raw pointers ok besides the author's use of shared pointers? Would unique pointers be preferable?
> Can we use unique pointers by simply using std::move for every assignment? For example, if we use unique pointers, do we replace tail->next = n; by tail->next = std::move(n); Does that approach work straightforwardly or are there complications, necessitating shared instead of unique pointers?
> Many thanks for your help.
>
> Paul

I see some typos in the above code. Sorry, I'll try to correct these.

template <typename T>
void append_node(shared_ptr<node_t<T> >& head, shared_ptr<node_t<T> >& tail,
shared_ptr<node_t<T> >& n)
{
head ? tail->next = n : head = n;
tail = n;
}

template <typename T>
void append_node_and_advance(shared_ptr<node_t<T> >& head, shared_ptr<node_t<T> >& tail,
shared_ptr<node_t<T> >& n)
{
append_node(head, tail, n);
n = n->next;
}

template <typename T>

shared_ptr<node_t<T> > merge_sorted_linked_lists(shared_ptr<node_t<T> > F, shared_ptr<node_t<T> > L)

[Paul]

On Tuesday, July 28, 2015 at 10:44:44 PM UTC+1, Paul wrote:
...
Hopefully, final attempt to get this right:

[Alf P. Steinbach]

On 28-Jul-15 11:38 PM, Paul wrote:
> are std::unique_ptr or raw pointers ok besides the author's use of shared pointers?

I can't think of any application of a DIY linked list where smart
pointers would be appropriate for linking up the nodes. At the design
level it's inappropriate because the linked list is an owner of its
nodes. At the coding/implementation level it's inappropriate because
it's more verbose and hence less maintainable code, and also (but
secondary) just needless memory and possibly execution time overhead.

However, no rule without exception.

But on the third and gripping hand, the question is not whether raw
pointers are OK, it's whether the author's use of shared pointers is OK,
and that's at least highly questionable.

Cheers & hth.,

- Alf

--
Using Thunderbird as Usenet client, Eternal September as NNTP server.

[Öö Tiib]

On Wednesday, 29 July 2015 02:18:33 UTC+3, Alf P. Steinbach wrote:
> On 28-Jul-15 11:38 PM, Paul wrote:
> > are std::unique_ptr or raw pointers ok besides the author's use of shared pointers?
>
> I can't think of any application of a DIY linked list where smart
> pointers would be appropriate for linking up the nodes. At the design
> level it's inappropriate because the linked list is an owner of its
> nodes. At the coding/implementation level it's inappropriate because
> it's more verbose and hence less maintainable code, and also (but
> secondary) just needless memory and possibly execution time overhead.

There may be cases where such design makes best sense and when it
makes sense then it usually simplifies coding as well. I can think of
two:

1) Case when element is most logical owner of next element.
Singly linked list is technically subcase of tree. Sort of one-branched tree.
If trunk interacts with its branch then a reference makes sense. If trunk
owns the branch then smart pointer makes sense as that reference.

2) Case when neither elements nor the list own elements.
Elements are owned by something outside but sometimes form such
temporary lists. Intrusive list may perform better and make better sense
than list of pointers. Non-owning 'std::unique_ptr' may be used there as
link between elements to signal the "something outside" that element has
left such list.

Performance-wise there is very little difference between 'unique_ptr' and
raw ... it is 'shared_ptr' that is fat.