Peer review: Template singly linked list using unique_ptr

[Sekkkyyy]

Sorry for the long code post:


Class

  template<typename B>
class linkedlist{


public:
//linked list struct
struct node{
	B x;
	unique_ptr<node> next;
	~node(){     //destructor for clarification
		cout<<"a node has been freed"<<endl;
	}
};	

//linked list nodes
unique_ptr<node> head;
node * tail;
node * current;

//constructor
linkedlist(){
	head = nullptr;
	current = nullptr;
}

//functions
void addNode(B x);
void deleteNode(B x);
void traverseNode();	
};

Functions add/delete/traverse

template<typename B>
void linkedlist<B>::addNode(B x){


node * n = new node;   						//initialize new node
n->x = x;
n->next = nullptr;


if(head == nullptr){							//if the list is empty

	head = (unique_ptr<node>)n;				//cast the normal pointer to a unique pointer

}else{        								//if there is an existing link
	current = head.get();					//get the address that is being pointed by the unique_ptr head
	
											
	while(current->next != nullptr)				//loop until the end then stop
		current = (current->next).get();
	
	
	current->next = (unique_ptr<node>) n;		//connect the new node to the last node

}

}





template<typename B>
void linkedlist<B>::deleteNode(B x){
	

current = head.get();							//set current to the head


if(current->x == x){     							//head is being deleted


//tricky
head = move(head->next);    						 //transfer the ownership of the next pointer to the head, thus freeing the first node.

//not head
} else{
	
	while(current->x != x && current->next != nullptr){	//    traverse and set traverse limits
	
	tail = current;				              				//set tail sa current
	current= (current->next).get();  					//move the current
	}	
	
	if(current->next == nullptr && current->x != x){	//check if you reached the end of the node and there is no x
		cout<<"value isnt here!"<<endl;	
	} else{										//once it founds it. 
		//delete operation
		if(current->next != nullptr)					//if there node after
		tail->next = move(current->next);
		else										// if there is no node after.
		(tail->next).reset();
		current = nullptr;
	}
	
	
}



	
	
}





template<typename B>				
void linkedlist<B>::traverseNode(){
	
current = head.get();									//set current to head

	if(head != nullptr){									//if the list exist
	cout<<"val: "<<head->x<<endl;
		while(current->next != nullptr){					//traverse
		current = (current->next).get();
		cout<<"val: "<<current->x<<endl;
		}		

	}else{											//if there are no elements in the list
		cout<<"there is no element in the list"<<endl;
	}
}

Main

int main() {


	//initalize
	linkedlist<int> l;
	
	//add values
	l.addNode(1);
	l.addNode(2);
	l.addNode(3);
	l.addNode(4);
	l.addNode(5);
	
	//add and delete
	l.traverseNode();
	cout<<"deleting first value: ";
	l.deleteNode(1);
	cout<<"deleting third value: ";
	l.deleteNode(3);
	cout<<"adding new value: 6"<<endl;
	l.addNode(6);
	cout<<"traversing updated values.........."<<endl;
	l.traverseNode();
	
	
	system("pause");
	return 0;
}

Output

val: 1
val: 2
val: 3
val: 4
val: 5
deleting the first value: a node has been freed
deleting the third value: a node has been freed
adding new value: 6
traversing updated values....................
val: 2
val: 4
val: 5
val: 6

Please check my implementation, any constructive inputs will be appreciated.

[coder777]

Please ask a specific question. Does something not work as expected?

cast the normal pointer to a unique pointer

No, never.

[Sekkkyyy]

Things work as intended but i am not sure if i did the process correctly.

Is there something that i shouldnt have done? like bad allocations or bad practices.

[andywestken]

If you want a code review then please sort out your formatting (by editing you opening post, not reposting!)

Modern IDEs don't need the old 80 col max rule to be strictly applied (the default width of the console in the "old days"), but that doesn't mean really long lines of code are a good idea.

If you can't be bothered to be tidy...

Andy

[coder777]

Sekkkyyy wrote:

Is there something that i shouldnt have done? like bad allocations or bad practices.

Well: Never cast away an error.

What you do is a major abuse of unique_ptr. As the name imply the intention is that you have only one pointer at any time to a certain object. So don't use unique_ptr if that isn't what you want.

[JLBorges]

> As the name imply the intention is that you have only one pointer at any time to a certain object.
> So don't use unique_ptr if that isn't what you want.

The intent is that there is only one owning-pointer to an object. There can be other non-owning-pointers or references to the object owned by a unique pointer.


A few suggestions:

addNode() can be made O(1) if the value of the member node* tail; is maintained.

addNode() can support move seamantics.
(Either overloads for lvalue and rvalue references or a universal reference with perfect forwarding.)

If it is C++14, std::make_unique<>() makes for more pleasing code.
http://en.cppreference.com/w/cpp/memory/unique_ptr/make_unique

#include <iostream>
#include <memory>

template< typename T > struct fwd_list
{
    struct node
    {
        node( const T& v, std::unique_ptr<node>&& n = nullptr ) : value(v), next( std::move(n) )
        { ++constructor_cnt ; }

        ~node() { ++destructor_cnt ; }

        ////////////////////////
        node( node&& ) = delete ;
        ///////////////////////

        T value ;
        std::unique_ptr<node> next ;

        static int constructor_cnt ;
        static int destructor_cnt ;
    };

    std::unique_ptr<node> head ;
    node* tail = nullptr ;

    template < typename U > void add( U&& v )
    {
        if( tail != nullptr )
        {
            tail->next = std::make_unique<node>( std::forward<U>(v) ) ;
            tail = tail->next.get() ;
        }
        else
        {
            head = std::make_unique<node>( std::forward<U>(v) ) ;
            tail = head.get() ;
        }
    }

    void erase( const T& v )
    {
        if( head == nullptr ) return ;

        node* prev = head.get() ;
        node* curr = prev ;

        while( curr != nullptr )
        {
            if( curr->value == v ) break ;
            prev = curr ;
            curr = curr->next.get() ;
        }

        if( curr == tail ) { tail = prev ; tail->next = nullptr ; }
        if( curr == head.get() ) head = std::move( head->next ) ;
        else if(prev) prev->next = prev->next ? std::move( prev->next->next ) : nullptr ;
    }

    std::ostream& print( std::ostream& stm = std::cout ) const
    {
        stm << "[ " ;
        for( node* n = head.get() ; n != nullptr ; n = n->next.get() )
            stm << n->value << ' ' ;
        return stm << "]  (constructor/destructor counts: " << node::constructor_cnt
                   << '/' << node::destructor_cnt << ")\n\n" ;

    }
};

template< typename T > int fwd_list<T>::node::constructor_cnt = 0 ;
template< typename T > int fwd_list<T>::node::destructor_cnt = 0 ;

int main()
{
   {
        //initalize
        fwd_list<int> lst;

        //add values
        for( int v = 1 ; v < 6 ; ++v ) lst.add(v);
        lst.print();

        //add and delete
        std::cout<<"deleting first value: ";
        lst.erase(1);
        lst.print();

        std::cout<<"deleting third value: ";
        lst.erase(3);
        lst.print();

        std::cout<<"adding new value: 6 "; //<<endl;
        lst.add(6);
        lst.print();

        std::cout<<"deleting last value: ";
        lst.erase(6);
        lst.print();
   }

   std::cout << "final constructor/destructor counts: "
             << fwd_list<int>::node::constructor_cnt
             << '/' << fwd_list<int>::node::destructor_cnt << '\n' ;
}

http://coliru.stacked-crooked.com/a/16c83c468644f269