Digest for comp.lang.c++@googlegroups.com - 4 updates in 1 topic

comp.lang.c++@googlegroups.com

Google Groups

Topic digest
View all topics

• Questions on pointer type for merging of linked list problem in Elements of programming interviews. - 4 Updates

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

Paul <pepstein5@gmail.com>: Jul 28 02:38PM -0700 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 <pepstein5@gmail.com>: Jul 28 02:44PM -0700 On Tuesday, July 28, 2015 at 10:39:11 PM UTC+1, Paul wrote: > 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) { 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 <pepstein5@gmail.com>: Jul 28 02:48PM -0700 On Tuesday, July 28, 2015 at 10:44:44 PM UTC+1, Paul wrote: ... Hopefully, final attempt to get this right:   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;   }

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jul 29 01:18AM +0200 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.

Back to top

You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.