6
\$\begingroup\$
//  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?

\$\endgroup\$
7
  • \$\begingroup\$ Could you provide a summary of what your code does \$\endgroup\$
    – Tolani
    Feb 13, 2017 at 11:17
  • \$\begingroup\$ It is a basic linked list which uses ´push_back()´ and ´pop_front()´to store data and get them respectively. \$\endgroup\$ Feb 13, 2017 at 11:20
  • \$\begingroup\$ Could you add your description to your post \$\endgroup\$
    – Tolani
    Feb 13, 2017 at 11:44
  • \$\begingroup\$ oh sorry its fifo so it is queue. And what do you suggest to have it worked with other types? \$\endgroup\$ Feb 13, 2017 at 12:12
  • \$\begingroup\$ @RıfatTolgaKiran, use constructor with no arguments. It will work on numbers too. \$\endgroup\$ Feb 13, 2017 at 12:13

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ If something here is ambiguous, probably I've messed something up, since I haven't written a line of C++ code for a quite a while now and probably lost some snappishness (thanks Java). Feel free to ask anything. \$\endgroup\$ Feb 13, 2017 at 16:15
  • \$\begingroup\$ You should push up the rule of five to make it more promenant. \$\endgroup\$ Feb 13, 2017 at 22:24
  • \$\begingroup\$ @Incomputable can you lead me how to prevent extra copy ctor and assignment operators? is there another way? or shall i return the address of values? \$\endgroup\$ Feb 16, 2017 at 5:45
  • \$\begingroup\$ @RıfatTolgaKiran, there are generally two ways to avoid copy/move constructor/assignment. Pass by reference or pass by pointer. In case of push, just keep passing const T& until the constructor of the node, and make the constructor take const T& as well. So it will make only one copy. About pops it is not possible to make only one copy. Passing a pointer/reference is not a good idea either. Standard library just provide a peek() method, which returns const T& to the top of the stack, then pop just doesn't return anything. There is a reason for that, I'll leave it as an exercise. \$\endgroup\$ Feb 16, 2017 at 7:05
  • \$\begingroup\$ @RıfatTolgaKiran, the best way to get interactive help would be to setup a public github repo and embed it into the question (just put something like "Curent version can be found at link", without any EDIT words in caps or anything else). I can drop by from time to time to write comments about the code if you're interested in my opinion \$\endgroup\$ Feb 16, 2017 at 7:12

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.