4
\$\begingroup\$

I am trying to implement a linked list in C++, functional and persistent. Before looking into sample implementations, I tried to come up with my own as an exercise.

I came up with two versions:

  1. One is using pointers as is customary in C++. I am trying to set up an interface that respects structural sharing.
  2. The other one is using full-constexpr. It is basically a compile-time list, if you do not use operator<<.

To begin, the complete code is so long so I am going to start with a link to Compiler Explorer that contains all of the code. Here is the code. There, "C++ Source 1" contains the code for pointer based implementation. "C++ Source 2" contains more functional implementation. You can find respective compiler outputs on the right pane.

First one is the pointer-based version:

#include <iostream>
#include <type_traits>

static size_t total_allocated = 0;

namespace chops {
template <typename T>
class linked_list {
public:
    using ValueType = T;

    template <typename ValueType>
    struct list_node{
        ValueType val;
        list_node *next;

    const ValueType head() const {
        return val;
    }
    const list_node *tail() const {
        return next;
    }

    list_node *Clone(const list_node* other){
        if(other == nullptr)
            return nullptr;


        list_node* result = new list_node;
        total_allocated += sizeof(list_node<ValueType>);
        result->val = other->val;
        result->next = Clone(other->next);
        return result;
    }

    friend std::ostream& operator<<(std::ostream& str,
                             const list_node<ValueType> *ci){
        if(ci == nullptr){
            str << "\n";
            return str;
        }
        str << ci->head() << " " << ci->tail();
        return str;
    }
    };

    using ConstListIterator = const list_node<ValueType>*;
    using ListIterator = list_node<ValueType>*;
    static const size_t node_size = sizeof(list_node<ValueType>);

    linked_list() :_head{nullptr}, a_new_copy{false}{
        _head = nullptr;
    };

    linked_list(const linked_list& other){
        if(_head != nullptr){
            _head->next = nullptr;
            delete _head;
        }
        _head = nullptr;

        _head = _head->Clone(other._head);
        a_new_copy = true;
        std::cout << "copy is happening\n";
    }

    ~linked_list()
    {
        if(_head != nullptr && !a_new_copy){
            std::cout << "Calling the destructor\n";
            _head->next = nullptr;
            delete _head;
        }else
        {
            ListIterator current = _head;
            while(current != nullptr){
                std::cout << "Calling the destructor\n";
                ListIterator next = current->next;
                current->next = nullptr;
                delete current;
                current = next;
            }
        }
    }

    auto prepend(T val) const{
        ListIterator new_node = new list_node<ValueType>;
        total_allocated += sizeof(list_node<ValueType>);
        new_node->val = val;
        new_node->next = _head;
        return linked_list{new_node};
    }

    auto head() const {
        return _head->head();
    }

    ConstListIterator tail() const {
        return _head->tail();
    }

    bool is_empty() const {
    return _head == nullptr;   
    }

    private:
    linked_list(ListIterator begin) : _head(begin), a_new_copy{false}
    {};

    ListIterator _head;
        bool a_new_copy;
    };

    template <typename T>
    std::ostream& operator<<(std::ostream& str, const linked_list<T>& l){
        if(l.is_empty()){
            str << "\n";
            return str;
        }
        str << l.head() << " " << l.tail();
        return str;
    }

}

int main()
{   
    const chops::linked_list<int> ll;
    if(ll.is_empty())
        std::cout << "Empty list!\n";

    const auto ll2 = ll.prepend(6);
    const auto ll3 = ll2.prepend(5);
    const auto ll4 = ll3.prepend(4);
    const auto ll5 = ll4.prepend(3);
    const auto ll6 = ll5.prepend(2);
    const auto ll7 = ll6.prepend(1);

    std::cout << ll7;
    std::cout << ll6.tail();
    const chops::linked_list<int> lcopy{ll6};
    std::cout << lcopy;

    if(std::is_same_v<decltype(ll), decltype(ll7)>)
        std::cout << "Total allocated memory is " << total_allocated << " bytes\n";

    std::cout << "Size of int is: " << sizeof(int) << " \n";
    std::cout << "Size of list_node<int> is: "
              << chops::linked_list<int>::node_size 
              << " \n";

} 

And, here is the constexpr version:

#include <iostream>
#include <type_traits>

namespace chops {
template <typename E1, typename E2>
struct pair {

    constexpr pair() :_car{E1{}}, _cdr{E2{}}, empty{true}
    {}

    constexpr pair(const E1 &car, const E2 &cdr)
    :_car{car}, _cdr{cdr}, empty{false}
    {}

    constexpr auto car() const{
        return _car;
    }

    constexpr auto cdr() const{
        return _cdr;
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    pair<E1, E2> p){
        if(p.empty)
            return str;
        str << p.car() << " " << p.cdr();
        return str;
    }

    const E1 _car;
    const E2 _cdr;
    bool empty;
};

template <typename E1, typename E2>
constexpr bool operator==(const pair<E1, E2>& p1, const pair<E1, E2>& p2)
{
    return (p1.car() == p2.car()) && (p1.cdr() == p2.cdr());
}

template <typename Head, typename Tail>
class list{
    public:

    constexpr list():p{}, empty{true}
    {}

    constexpr list(Head h, Tail t)
    :p{h, t}, empty{false}
    {}

    constexpr auto prepend(Head h) const{ 
        return list<Head, decltype(p)>{h, p};
    }

    constexpr auto head() const {
        return p.car();
    }

    constexpr auto tail() const {
        return list<decltype(p.cdr().car()),
                    decltype(p.cdr().cdr())>
                    {p.cdr().car(),
                     p.cdr().cdr()
                    };
    }

    bool is_empty() const {
        return empty;
    }

    friend std::ostream& operator<<(std::ostream& str,
                                    list<Head, Tail> l){
        str << l.p;
        str << "\n";
        return str;
    }

    private:
    pair<Head, Tail> p;
    bool empty;
};

template <typename T>
using linked_list = list<T, T>;

}

int main()
{
    constexpr chops::linked_list<int> l1;
    constexpr auto l2 = l1.prepend(6);
    constexpr auto l3 = l2.prepend(5);
    constexpr auto l4 = l3.prepend(4); 
    constexpr auto l5 = l4.prepend(3); 
    constexpr auto l6 = l5.prepend(2); 
    constexpr auto l7 = l6.prepend(1); 

    constexpr auto lcopy = l7.tail();
    std::cout << l5;
    std::cout << l4.tail();
    std::cout << lcopy;
}

I think these are working somewhat correctly but I need to ask couple of questions.

  1. Are there any errors that I am missing? How would you improve this code, in general terms?

  2. Why is the pointer-based implementation generating so much longer assembly, assuming this indicates a slower code. They are doing pretty-much the same thing but compile-time version is much faster. Look at the next question for further points.

  3. Is my second implementation truly constexpr? I can see a compile-time version can be faster, since computation happens at compile-time. But in the sample, I am not putting constexpr in my declarations. I can construct those lists in main as constexpr as well. For example, I can do this, adding constexpr:

    constexpr chops::linked_list<int> l1;
    constexpr auto l2 = l1.prepend(6);
    constexpr auto l3 = l2.prepend(5);
    constexpr auto l4 = l3.prepend(4); 
    constexpr auto l5 = l4.prepend(3); 
    constexpr auto l6 = l5.prepend(2); 
    constexpr auto l7 = l6.prepend(1); 
    
    constexpr auto lcopy = l7.tail();
    std::cout << l5;
    std::cout << l4.tail();
    std::cout << lcopy;
    

    and if I comment out the I/O part, this generates nearly no-code at all which is expected right, assuming all the computation happens at compile-time?

  4. My compile-time version is more like lisp const-lists. They are made out of pairs which also lives in chops namespace. So tail of a list is just another nested-pair. This complicates things a-little bit. I had to invent an empty pair. If you think as a mathematical abstraction, an empty pair might not be a good idea. But pointer-based version can just use nullptr to indicate empty list. The other problem with compile-time version is that, I wrapped list into a linked_list through a variable template. But in reality, every list has a different type. After you prepend, you get a new list and it's type is not the same as input list. Types in the compile-time version contains all the structure of the list. For example type of (1 2 3) is list<int, pair<int, int>>. Would this pose a disadvantage in terms of generic usage? Is it better if all had the type List<T>?

  5. What should be the copy-semantics for a purely functional list? Right now, I am treating every copy as if a new world of lists created, separate from the previous list worlds. Is there any mistakes here? My destructor is just deleting the prepended node, unless it is the beginning of a new copy. You can check this out in the code, in the pointer-based version. Compile-time version has no destructor or copy constructor. It is all value-semantics. Which would you prefer?

  6. How would you implement multithreading and fmap-like facility in the compile-time version?

  7. Would move-semantics help the performance of the pointer-based version?

  8. What are the code-smells you can point out?

  9. Is the heavy use of recursion problematic here?

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Unfortunately your question is off-topic as of now, as the code to be reviewed must be present in the question. Please add the code you want reviewed in your question. Thanks! \$\endgroup\$ – Vogel612 Apr 9 '18 at 9:56
  • 1
    \$\begingroup\$ I'm a bit embarrassed because you ask a review of two very different pieces of code. They aren't two different implementations of the same concept. I believe you should ask about one or the other, but not both. About the second kind of list, there is no difference between a pair and a list, so it isn't really useful to write two different classes. Lists in functional or functional-friendly languages are algebraic types (in this instance either nil or a cons) we don't really have in C++, hence the weird empty pair. \$\endgroup\$ – papagaga Apr 9 '18 at 13:57
  • 1
    \$\begingroup\$ Is this supposed to be a comparative-review (as in "which of these should I use?")? If not, it might be better as two questions. \$\endgroup\$ – Toby Speight Apr 9 '18 at 15:25
  • \$\begingroup\$ @papagaga I probably did something wrong there, I thought about it. But, performance questions and C++ type system related questions made me believe that it is better if i gave a sample implementation of both. \$\endgroup\$ – meguli Apr 9 '18 at 17:18

Your Answer

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

Browse other questions tagged or ask your own question.