simple forward_list

Question

//  NODE implementation
template <typename T>
class forward_list_node{
public:
    using value_type = T;
    using pointer_type = T*;
    using reference_type = T&;

    forward_list_node(value_type value = 0) :  data(value), next(nullptr) {
    }

    forward_list_node<value_type> * get_next() const{
        return this->next;
    }

    void set_next(forward_list_node<value_type> * node){
        this->next = node;
    }

    value_type get_data() const{
        return this->data;
    }

    void set_data(value_type value){
        this->data = value;
    }

private:
    value_type data;
    forward_list_node<value_type> * next;
};


//  FORWARD_list implementation
template <typename T>
class forward_list{
public:
    using value_type = T;
    using pointer_type = T*;
    using reference_type = T&;

    using node = forward_list_node<value_type>;
    using node_pointer = node *;

    // ctor
    forward_list() : head(nullptr), tail(nullptr){
    }

    //  dtor
    ~forward_list(){
        node_pointer ptr = this->head, tmptr;

        while(ptr != nullptr){
            tmptr = ptr;
            std::cout << "GC: " << ptr->get_data() << " deleting..." << std::endl;
            ptr = ptr->get_next();
            delete tmptr;
        }

    }

    forward_list& push_back(value_type value){
        node_pointer item = new node(value);

        if(this->tail) this->tail->set_next(item);
        this->tail = item;
        if(!this->head) this->head = this->tail;

        return *this;
    }

    value_type pop_front(){
        node_pointer item;
        value_type data = 0;

        if(this->tail && this->head){
            data = this->head->get_data();
            item = this->head;
            this->head = this->head->get_next();
        }

        return data;
    }


private:
    node_pointer head, tail;
};

Here is the code i wrote to test my skills. This code is simple singly linked list program. it uses push_back() function to push an item at the end and pop_front() function to get the first item in the list just like a queue.

Now i need some feedbacks to make my program more efficient. What would you advise me?

Answer 1

Leaking memory

You have a memory leak. In pop_front, you only move the head, but you don't delete the previous head.

value_type pop_front(){
    node_pointer item;
    value_type data = 0;

    if(this->tail && this->head){
        data = this->head->get_data();
        item = this->head;
        this->head = this->head->get_next(); // old head unreachable!
    }

    return data;
}

Here's a mnemonic: if one of your functions is a dual to another, and one of these uses new, the other one should likely use delete. push_back is the dual of pop_front. The first uses new, but the latter is missing delete.

Is the queue empty?

Let's use a forward_list:

forward_list<int> list_of_zeros;

list_of_zeros.push_back(0);
list_of_zeros.push_back(0);
list_of_zeros.push_back(0);

How do I know whether I've read all the contents of the queue? It's not distinguishable:

for(int zero; (zero = list_of_zeros.pop_front()) == 0; ){
    // handle zero
}

That's not going to end well. Your minimal interface should include a size method. You can add empty(), but that's not necessary.

Also, you have to think about the empty queue a little bit more. Returning 0 isn't possible if I have a queue of std::string. Indeed, pop_front won't even compile if I use a fordward<std::string>.

From my point of view, pop_front on the empty list should throw an exception or return nothing. That's how it is specified in std::forward_list. There pop_front removes the front (if it exists), and you access the actual front with front().

After those two comments, we end up with the following pop_front:

value_type pop_front(){
    if(this->head == nullptr) {
        return value_type();                  // see remark below
        //or: throw <your_exception_type>;
    }
    data = this->head->get_data();

    node_pointer old_head = this->head;

    if(this->head == this->tail) {
        this->head = nullptr;
        this->tail = nullptr;
    } else {
        this->head = this->head->get_next();
    }

    delete old_head;

    return data;
}

Instead of return 0, we use return value_type() to construct a default value of the given type. Now your pop_front works with other types than integral or floating point ones.

Hide implementation details

Your forward_list_node is an implementation detail of forward_list. It shouldn't be exposed to the user. Also, it can be simplified:

template <typename T>
class forward_list{
    struct forward_list_node {
        T data;
        forward_list_node * next;
    };

    using node = forward_list_node;
    using node_pointer = node *;

public:
    using value_type = T;
    using pointer_type = T*;
    using reference_type = T&;

Now the user doesn't know that there is any kind of node. After all, your public interface of forward_list never exposed those nodes in the first way.

Your constructor is fine:

// ctor
forward_list() : head(nullptr), tail(nullptr){
}

You destructor is fine too, although you don't need the ptr. Also, you don't want to print text in a destructor usually, except for debugging. Note that I'm using the new forward_list_node described above here:

//  dtor
~forward_list(){
    while(this->head != nullptr){
        node_pointer old_head = this->head;
        this->head = this->head->next;
        delete old_head;
    }
}

The size of the list

Your push_back is also fine. However, I would not return a forward_list&. That depends on your use case, though. A void function should be fine, too.

Also, I would add an additional detail:

// using your old interface for simplicity:
forward_list& push_back(value_type value){
    node_pointer item = new node(value);

    if(this->tail) this->tail->set_next(item);
    this->tail = item;
    if(!this->head) this->head = this->tail;

    number_of_nodes++; // this detail

    return *this;
}

The new number_of_nodes provides an easy way to see whether the list is empty:

size_t size() const {
    return number_of_nodes;
}

This would fix the problem shown above in the list_of_zeros example. You have to decrease the variable of course if you use pop_front, and you need to add it to your member variables. But both of them are left as an exercise.

Naming

Your naming was fine, however, if you prefix or postfix your member variables, you can drop this->. That way, you can also simply call get_data() data() for example. But that's personal preference.

The only real naming-nitpick I had was ptr instead of old_head in the destructor. We know that it's a pointer due to its type, it's much more interesting what it points to.

Other

You should add a copy constructor, copy assignment operator, move constructor and move assignment operator or forbid those operations explicitly with = delete.

Answer 2

Rule of five:

Since container has ownership of elements, it is responsible for preventing corruption of the data inside. It has to take care of those resources when copied/moved. Since explicit destructor is declared, default generation of copy and move operations is disabled. It would be great to have rule of five implemented, especially for the containers.

The container is not so generic

This is the biggest easy of use issue. It places enormous restriction on the T.

value_type data = 0;

This line tells the compiler that T should be assignable (copy or move) or in C++17 copy constructible from zero. There are way too many types that are not copy constructible or assignable from/to zero.

Too many useless copy constructor calls:

This is the biggest potential performance issue.

A few examples with some explanations:

    value_type data = 0;

    if(this->tail && this->head){
        data = this->head->get_data();
        item = this->head;
        this->head = this->head->get_next();
    }

    //excerpt from node
    value_type get_data() const{
        return this->data;
    }

So, first copy construction happens on the line mentioned in the previous paragraph. The second time is when get_data() is invoked. It copy constructs the internal data, then copy assignment happens again when data is assigned to it. This culminates the non-generic nature of the code. Then, the last copy construction happens when data is returned. 4 copy construction/assignment calls just to get the data off of the queue. Isn't it way too much?

forward_list& push_back(value_type value){
    node_pointer item = new node(value);

    if(this->tail) this->tail->set_next(item);
    this->tail = item;
    if(!this->head) this->head = this->tail;

    return *this;
}

//excerpt from node
void set_data(value_type value){
    this->data = value;
}

Roughly the same as above, just in another direction.

Actually compiler can elide some (or all unnecessary ones) copy constructor calls, but it doesn't mean that one shouldn't care about it.

Generic code:

Some people try to write special case first, then make it generic. Although this works for simple cases, it is not going to work when number of template parameters/parameter packs start increasing. The problem is that it creates that many-to-many dependency, which makes "sticking different parts together" very hard/error prone at the end. For cases like this it should work though.

I found thinking in terms of concepts (or constraints) a great way to accomplish most of the metaprogramming tasks. Knowing C++ concepts should facilitate in that.

Exception specification:

Due to copy constructive nature of the container it probably can't guarantee anything, so it might be great to fix that.