2
\$\begingroup\$

I wrote list, which I think is more elaborate than usual. I would like to ask you for some tips, criticisms, and general feedback about my code.

#ifndef _LIST_HPP
#define _LIST_HPP
#include<memory>
#include<iostream>
#include<cassert>

template<typename T>
class List{
    private:
        struct Node{
            std::shared_ptr<Node> next;
            T value;

            Node():next(nullptr){};
            Node(T item,std::shared_ptr<Node> node):value(item),next(node){};
            Node(T item):value(item),next(nullptr){};
        };

        std::shared_ptr<Node> head;   //head is also header node as the first node of the list 
        std::shared_ptr<Node> tail;   // but it have no element, is not considered to be an element
        std::shared_ptr<Node> curr;   // of the list
        size_t size;

        void deepCopy(const List<T>& l){
            if(this!=&l){
                size=l.size;
                curr=tail=head=l.head;
                auto l_curr=l.curr;
                auto this_curr=curr;
                l_curr=l_curr->next; //head have any element in so we must go to next
                while(l_curr->next){
                    this_curr=this_curr->next;
                    this_curr->value=l_curr->value;
                    l_curr=l_curr->next;
                    if(l_curr->next)this_curr->next=std::make_shared<Node>();
                }
                    this_curr->value=l_curr->value;//assign last element 
            }
        }

        void clear(){
            moveToStart();
            while(curr->next){
                remove();
            }
        }

    public:
        List():size(0),head(std::make_shared<Node>()),curr(tail),tail(head){};
        List(const List<T>& l){deepCopy(l);}
        List(List<T>&&);
        ~List(){clear();};
        List<T>& operator=(const List<T>& l);
        List<T>& operator=(List<T>&&);

        void insert(T);
        void append(T);
        T remove();
        void moveToStart(){curr=head;}
        void moveToEnd(){curr=tail;}
        void goNext();
        int lenght(){return size;}
        void prev(){ if(curr->next)curr=curr->next;}
        T getValue()const;
        int getPosition();
        void moveToPos(int pos);
        template <typename U>friend std::ostream& operator<<(std::ostream&,const List<U>&); 
};


template<typename T>
List<T>::List(List<T>&& l){
    deepCopy(l);
    l.clear();
}

template<typename T>
List<T>& List<T>::operator=(const List<T>& l){
    deepCopy(l);
    return *this;
}

template<typename T>
List<T>& List<T>::operator=(List<T>&& l){
    deepCopy(l);
    l.clear();
    return *this;
}

template<typename T>
void List<T>::insert(T item){
    curr->next=std::make_shared<Node>(item,curr->next);
    if(tail==curr) tail=curr->next;
    ++size;
}

template<typename T>
void List<T>::append(T item){
    tail->next=std::make_shared<Node>(item);
    tail=tail->next;
    ++size;
}

template<typename T>
T List<T>::remove(){
    assert(curr->next!=nullptr);
    T it=curr->next->value;
    if(tail=curr->next) tail=curr;
    curr->next=curr->next->next;
    --size;
    return it;
}

template<typename T>
int List<T>::getPosition(){
    auto temp=head.get();
    int i=0;
    for(i;temp!=curr.get();++i)
        temp=temp->next.get();
    return i;
}

template<typename T>
void List<T>::moveToPos(int pos){
    if(pos>=size) return;
    auto temp=head.get();
    int i=0;
    while(i<pos-1){
        temp=temp->next.get();
        ++i;
    }
    curr=temp->next;
}

template<typename T>
T List<T>::getValue()const{
    assert(curr->next!=nullptr);
    return curr->next->value;
}

template<typename U>
std::ostream& operator<<(std::ostream& os,const List<U>& l){
    auto temp=l.head.get();
    temp=temp->next.get();
    while(temp){
        os<<temp->value<<std::endl;
        temp=temp->next.get();
    }
    return os;
}
#endif

//and some test 


#include<ostream>
#include"list.hpp"

typedef int T;

bool  checkRemove(List<T>&);
bool checkGoNextAndPrev(List<T>&);
bool checkPos(List<T>&);
void insert(List<T>&);
void append(List<T>&);
bool checkCopy(List<T>&);

int main(){
    List<T> l;
    insert(l);
   // append(l);
    std::cout<<std::boolalpha;
    std::cout<<"remove "<<checkRemove(l)<<std::endl;
    std::cout<<"pos "<<checkPos(l)<<std::endl;
    std::cout<<"checkGoNextAndPrev "<<checkGoNextAndPrev(l)<<std::endl;
    std::cout<<l;
    l.moveToStart();
    std::cout<<"copy "<<checkCopy(l);

}

bool  checkRemove(List<T>& l ){
    int len=l.lenght();
    l.remove();
    return len-1==l.lenght();
}

bool checkGoNextAndPrev(List<T>& l){
    l.prev();
    l.prev();
    return 2==l.getPosition();
}

bool checkPos(List<T>& l){
    l.moveToPos(2);
    bool boo=(2==l.getPosition());
    l.moveToStart();
    return boo;
}
void insert(List<T>& l){
    for(int i=1;i<25;++i){
        l.insert(i);
    }
}

void append(List<T>& l){
    for(int i=1;i<25;++i){
        l.append(i);
    }
}

bool checkCopy(List<T>& l){
    List<T> l2(l);
    bool copyConstr=(l2.lenght()==l.lenght());
    List<T> l3;
    l3=l;
    std::cout<<l3;
    bool copyOperator=(l3.lenght()==l.lenght());
    List<T> l4;
    l4=std::move(l);
    bool moveOperator=(l4.lenght()!=l.lenght());
    return moveOperator&&copyOperator&&copyConstr;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I am so sorry. I will never do it again. \$\endgroup\$ – Klemens Aug 17 '16 at 13:10
6
\$\begingroup\$

Move assignment and constructor too expensive

Whenever I see Type(Type &&);, I expect that operation to be cheaper than Type(const Type&). However, in your case, it's far too expensive. You're creating a copy of something that's going to be "moved from" either way. In your move constructor, you should simply take ownership of the shared_ptrs:

template<typename T>
List<T>::List(List<T>&& l){
    head.swap(l.head);
    tail.swap(l.tail);
    curr.swap(l.curr);
}

template<typename T>
List<T>& List<T>::operator=(List<T>&& l){
    head.swap(l.head);
    tail.swap(l.tail);
    curr.swap(l.curr);
    return *this;
}

Let them clear themselves

Why no clear call in the operator/constructor above? Because clear should be also trivial:

void clear(){
    curr = tail = head = std::make_shared<Node>();
}

After all, your list is a forward-list. Every node only points to the next one, and at the moment all three head, tail and curr go out of scope, the items will be deleted (unless you accidentally added a loop somewhere).

No overhead for empty objects

You have an "empty" node at the end of your list. This is troublesome due to two limitations:

  1. all your List<T>s need to allocate, even if they never get used
  2. one cannot use List<T> with types that don't support default construction

Don't call things by wrong names

deepCopy does not create a deep copy. Instead, it does overwrite a list with its own (later) values and has two List<T> manage the same contents. That's due to your head = l.head line.

You could use insert here instead. If you provided an iterator interface, you could simply use

clear();    

for(const auto & value : otherList){
   this->append(value);
}

but that's left as an exercise.

Don't use typedef int T

Single-letter type variables are used in template declarations, but never with typedef. This looks like a bunch of declared template functions:

bool checkRemove(List<T>&);
bool checkGoNextAndPrev(List<T>&);
bool checkPos(List<T>&);
void insert(List<T>&);
void append(List<T>&);
bool checkCopy(List<T>&);

but it isn't. Use typedef int my_test_type or something else with a better name.

Documentation, documentation, documentation

Your class has no documentation, except for head, curr and tail, and I wouldn't count those three lines as actual documentation. I'm not talking about implementers documentation, e.g.

template<typename T>
List<T>::List(List<T>&& other){
    // Due to the nature of shared_ptr, we can swap
    // our current head, tail and curr with the 
    // @c other values. Swapping is noexcept. The @c other
    // list will be empty.
    head.swap(other.head);
    tail.swap(other.tail);
    curr.swap(other.curr);
}

but users:

// Advances the internal position to the next item. 
// If there is no item, it will stay on the last item.
//
// @seealso getPosition(), setPosition()
void List<T>::goNext();

By the way, you never implemented goNext().

Summary

Don't make the move operations more expensive than the non-move ones, use features that you already have at hand (shared_ptr::~shared_ptr), don't lie to yourself (deepCopy), don't limit your class with arbitrary constraints (unless there's a reason), add documentation, and test more thoroughly.

It's good that you have tests, but they didn't catch the bug in deepCopy.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.