Постоянный список с помощью constexpr и указатели


Я пытаюсь реализовать связанный список в C++, функциональным и стойким. Прежде чем искать в образце реализации, я пытался придумать что-то свое в качестве упражнения.

Я придумал два варианта:

  1. Один заключается в использовании указателей, как это принято в C++. Я пытаюсь создать интерфейс, который уважает структурного обмена.
  2. Другой использует полныйconstexpr. Это в основном компиляции списка, если вы не пользуетесь operator<<.

Для начала, полный код слишком длинный, поэтому я начну со ссылкой на Compiler Explorer который содержит весь код. Вот код. Там, "C++ код 1" содержит код для указателя реализации. "C++ код 2" содержит более функциональной реализации. Вы можете найти соответствующие выходы компилятор на правой панели.

Первый указатель-версия:

#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";

} 

И, вот constexpr версия:

#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;
}

Я думаю, что это немного неправильно работает, но мне нужно задать пару вопросов.

  1. Есть ли ошибки, что мне не хватает? Как бы вы улучшили этот код, в общих чертах?

  2. Почему указатель на основе генерации реализации намного дольше, сборки, предполагая, что это указывает на более медленный код. Они делают довольно много-то же самое, но во время компиляции версии намного быстрее. Следующий вопрос для последующих пунктов.

  3. Это моя вторая реализация-настоящему пользователем? Я вижу времени компиляции версия может быть быстрее, так как вычисление происходит во время компиляции. Но в образце, я не отдам constexpr в моей декларации. Я могу построить эти списки в основном как constexpr как хорошо. Например, я могу сделать это, добавив 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;
    

    и если я закомментируйте ввода/вывода, это создает почти никаких-кода, который, как ожидается, хорошо, если все вычисление происходит во время компиляции?

  4. Мои компиляции версия больше нравится lisp константный-листы. Они сделаны из pairS, которая также живет в chops пространства имен. Так что хвост списка-это просто еще один вложенный пары. Это усложняет вещи немного. Мне пришлось изобрести пустой pair. Если вы думаете, как математическая абстракция, пустая пара может не быть хорошей идеей. Но указатель-разрядных версий можно просто использовать nullptr чтобы указать пустой список. Другая проблема с компиляции версии, я завернул list в linked_list через переменную шаблона. Но в действительности, каждый list имеет различный вид. После prependвы получаете новый list и это типа не то же самое как входной list. Типов во время компиляции версия содержит все структуры списка. Например типа (1 2 3)это list<int, pair<int, int>>. Это создает невыгодное положение с точки зрения универсального использования? Это лучше, если все типа List<T>?

  5. Какой должна быть копия-семантики для чисто функциональный список? Прямо сейчас, я вижу каждую копию так, как если бы вновь созданный мир из списков, отдельные из предыдущего списка миров. Есть ли здесь ошибки? Мой деструктор просто удалить узел добавляется, если это начало новой копии. Вы можете проверить это в коде, в указатель-разрядной версии. Во время компиляции версия не имеет деструктор и конструктор копирования. Это все значение-семантику. Что бы вы предпочли?

  6. Как реализовать многопоточность и fmap-как объект в компиляции версии?

  7. Будет двигаться-семантика повысить производительность указатель-версия?

  8. Какие код-запахи вы можете отметить?

  9. Это интенсивное использование рекурсии проблематично здесь?



192
4
задан 9 апреля 2018 в 09:04 Источник Поделиться
Комментарии