High performance parallel programming and optimization | lesson 02 homework at home

Catalog

One   Job requirements

Two   Job initial run results

3、 ... and   Copied answer

Four   Improved operational results

---

 

One   Job requirements

# High performance parallel programming and optimization - The first 0x My homework

adopt pull request Submit the assignment . Meeting batch score , however ：

No certificate of completion , Homework is only used as a means to evaluate the effect of learning and consolidate knowledge , Don't be nervous about grades :)
Our strengths , As long as you can in this class , Learn what you didn't know yesterday , Is victory , There is no need to compare with others .
Be careful not to peek at other people's homework ！

- Courseware ：https://github.com/parallel101/course
- Record and broadcast ：https://space.bilibili.com/263032155

There is no time limit for submitting homework :) Even if I want to hand it in after it's finished, I'll see it ~ But it's best to finish before the next lecture starts .

- How to drive pull request：https://zhuanlan.zhihu.com/p/51199833
- How to set up https agent ：https://www.jianshu.com/p/b481d2a42274

## Scoring rules

- Basic requirements for completing the operation 50 branch （ Please see below " Job requirements "）
- In the PR Explain in your own words 25 branch
- Code format specification 、 Ability to cross platform 5 branch
- Has its own unique innovation 20 branch
- Obvious plagiarism -100 branch
- change to the use of sth. `unique_ptr<Node>` 10 branch

## Job requirements

modify main.cpp, Improve the double linked list class `List`：

- Avoid unnecessary copying of function parameters 5 branch
- Fix problems caused by smart pointers 10 branch

- Implement the copy constructor as a deep copy 15 branch
- Explain why copy assignment functions can be deleted 5 branch
- improvement `Node` Constructor for 5 branch

And pass `main()` Basic tests in functions .

## About the inner volume

If you put List Changed to iterator based , Or as a template `List<int>`：
As long as it's in the ** The basis for meeting the operation requirements ** On , That's a good thing ！
The teacher will add points as appropriate , As “ Unique innovation ”, But not more than 20 branch .
 

/*  Based on intelligent pointer to achieve two-way linked list  */
#include <cstdio>
#include <memory>

struct Node {
    //  What problems do these two pointers cause ？ Please repair 
    std::shared_ptr<Node> next;
    std::shared_ptr<Node> prev;
    //  If you can change it to  unique_ptr  That's better. !

    int value;

    //  What can be improved about this constructor ？
    Node(int val) {
        value = val;
    }

    void insert(int val) {
        auto node = std::make_shared<Node>(val);
        node->next = next;
        node->prev = prev;
        if (prev)
            prev->next = node;
        if (next)
            next->prev = node;
    }

    void erase() {
        if (prev)
            prev->next = next;
        if (next)
            next->prev = prev;
    }

    ~Node() {
        printf("~Node()\n");   //  How many times should I output ？ Why not ？
    }
};

struct List {
    std::shared_ptr<Node> head;

    List() = default;

    List(List const &other) {
        printf("List  Be copied ！\n");
        head = other.head;  //  This is a shallow copy ！
        //  Please implement the copy constructor as  ** Deep copy **
    }

    List &operator=(List const &) = delete;  //  Why is there no error in deleting the copy assignment function ？

    List(List &&) = default;
    List &operator=(List &&) = default;

    Node *front() const {
        return head.get();
    }

    int pop_front() {
        int ret = head->value;
        head = head->next;
        return ret;
    }

    void push_front(int value) {
        auto node = std::make_shared<Node>(value);
        node->next = head;
        if (head)
            head->prev = node;
        head = node;
    }

    Node *at(size_t index) const {
        auto curr = front();
        for (size_t i = 0; i < index; i++) {
            curr = curr->next.get();
        }
        return curr;
    }
};

void print(List lst) {  //  What is worth improving ？
    printf("[");
    for (auto curr = lst.front(); curr; curr = curr->next.get()) {
        printf(" %d", curr->value);
    }
    printf(" ]\n");
}

int main() {
    List a;

    a.push_front(7);
    a.push_front(5);
    a.push_front(8);
    a.push_front(2);
    a.push_front(9);
    a.push_front(4);
    a.push_front(1);

    print(a);   // [ 1 4 9 2 8 5 7 ]

    a.at(2)->erase();

    print(a);   // [ 1 4 2 8 5 7 ]

    List b = a;

    a.at(3)->erase();

    print(a);   // [ 1 4 2 5 7 ]
    print(b);   // [ 1 4 2 8 5 7 ]

    b = {};
    a = {};

    return 0;
}

Two   Job initial run results

3、 ... and   Copied answer

It's changed for a long time , It didn't work , It's really annoying , Dragged 2 Months , Let's copy the answer .

/*  Based on intelligent pointer to achieve two-way linked list  
 Reference code ：https://github.com/parallel101/hw02/pull/53/files
*/
#include <cstdio>
#include <exception>
#include <memory>
#include <stdexcept>
#include <utility>
#include <type_traits>
#include <iterator>
#include <cstddef>

template <typename T>
struct Node {
    //  What problems do these two pointers cause ？ Please repair 
    //     std::shared_ptr<Node> next;
    //     std::shared_ptr<Node> prev;
    //  For a two-way linked list , There is a circular reference between adjacent items , Reference count cannot be zeroed to free space .
    //  For a two-way linked list , It can be regarded as the previous item “ Have ” The latter .
    //  The latter one retains the former one Node* The pointer 
    std::unique_ptr<Node> next;
    Node* prev;
    //  If you can change it to  unique_ptr  That's better. !
    //int value;

      What can be improved about this constructor ？
    //Node(int val) {
    //    value = val;
    //}

    //void insert(int val) {
    //    auto node = std::make_shared<Node>(val);
    //    node->next = next;
    //    node->prev = prev;
    //    if (prev)
    //        prev->next = node;
    //    if (next)
    //        next->prev = node;
    //}

    T value;

    //  What can be improved about this constructor ？:value Direct basis val Construct instead of default post construct assignment .
    Node(const T& val) : value(val), prev(nullptr) {}
    Node(const Node&) = default;
    Node& operator=(Node&&) = default;

    // insert Will make it unusable unique_ptr, Because it will break the above assumptions “ The former has the latter ” The premise of 
    /*
              +--- O ---+
        O ---x           x--- nextO
              +--- O ---+
         It will become like this ,  This operation is not used in the two-way linked list, so it is directly noted .
    */
    // void insert(int val) {
    //     auto node = std::make_unique<Node>(val);
    //     node->next = next;
    //     node->prev = prev;
    //     if (prev)
    //         prev->next = node;
    //     if (next)
    //         next->prev = node;
    // }


    void erase() {
        //if (prev)
        //    prev->next = next;
        if (next)
            next->prev = prev;
        if (prev)
            prev->next = std::move(next);
    }


    ~Node() {
        printf("~Node()\n");   //  How many times should I output ？ Why not ？ Because of the circular quotation 
    }
};

template<typename T>
struct List {
    //std::shared_ptr<Node> head;
    class iterator {
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = Node<T>;
        using pointer = value_type*;  // or also value_type*
        using reference = value_type&;  // or also value_type&

        iterator(pointer ptr) : m_ptr(ptr) {}
        reference operator*() { return *m_ptr; }
        pointer operator->() { return m_ptr; }

        // Prefix increment
        iterator& operator++()
        {
            m_ptr = m_ptr->next.get(); return *this;
        }

        // Postfix increment
        iterator operator++(int)
        {
            iterator tmp = *this; ++(*this); return tmp;
        }

        friend bool operator== (const iterator& a, const iterator& b)
        {
            return a.m_ptr == b.m_ptr;
        };
        friend bool operator!= (const iterator& a, const iterator& b)
        {
            return a.m_ptr != b.m_ptr;
        };

    private:
        Node<T>* m_ptr;
    };

    std::unique_ptr<Node<T>> head;
    Node<T>* back = nullptr;

    List() = default;
    List(List const& other_) {
        List& other = const_cast<List&>(other_);// The copy constructor has a specific function signature , It is not recommended to change easily .
        printf("List  Be copied ！\n");
        //head = other.head;  //  This is a shallow copy ！
        //  Please implement the copy constructor as  ** Deep copy **
        for (auto it = other.begin(); it != other.end(); it++) {
            push_back(it->value);
        }
    }

    List &operator=(List const &) = delete;  //  Why is there no error in deleting the copy assignment function ？
    //  Copy assignment here  =  Copy to construct the right value + Move assignment 

    List(List &&) = default;
    List &operator=(List &&) = default;

    //Node *front() const {
    Node<T>* front() const {
        return head.get();
    }

    //int pop_front() {
    //    int ret = head->value;
    //   head = head->next;
    T pop_front() {
        if (begin() == end()) {
            throw std::out_of_range("pop_front()");
        }
        T ret = head->value;
        if (head.get() == back)
            back = nullptr;
        head = std::move(head->next);
        return ret;
    }

    //void push_front(int value) {
    //    auto node = std::make_shared<Node>(value);
    //    node->next = head;
    void push_front(const T& value) {
        auto node = std::make_unique<Node<T>>(value);
        if (head)
     //       head->prev = node;
    //    head = node;
        head->prev = node.get();
        else
        back = node.get();
        node->next = std::move(head);
        head = std::move(node);
    }

   // Node *at(size_t index) const {
    void push_back(const T& value) {
        auto node = std::make_unique<Node<T>>(value);
        if (back) {
            node->prev = back;
            back->next = std::move(node);
            back = back->next.get();
        }
        else {
            head = std::move(node);
            back = head.get();
        }
    }

    Node<T>* at(size_t index) const {
        auto curr = front();
        for (size_t i = 0; i < index; i++) {
            curr = curr->next.get();
        }
        return curr;
    }

    iterator begin() { return iterator(head.get()); }
    iterator end() { return iterator(nullptr); }
};

void print(List<int> & lst) {  //  What is worth improving ？:  Pass in const quote , Avoid copying 
    printf("[");
  //  for (auto curr = lst.front(); curr; curr = curr->next.get()) {
  //      printf(" %d", curr->value);
    for (auto &v : lst) {
        printf(" %d", v.value);
    }
    printf(" ]\n");
}

int main() {
    //List a;
    List<int> a;

    a.push_front(7);
    a.push_front(5);
    a.push_front(8);
    a.push_front(2);
    a.push_front(9);
    a.push_front(4);
    a.push_front(1);

    print(a);   // [ 1 4 9 2 8 5 7 ]

    a.at(2)->erase();

    print(a);   // [ 1 4 2 8 5 7 ]

    //List b = a;
    List<int> b = a;

    a.at(3)->erase();

    print(a);   // [ 1 4 2 5 7 ]

    b.push_back(1);
    b.push_back(2);
    b.push_back(3);
    print(b);   // [ 1 2 3 ]
    print(b);   // [ 1 4 2 8 5 7 ]

    b = {};
    a = {};

    return 0;
}

Four   Improved operational results