Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was practicing my C++ routine and decided to code up this simple linked list data structure. Furthermore, I made an attempt to make the list iterator "safe" in the sense that it throws an exception instead of tampering a memory region it should not..

safelist.h

#ifndef SAFE_LIST_H
#define SAFE_LIST_H

#include <stdexcept>

namespace net {
namespace coderodde {
namespace util {

template<typename T>
class Safe_list {
public:

    Safe_list()
    :
    head{nullptr},
    tail{nullptr}
    {}

    // Disable all the constructors + assignments:
    Safe_list(const Safe_list&)            = delete;
    Safe_list(Safe_list&&)                 = delete;
    Safe_list& operator=(const Safe_list&) = delete;
    Safe_list& operator=(Safe_list&&)      = delete;

    void push_back(const T& datum)
    {
        Safe_list_node* new_node = new Safe_list_node(datum);

        if (tail == nullptr)
        {
            head = new_node;
        }
        else
        {
            tail->next = new_node;
        }

        tail = new_node;
    }

    void pop_front()
    {
        check_list_not_empty();
        Safe_list_node* removed = head;
        head = head->next;

        if (head == nullptr)
        {
            tail = nullptr;
        }

        delete removed;
    }

    const T& front() const
    {
        check_list_not_empty();
        return head->datum;
    }

    T& front()
    {
        check_list_not_empty();
        return head->datum;
    }

private:

    struct Safe_list_node {
        T datum;
        Safe_list_node* next;

        Safe_list_node(const T& datum)
        :
        datum{datum},
        next{nullptr}
        {}
    };

    Safe_list_node* head;
    Safe_list_node* tail;

    void check_list_not_empty()
    {
        if (head == nullptr)
        {
            throw std::runtime_error{"Operating on an empty list."};
        }
    }

public:

    class Safe_list_iterator {
        Safe_list_node* current_node;

    public:        
        Safe_list_iterator(Safe_list_node* node)
        :
        current_node{node}
        {}

        const T& operator*() { return current_node->datum; }
        T& operator*() const { return current_node->datum; }

        bool operator!=(const Safe_list_iterator& lhs)
        {
            return this->current_node != lhs.current_node;
        }

        Safe_list_iterator& operator++()
        {
            if (current_node == nullptr)
            {
                throw std::runtime_error{"No elements left for iteration."};
            }

            current_node = current_node->next;
            return *this;
        }
    };

    using iterator = Safe_list_iterator;

    iterator begin()
    {
        return Safe_list_iterator{head};
    }

    iterator end()
    {
        return Safe_list_iterator{nullptr};
    }
};

} // End of net::coderodde::util
} // End of net::coderodde
} // End of net

#endif // SAFE_LIST_H

main.cpp

#include "safelist.h"
#include <iostream>
#include <stdexcept>

using net::coderodde::util::Safe_list;
using std::cerr;
using std::cout;
using std::endl;
using std::runtime_error;

int main(int argc, const char * argv[]) {
    Safe_list<float> list;

    for (int i = 0; i < 10; ++i)
    {
        list.push_back((float) i);
    }

    cout << "Iterating the queue in for each loop:" << endl;

    for (const auto x : list)
    {
        cout << x << " ";
    }

    cout << endl;
    cout << "Iterating the queue via old style iterators:" << endl;

    for (Safe_list<float>::iterator it = list.begin(); it != list.end(); ++it)
    {
        cout << *it << " ";
    }

    cout << endl;
    cout << "Popping the queue:" << endl;

    for (int i = 0; i < 10; ++i)
    {
        cout << list.front() << " ";
        list.pop_front();
    }

    cout << endl;

    cout << "Safety demo:" << endl;
    Safe_list<float> list2;

    for (int i = 10; i < 20; ++i)
    {
        list2.push_back((float) i);
    }

    try
    {
        for (Safe_list<float>::iterator begin = list.begin(),
             end = list2.begin();
             begin != end;
             ++begin)
        {

        }
    }
    catch (std::runtime_error& error)
    {
        cerr << "Exception caught! Message: " << error.what() << endl;
    }
}

Please tell me anything that might make my code more idiomatic.

share|improve this question
    
leaks galore.. You may want to fix those – ratchet freak 2 days ago
    
Am I allowed to edit my question? – coderodde 2 days ago
    
@ratchetfreak Fixed. Hopefully no-one minds editing my question + Thank you for pointing that out. – coderodde 2 days ago
2  
Little fixes are fine, However edits after you get an answer are not allowed. – ratchet freak 2 days ago
    
@ratchetfreak Got it! – coderodde 2 days ago
up vote 1 down vote accepted

I would take std::unique_ptr<> with great care. There is a reason why I wouldn't want to use it when it recursively may own another std::unique_tr<>: stackoverflow. Destructor of each ptr will keep calling another, without exiting. I guess we have to accept it: manual memory management is something we can't avoid in general case.

Missing pieces of interface:

No in place construction:

template <typename ... ArgTypes>
void emplace_back(ArgTypes&& ... args)

and one for emplace with iterator hint

Swap, easiest one.

Construction from std::initializer_list. May be slightly headache, due to exception safety.

Don't pay for what you don't use:

I know that people are free to use std::list, but in general I would refrain from writing code that incurs needless overhead. The user knows the size of the list, the current node, etc. So, he/she has complete control over it. If they want to shoot themselves in the foot, let them do it! This is C++, footshooter!

Allocator:

Although std::allocator and the interface is a complete fail, you should try to incorporate it into the list on the next iteration / another implementation. What I would do is define my own allocator interface (and write the some allocators, of course). Some people may find it great, some not, but I'm sure it will be better than Allocator concept.

Optimizations:

I know that the list wasn't supposed to be optimized, but I want to present a list of very interesting optimizations (some have drastical impact, some have almost zero):

  1. Small List optimization

This is the first optimization I would do. Have a union (yes, bare union), with some predefined number of objects sitting on the stack. You could also remove the links in that version, since you know where is the next node (if insertions are only at the end). This will greatly reduce fragmentation. When the size exceeds that capacity, repurpose the union into head, size and whatever needed.

  1. Peculiar fact about malloc

std::malloc() (the same as C malloc) gives 16 byte aligned memory on 64 bit machines (not sure if the same applies on 32 bit). The alignment says that lower 4 bits of the pointer will be always 0. Exploit it! You can store some information there, such as flags, or size lower than 16.

  1. Sentinel

Make a sentinel to be just an empty data structure. Then the operator==() will just check if the current is nullptr. This will increase cache consistency (you won't be creating new iterator + there won't be access far from the node you're currently in).

Those are from top of my head. There might be more.

Idiomatic C++:

I know it's great. I know it's safe. I know everybody loves it. Despite that, at some point you'll find out that current meta (idiomatic C++) is not that good yet. There are some optimizations (some of them listed above), that doesn't hurt much readability and safety. People are stuck on the idea don't pay for what you don't use when you can make users pay nothing for what they are using.

share|improve this answer
    
I have a feeling that Bjarne would call the 2. optimization evil. – coderodde 2 days ago
1  
@coderodde, the optimizations are not meant to be good :) the thing is that the list is a library, and you will never know how fast is fast enough (compared to end user applications). So, the only thing left is to make it even faster. – Olzhas 2 days ago
    
"std::malloc() (the same as C malloc) gives 16 byte aligned memory on 64 bit machines" - not an actual guarantee, and new doesn't make the same promises as malloc anyway. – user2357112 2 days ago
    
@user2357112, I've just checked out that VC++ returns 16 byte aligned memory on 64 bit platform. I remember Chandler Carruth mentioned this optimization, and he is a head of Clang development team, which means that Clang malloc returns 16 byte aligned memory too, probably g++ as well. About operator new not calling malloc, it does in the major compilers, though you're right, not in all of them. – Olzhas 2 days ago

I mentioned that your code was leaking but it still is. There is no destructor to clean up the nodes.

To cleanly get proper cleanup you can use unique_ptr:

void pop_front()
{
    check_list_not_empty();
    Safe_list_node* next = head->next.release();
    head.reset(next);

    if (!head)
    {
        tail = nullptr;
    }
}

void push_back(const T& datum)
{
    std::unique_ptr<Safe_list_node> new_node = std::make_unique<Safe_list_node>(datum);
    tail = new_node.get();

    if (!tail)
    {
        head = std::move(new_node);
    }
    else
    {
        tail->next = std::move(new_node);
    }

}

struct Safe_list_node {
    T datum;
    std::unique_ptr<Safe_list_node> next;

    Safe_list_node(const T& datum)
    :
    datum{datum},
    next{}
    {}
};

std::unique_ptr<Safe_list_node> head;
Safe_list_node* tail;

Consider allowing (only) the move constructor and assignment. As is (with the unique_ptr) you can just remove the disabling declarations and it'll work, though I suggest implementing them yourself to null out the tail pointer in the moved-from object.

share|improve this answer
    
So the point behind unique_ptr is that when we destruct the list, first the head will be deleted, which will trigger the node after the head, and so on until we reach nullptr? – coderodde 2 days ago
1  
@coderodde exactly. If you want to do it without unique_ptr then you would need to loop over the list and delete each node yourself. – ratchet freak 2 days ago
    
@coderodde, I recommend running the program under a memory-checking tool (e.g. Valgrind in "memcheck" mode) to help identify bugs like this. – Toby Speight 2 days ago
2  
std::unique_ptr<> will cause stackoverflow on big lists. The destructor will keep recurring, which will make overflow. You could try to change implementation at runtime, but I wouldn't care to do it. – Olzhas 2 days ago
    
@TobySpeight Thanks for letting me know about Valgrind, yet I can write non-leaking programs without any aid. It's just I was too concentrated on the iterator "safety" and came with the leaking list since I needed something to iterate. – coderodde 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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