0

Part of my homework assignment is to implement a generic linked list. So far I wrote this function:

template<class T>
void List<T>::insert(const T& data)
{
    List<T>::Node* newNode = new List<T>::Node(data);
    newNode->next = nullptr;

    if (head == nullptr)
    {
        head = newNode;
        tail = newNode;
    }
    else
    {
        tail->next = newNode;
        tail = newNode;
    }
    size++;
}

As you can see I'm getting the data by reference but I could get it by value as well. My question is what approach is better and why?

triple fault
  • 13,410
  • 8
  • 32
  • 45
  • What does the List::Node constructor do with data? Store a copy? Who manages the lifetime of the objects in the list? – zdan Sep 19 '13 at 00:10

3 Answers3

4

In C++98/03, what you have is generally the correct solution. In C++11, you can keep it the same, and you will be no worse off. But if you want to improve efficiency, you can make some modifications. There are two schools of thought. The most efficient solution requires a little code duplication. You need two functions.

template<class T>
void List<T>::insert(const T& data)                    // take a const reference
{
    List<T>::Node* newNode = new List<T>::Node(data);  // copy it in
...

template<class T>
void List<T>::insert(T&& data)                         // take an r-value reference
{
    List<T>::Node* newNode
        = new List<T>::Node(std::move(data));          // move it in
...

The other method is only slightly less efficient in most cases, and it avoids code duplication:

template<class T>
void List<T>::insert(T data)                           // take a value (copy)
{
    List<T>::Node* newNode
        = new List<T>::Node(std::move(data));          // move it in
...
Benjamin Lindley
  • 101,917
  • 9
  • 204
  • 274
  • I'm not sure that I understand the "move it in" part, what problem it comes to solve? When I'm adding data to a linked list, I'm adding a copy, right? Why I need to move things? – triple fault Sep 19 '13 at 00:15
  • @BenjaminLindley, you are right, one can use move semantics. I recommended const reference because I'm a C++98 dinosaur, still using classical C++ syntax. It's been 2 years since the new standard, so I've got to auto-mate my thinking. – Michael Sep 19 '13 at 00:22
  • @Doppelganger: If the original object that you supply for adding is *discardable*, i.e. you no longer need it after the addition, then you can make your code much more efficient by *relocating* (*moving* ) data from the original object to the entry in the list instead of *duplicating* (*copying*) it. That's the point of move semantics in this case. – AnT stands with Russia Sep 19 '13 at 01:09
  • @AndreyT You sorted the last piece of puzzle for me, thank you. – triple fault Sep 19 '13 at 12:53
2

Avoid unnecessary copy of data if passing by value, pass it by const reference as you did.

Michael
  • 5,775
  • 2
  • 34
  • 53
  • So why C++ doesn't pass by reference by default? – triple fault Sep 19 '13 at 00:05
  • First, for backward compatibility with C. Second, because for basic types such as integers and floats it's more efficient to pass the value. Java doesn't claim compatibility with C and tends to pass objects by reference, but even Java passes basic types by value. C++ tends to give more control to the programmer, therefore it doesn't quietly replace value semantics with const reference semantics unless the programmer asks for it. – Michael Sep 19 '13 at 00:17
  • I agree with Michael, that it should be avoided, but be careful not to always lean on passing by reference as noted in my answer. – jmstoker Sep 19 '13 at 00:30
-1

By reference is better. The data is not copied over. Which can be significant we are talking about class, structures, unions, etc.

By using "const" avoids the stupid programming error of storing values to parameters. i.e.

void dumb_print_function(Type& d){
    d=3;  // bad programming practice.
    }
x=LongCalc();

dumb_print_function(x); // output 3 not results of "LongCalc();".
Brian Erickson
  • 1