6
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ leaks galore.. You may want to fix those \$\endgroup\$ Commented Nov 9, 2016 at 16:35
  • \$\begingroup\$ Am I allowed to edit my question? \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 16:36
  • \$\begingroup\$ @ratchetfreak Fixed. Hopefully no-one minds editing my question + Thank you for pointing that out. \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 16:38
  • 2
    \$\begingroup\$ Little fixes are fine, However edits after you get an answer are not allowed. \$\endgroup\$ Commented Nov 9, 2016 at 17:11
  • \$\begingroup\$ @ratchetfreak Got it! \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 17:12

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I have a feeling that Bjarne would call the 2. optimization evil. \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 18:19
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Nov 9, 2016 at 18:20
  • \$\begingroup\$ "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. \$\endgroup\$ Commented Nov 9, 2016 at 21:02
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Nov 10, 2016 at 7:08
5
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 17:14
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Nov 9, 2016 at 17:17
  • \$\begingroup\$ @coderodde, I recommend running the program under a memory-checking tool (e.g. Valgrind in "memcheck" mode) to help identify bugs like this. \$\endgroup\$ Commented Nov 9, 2016 at 17:55
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Nov 9, 2016 at 17:57
  • \$\begingroup\$ @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. \$\endgroup\$
    – coderodde
    Commented Nov 9, 2016 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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