高性能并行编程与优化 | 第02讲回家作业

一 作业要求

# 高性能并行编程与优化 - 第0x讲的回家作业

通过 pull request 提交作业。会批分数，但是：

没有结业证书，回家作业仅仅作为评估学习效果和巩固知识的手段，不必为分数感到紧张 :)
量力而行，只要能在本课中，学到昨天的自己不懂的知识，就是胜利，没必要和别人攀比。
注意不要偷看别人的作业哦！

- 课件：https://github.com/parallel101/course
- 录播：https://space.bilibili.com/263032155

作业提交时间不限 :) 即使完结了还想交的话我也会看的~ 不过最好在下一讲开播前完成。

- 如何开 pull request：https://zhuanlan.zhihu.com/p/51199833
- 如何设置 https 代理：https://www.jianshu.com/p/b481d2a42274

## 评分规则

- 完成作业基本要求 50 分（详见下方"作业要求"）
- 能够在 PR 描述中用自己的话解释 25 分
- 代码格式规范、能够跨平台 5 分
- 有自己独特的创新点 20 分
- 明显抄袭现象 -100 分
- 改用 `unique_ptr` 10 分

## 作业要求

修改 main.cpp，改良其中的双链表类 `List`：

- 避免函数参数不必要的拷贝 5 分
- 修复智能指针造成的问题 10 分

- 实现拷贝构造函数为深拷贝 15 分
- 说明为什么可以删除拷贝赋值函数 5 分
- 改进 `Node` 的构造函数 5 分

并通过 `main()` 函数中的基本测试。

## 关于内卷

如果你把 List 改成了基于迭代器的，或是作为模板 `List`：
只要是在 **满足作业要求的基础** 上，这是件好事！
老师会酌情加分，视为“独特的创新点”，但最多不超过 20 分。

/* 基于智能指针实现双向链表 */
#include <cstdio>
#include <memory>

struct Node {
   
    // 这两个指针会造成什么问题？请修复
    std::shared_ptr<Node> next;
    std::shared_ptr<Node> prev;
    // 如果能改成 unique_ptr 就更好了!

    int value;

    // 这个构造函数有什么可以改进的？
    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");   // 应输出多少次？为什么少了？
    }
};

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

    List() = default;

    List(List const &other) {
   
        printf("List 被拷贝！\n");
        head = other.head;  // 这是浅拷贝！
        // 请实现拷贝构造函数为 **深拷贝**
    }

    List &operator=(List const &) = delete;  // 为什么删除拷贝赋值函数也不出错？

    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) {
     // 有什么值得改进的？
    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;
}

二 作业初始运行结果

三 抄的答案

改了很久，没成功，实在很烦，拖了2个月，还是抄答案吧。

/* 基于智能指针实现双向链表 
参考代码：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 {
   
    // 这两个指针会造成什么问题？请修复
    //     std::shared_ptr<Node> next;
    //     std::shared_ptr<Node> prev;
    // 对于双向链表，相邻项之间存在循环引用，引用计数无法归零释放空间。
    // 对于双向链表，可以看作前一项“拥有”后一项。
    // 而后一项保留前一项的Node*指针
    std::unique_ptr<Node> next;
    Node* prev;
    // 如果能改成 unique_ptr 就更好了!
    //int value;

     这个构造函数有什么可以改进的？
    //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;

    // 这个构造函数有什么可以改进的？:value直接根据val构造而不是默认构造后赋值。
    Node(const T& val) : value(val), prev(nullptr) {
   }
    Node(const Node&) = default;
    Node& operator=(Node&&) = default;

    // insert会导致无法使用unique_ptr，因为会破环上面假设的“前一项拥有后一项”的前提
    /*
              +--- O ---+
        O ---x           x--- nextO
              +--- O ---+
        会变成上面这样, 双向链表中用不到该操作所以直接注掉了。
    */
    // 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");   // 应输出多少次？为什么少了？因为循环引用
    }
};

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_);//拷贝构造函数有特定的函数签名，不建议轻易改变。
        printf("List 被拷贝！\n");
        //head = other.head;  // 这是浅拷贝！
        // 请实现拷贝构造函数为 **深拷贝**
        for (auto it = other.begin(); it != other.end(); it++) {
   
            push_back(it->value);
        }
    }

    List &operator=(List const &) = delete;  // 为什么删除拷贝赋值函数也不出错？
    // 此处拷贝赋值 = 拷贝构造出右值+移动赋值

    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) {
     // 有什么值得改进的？: 传入const引用，避免拷贝
    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;
}

四 改进的运行结果