About Smart Pointers

[geeloso]

Hey guys!

I am reading a terse Programming book in which the solution to a linked-list problem is coded as shown below. The struct prototype used is:

template <typename T>
struct ListNode 
{
    T data;
    shared_ptr<ListNode<T>> next;
};

Problem: Write a function that takes singly linked lists, L and F, and returns the merge of L and F. Your code should reuse the nodes from the lists provided as input. Your function should use O(1) additional storage. The only field you can change in a node is next.

shared_ptr<ListNode<int>> MergeTwoSortedLists(shared_ptr<ListNode<int>> F, shared_ptr<ListNode<int>> L)
{
    //Creates a placeholder for the result
    shared_ptr<ListNode<int>> dummy_head(new ListNode<int>);
    auto tail = dummy_head; 

    while (F && L)
        AppendNode(F->data < L->data ? &F: &L, &tail);

    if (F)
        //Appends the remaining nodes of F
        tail->next = F;
    else if (L)
        //Appends the remaining nodes of L
        tail->next = L;

    return dummy_head->next;
}



void AppendNode(shared_ptr<ListNode<int>>* node, shared_ptr<ListNode<int>>* tail)
{
    (*tail)->next = *node;
    *tail = *node;   //Updates tail
    *node = (*node)->next;
}

I do need some clarifications/explanations about the following please:

1. In line 8, why are &F and &L being passed to function AppendNode when, as formal parameters of function MergeTwoSortedLists, F and L were already pointers?

2. In line 17, why is dummy_head->next being returned and NOT just dummy_head?

3. In line 22, why are the asterisks again qualifying the type of the formal parameters node and tail when, in my view, shared_ptr<ListNode<int>> already qualified them as pointers?

4. As a result of the confusion expressed in 3. above, lines 24 and 26 are downright confounding! If node and tail were pointers, why are they dereferenced and then simultaneously used with the member access operator arrow (->) symbol?? I would think -> is strictly used with pointers!

5. As a follow-up to 4. above, would function AppendNode still have worked correctly if all the asterisks were removed?

[Peter87]

shared_ptr<ListNode<int>>* is a pointer to a shared_ptr<ListNode<int>>. Not sure why they pass pointers instead of references.

If you change AppendNode to ...

void AppendNode(shared_ptr<ListNode<int>>& node, shared_ptr<ListNode<int>>& tail)
{
    tail->next = node;
    tail = node;
    node = node->next;
}

... and remove the dereference address-of operators from line 8 ...

AppendNode(F->data < L->data ? F : L, tail);

... it should should work the same.

[geeloso]

Thx Peter87 for your response. However, my confusion persists!

--> I want to disagree with what you wrote:

shared_ptr<ListNode<int>>* is a pointer to a shared_ptr<ListNode<int>>

I sure know that in the realm of raw pointers,
X* is a pointer to X; type X being int, double, char, any user-defined class, etc. This syntax would only hold if we are talking about raw pointers!

But, in the sphere of smart pointers,
shared_ptr<X> p is equivalent to X* p; X being the type and p being the declared pointer.


--> So, is the book wrong??


--> What about question 2. in my OP?


--> You also wrote:

... and remove the dereference operators from line 8 ...

But there are no dereference operators in line 8! Probably, you meant the 'address of' operators.

[xismn]

geeloso,

I might be misinterpreting what you've written, but here goes...

Assume the following:
shared_ptr<ListNode<int>>* ptr;

'ptr' is a "raw" pointer that points to a smart pointer (shared_ptr) which points to a ListNode of type int.

Answering your questions:

1.) 'AppendNode' expects a shared_ptr<ListNode<int>>* (a raw pointer to a shared ptr to a ListNode of int). Yes, technically 'F' and 'L' are (smart) pointers, but that's not what 'AppendNode' wants. Think of it this way:

using Type = shared_ptr<ListNode<int>>;

void IWantAPointer(Type* p) {
	//do something
}

void doIt(Type object) {
	IWantAPointer(&object);
}

2.) That's where your result is stored. You could return dummy_head, but then later on you'd have to get the result from 'next'.

3.) Not sure why they're using pointers here. They could have passed by reference.

4.) You can think of 'node' and 'tail' as pointers to pointers. You'll have to dereference them because shared_ptr doesn't have a member named 'next'

5.) You would have to modify 'AppendNode' so that it expects smart pointer references. You would also invoke it differently.

[geeloso]

Thx xismn for your response. I agree with your answer to question 2; that almost seems obvious on hindsight!

However, you wrote:

'AppendNode' expects a shared_ptr<ListNode<int>>* (a raw pointer to a shared ptr to a ListNode of int)... .

But why do we need another raw pointer to point to a shared_ptr when there already exists an internal raw pointer in the shared_ptr that could point to ListNode<int>?! That's why I'm questioning this same reasoning in the Programming book where I saw this. The whole thing just reeks of a circuitous (complicated) way of accessing data when a more straightforward construct could have been used. I'm yet to be convinced about the programming soundness or benefit of this.

I think questions 3 and 4 are also borne out of this pattern of confusion.

[Peter87]

The thing is that AppendNode is supposed to modify the share_ptr objects that you pass to it. If they were passed in by value (not using pointers or references) the function would receive copies of them and any changes made to the copies would not affect the shared_ptrs that was passed in from MergeTwoSortedLists.

[xismn]

*EDIT* I concede that I've totally made a mistake.

Actually, upon closer inspection, it's as you say geeloso, the smart pointer pointers / references are not needed.

This is so because we aren't modifying the smart pointers themselves, but rather the objects they point to. Take a look at this example:

#include <iostream>
#include <string>
#include <memory>

using StringPtr = std::shared_ptr<std::string>;

void change_content(StringPtr _strptr) {

	//Change pointed-to string from "Hello World" to "Hello Darling".
	_strptr->assign(_strptr->substr(0, 6));
	_strptr->append("Darling");

}

int main() {

	StringPtr strptr = StringPtr(new std::string("Hello World"));

	::change_content(strptr);

	std::cout << *strptr << std::endl;

	std::cin.ignore();
	return 0;
}

Notice how we pass the shared_ptr to 'change_content' by value, not by reference or via a pointer. This works because when it is copied by value, the address it is internally pointing to is unaffected, whether it's passed by value, reference or pointer - therefore any changes made to the object being pointed to will take effect. However, any changes made to the shared_ptr itself will not be reflected unless you pass by reference or via a pointer. Another example:

#include <iostream>
#include <string>
#include <memory>

using StringPtr = std::shared_ptr<std::string>;

void print_count(StringPtr _strptr) {

	std::cout << "Inside 'print_count':\t" << _strptr.use_count() << std::endl;

}

int main() {

	StringPtr strptr = StringPtr(new std::string("Hello World"));

	::print_count(strptr);

	std::cout << "Inside 'main':\t" << strptr.use_count() << std::endl;

	std::cin.ignore();
	return 0;
}

'use_count' is a member function of 'shared_ptr'. It returns the number of pointers that share ownership of the object being pointed to (including itself). '_strptr' inside of the 'print_count' function is a copy of 'strptr' in our main function - when we print 'use_count' inside of 'print_count', it will yield a value of two, since there are two independent shared pointers pointing to the same thing (strptr and _strptr). Notice that if we modify 'print_count' to expect a reference or pointer to a shared_ptr, it will yield a value of one.

In short, if you're interested in working with the shared pointer itself, you must pass by reference or via a pointer. If you're interested in working with the content of a shared pointer, you may pass by value.

[Peter87]

xismn wrote:

Actually, upon closer inspection, it's as you say geeloso, the smart pointer pointers / references are not needed. This is so because we aren't modifying the smart pointers themselves, but rather the objects they point to.

This is not true. AppendNode updates the tail pointer so that it points to the newly inserted node. The node pointer is also updated so that it points to the next node in the list.

auto oldF = F;
AppendNode(&F, &tail);
// tail now points to *F
// and F points to oldF->next.
// If they were passed by value this
// wouldn't have been possible. 

[geeloso]

Thx xismin and Peter87 for your responses since my last post!

I am somewhat torn between the two seemingly divergent views you guys defended. While it is common knowledge that variables/objects are to be passed by reference/pointers to a function if any modification is expected in the calling function's scope (as Peter87 argued), I can't dismiss, either, xismin's powerful and reasonable argument for passing by value as illustrated above.
In the meantime, what makes logical sense to me is to modify function AppendNode and its call in MergeTwoSortedLists so that the former's formal parameters are passed by reference, as suggested in Peter87's first reply to my OP. Probably I should just consider it a pedantic case of overkill on the part of the authors of the Programming book to have used pointers in function AppendNode the way they did!


@ xismin: I really appreciate the extra effort you put into your illustrative examples; your ingenious use of use_count is very instructive!

You wrote:

... However, any changes made to the shared_ptr itself will not be reflected unless you pass by reference or via a pointer ...
In short, if you're interested in working with the shared pointer itself, you must pass by reference or via a pointer.

Using the same examples you gave, can you please illustrate how "changes made to the shared_ptr" or "working with the shared pointer itself," contrasts with the changes to "Hello World"?

[geeloso]

You used this statement in your two illustrative examples (in lines 17 and 15):

StringPtr strptr = StringPtr(new std::string("Hello World"));

Are you using 'StringPtr' as a casting operator in the right-hand-side expression?

[xismn]

geeloso,

I've made a mistake. You need to definitely pass the shared pointer via reference or pointer. The reason is because you are modifying the shared pointer itself, as opposed to the thing the shared pointer is pointing to. For some reason I thought 'AppendNode' wasn't modifying the shared_ptr, but it is, since you're changing the thing it is pointing to. Sorry for causing confusion.

[geeloso]

No problem, xismn! Thanks for your replies still.