top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Creating a 'Y'-list from two std::list or std::forward_list objects

+2 votes
493 views

"Imagine you have a singly-linked list L1 (of integers, for simplicity) with values 0 to 9. There is another singly-linked list L2 (again, of integers) with values 0 to 5.

As expected, the next-pointers of the last nodes of both the lists point to NULL. Now, I modify the next-pointer of the last node of L2 to point to the 7th node of L1 (which has the integer 6 in it). We now have a 'Y' : two lists which merge into one. How would you find the node where the two lists merge?"

The problem is not difficult. However, my colleague came up with the question "How would one _create_ such a 'Y' from two std::list or two std::forward_list objects in C++?". The constraint is that one _must_ use the STL list/forward_list and other STL functions only. He can't figure it out and neither can I :-(

I agree that creating such a 'Y' would be inviting trouble but still, how would one do it if one wanted to? I tried to google for "combining/merging/joining multiple lists" but the usual answers (splice, std::move, etc) don't seem to help.

posted Apr 25, 2014 by Riteshwar

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

TL;DR : Store pointers to the data objects in the list nodes rather than the data object values.

C++ standard library container types store data by value - that is they copy (or move or directly construct in C++11) objects that they store and the container then owns the (copied/moved/constructed) object.

Hence you cannot have the same object in two std::lists. You either have to make a copy from one list to the other or, since C++11 you have to move an object from one list to the other, invalidating the original (note: not all types are or should be movable).

Many other linked list implementations do not make copies of the object passed to the list for inclusion - they just store the object's pointer. You can probably see that with this type of list implementation you can easily create the 'Y' you were after.

Hence the way to replicate this using a std::list is to use a list of pointers to data objects: std::list<T*> rather than list. However doing this using raw pointers leads to all sorts of problems. Firstly, std::list<> objects delete each node's object when the list is destroyed. However deleting a raw pointer does _not_ delete the object it points to so the list items need to be deleted manually before destroying the list. Secondly in this case as some nodes' data objects are going to be shared between lists - how do you know when to delete list items? Maybe a node is still used on one or more other lists.

Both problems can be taken care of by using a suitable smart pointer. In this case std::shared_pointer (for C++11 implementations) would be such a smart pointer type or std::tr1::shared_pointer for mid-naughties implementations or look at boost::shared_pointer if neither of the others two are available. In fact you should use the associated make_shared function to create objects referred to by a shared_pointer. You might wish to look up further information on smart pointers, such as:

http://herbsutter.com/2013/05/29/gotw-89-solution-smart-pointers/

A shared_pointer will keep a count of references to the pointer it manages, or rather the object it manages via its pointer. When the reference count goes to zero the object is deleted.

This solves both the problems mentioned above with std::list<T*>. A std::list<std::shared_pointer> (or equivalent earlier/alternative of std::shared_pointer) will not require us to manually delete the object in the list and each shared pointer knows how many lists - and possibly other things - are referring to the pointed to object and will delete that object only when there is nothing left to refer to it.

Hope this helps.

UPDATED TO ADD:

It occurred to me a while after I posted my answer (and sorry some life stuff distracted me from getting this update out sooner!) that I did not make it clear that although using (smart) pointers will allow you to create a sort of Y-shaped effect you cannot do exactly as I think the question you were querying about implied as std::list (and in C++11 and later std::forward_list - a singly linked list type) will not let you mess around with their node data (i.e. the link pointers)* in the way the question was asking about. You will still have two distinct lists with distinct nodes, with nodes at the end of each list that just happen to have node-data that refers (points to) the same data. You can still manipulate the two lists separately so that the Y shape no longer exists or is changed.


  • OK you could work out the node structure of a specific std::list implementation and do all sorts of under handed things to mess with a list's nodes - C++ only helps protect you from mistakes not malice!
answer Apr 28, 2014 by Karan Joglekar
Similar Questions
+2 votes

I'm curious as to why libstdc++ is using a RB-tree to implement std::set (details here
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/set and here https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/stl_tree.h ),
when there are faster alternatives?

I'm mainly curious, because from all the people I've asked there hasn't been a single answer in favor of RB-trees, other than "they're already popular" or "easy to implement".

If you'd like more details on that, here's a link to my question on stackexchange http://cs.stackexchange.com/questions/41969/why-are-red-black-trees-so-popular,
where nobody has yet answered as well.

Using a variant of B-tree (or (a,b)-tree) should be faster, and everyone seems to suggest so, which makes me wonder what is the reason for picking RB-trees? This is not a question about their theoretical speed, but about real world behavior on real hardware with respect to CPU caches, etc.

...