Skip to content

AUT AP1400

Basic Information

来源：Amirkabir University of Technology

课程名称：AP1400, Advanced Programming (2022 Spring)

主题：C++ 语言 (C++ 20)

主要内容：6 个 Homework

课程网站：https://github.com/courseworks

个人实现：22Sp-AP1400-AUT

起止时间：2024.01 - 2024.02

Content

Homework 1

实现一个 Matrix 类，包含基本的矩阵运算。其中比较有难度的内容是高斯消元法。

Homework 2

模拟加密货币客户端与服务器端的交互。在完成过程中，主要遇到了以下问题：

Problem 1

Q: 在 server.h 和 client.h 分别实现了 Server 和 Client 类，如何处理这种相互引用时的声明问题？

A: 先声明 class 对象，但不给出具体实现即可。

1
2
3
4
5
// client.h
class Server;
class Client {
    // implementation ...
}

Problem 2

Q: 如果不使用友元, 如何访问一个类的 private 对象？

A: 借助指针。

其他方法见：C++奇技淫巧之访问private成员

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class A {
public:
    void add(int key, int value) {
        mp.insert(std::make_pair(key, value));
    }
    void print() {
        for (auto [u, v]: mp) {
            std::cout << u << " " << v << "\n";
        }
    }
private:
    std::map<int, int> mp;
};

int main() {
    A a;
    a.add(1, 4);
    a.add(2, 8);
    a.add(5, 7);
    std::cout << "Visit inside the class\n";
    a.print();
    std::cout << "Hack the private object\n";
    using type = std::map<int, int>;
    for (const auto&[u, v]: *(type *)&a) {
        std::cout << u << " " << v << "\n";
    }
    return 0;
}

Homework 3

实现一个 Binary Search Tree Interface 。

主要要考虑的是如何实现一个基本的 ADT ，包括构造函数、析构函数、重载运算符、移动语义等内容。当然也包括基本的 BST 操作（插入、查询、删除）。具体如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class BST
{
public:
    class Node
    {
    public:
        Node(int value, Node* left, Node* right);
        Node();
        Node(const Node& node);

        int value;
        Node* left;
        Node* right;

        friend std::ostream& operator<<(std::ostream& os, const Node& obj);
        friend bool operator==(const Node& lhs, int rhs);
        friend bool operator==(int lhs, const Node& rhs);
        friend bool operator!=(const Node& lhs, int rhs);
        friend bool operator!=(int lhs, const Node& rhs);
        friend bool operator>(const Node& lhs, int rhs);
        friend bool operator>(int lhs, const Node& rhs);
        friend bool operator<(const Node& lhs, int rhs);
        friend bool operator<(int lhs, const Node& rhs);
        friend bool operator>=(const Node& lhs, int rhs);
        friend bool operator>=(int lhs, const Node& rhs);
        friend bool operator<=(const Node& lhs, int rhs);
        friend bool operator<=(int lhs, const Node& rhs);

    };
    explicit BST(); // Default constructor
    BST(std::initializer_list<int> init); // Constructor using initializer list
    BST(const BST& other); // Copy constructor
    BST(BST&& other) noexcept; // Move constructor
    ~BST(); // Destructor
    BST& operator=(const BST& rhs); // = as copy
    BST& operator=(BST&& rhs) noexcept; // = as move

    Node*& get_root();
    void bfs(const std::function<void(Node*& node)>& func);
    size_t length() const;
    bool add_node(int value);
    Node** find_node(int value);
    Node** find_parrent(int value);
    Node** find_successor(int value);
    bool delete_node(int value);

    friend std::ostream& operator<<(std::ostream& os, const BST& obj);
    BST& operator++();
    BST operator++(int);

private:
    Node* root;
};

Homework 4

借助 template 来实现 C++ 中的新特性：智能指针，包括 unique_ptr 和 shared_ptr 。在完成过程中，主要遇到了如下问题：

Problem 1

想要实现

1
2
3
if (ptr) {
    // do something when ptr is not null
}

实际上只需要重载运算符

1
explicit operator bool() const { return p != nullptr; }

Homework 5

主要练习了基本的继承和多态。在完成过程中，主要遇到了如下问题：

Problem 1

继承的析构流程：先完成子类的析构函数，再完成超类的析构函数。

注意超类的析构函数需要被 virtual 声明，即

1
virtual ~EspressoBased();

Problem 2

考虑由指针组成的 vector 。在深度拷贝中，原始代码未将每个指针指向的对象进行拷贝，只是对 vector 本身做了深度拷贝，导致了析构时出现问题。解决方法就是对每个指针指向的对象做一次复制。

具体地，实现 clone 函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// ingredient.h
class Ingredient {
public:
    double get_price_unit() const;
    size_t get_units() const;
    virtual std::string get_name() const = 0;
    double price() const;
    virtual ~Ingredient() = default;
    virtual Ingredient* clone() const = 0;

protected:
    Ingredient(double price_unit, size_t units);
    double price_unit;
    size_t units;
    std::string name;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// sub_ingredients.h
#define DEFCLASS(X, price) \
class X : public Ingredient {\
public:\
    explicit X(const size_t units) : Ingredient{price, units} {\
        name = #X;\
    }\
    std::string get_name() const override { return name; }\
    X* clone() const override { return new X(*this); }\
}

DEFCLASS(Cinnamon, 5);

Problem 3

在重载等于号时（copy + move），没有将原来的 this 析构，导致出现内存泄露。解决方法即在 copy 和 move 前将原对象释放。

Homework 6

借助 STL 来解决四个问题，主要包括梯度下降算法、正则表达式匹配。在完成过程中，主要遇到了如下问题：

Problem 1

如何适配传入的函数？具体问题与解决方案如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// tests
struct Func {
    double operator()(double a) { return cos(a); }
};

auto min1 = q1::gradient_descent(0.01, 0.1, cos);
auto min2 = q1::gradient_descent(0.01, 0.01, cos);
auto min3 = q1::gradient_descent(0.01, 0.01,
    [](double a) { return sin(a) + cos(a); }
);
auto min4 = q1::gradient_descent(0.01, 0.01, Func{});
auto min5 = q1::gradient_descent<double, Func>(0.0, 0.01);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// solution
namespace q1 {
    inline double derivative(const double x, const std::function<double(double)>&func) {
        // do something ...
    }

    inline double solver(double x, const double step, const std::function<double(double)>&func) {
        for (int k = 0; k < 5000000; k += 1) {
            x = x - derivative(x, func) * step;
        }
        return x;
    }

    template<typename T, typename Func>
    double gradient_descent(const double x, const double step) {
        return solver(x, step, Func());
    }

    template<typename Func>
    double gradient_descent(const double x, const double step, Func func) {
        return solver(x, step, static_cast<const std::function<double(double)> &>(func));
    }

    inline double gradient_descent(const double x, const double step, double (*func)(double)) {
        return solver(x, step, func);
    }
}

Problem 2

如何使用正则表达式来匹配和获取数据？具体见代码实现。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 协议之条款下提供，附加条款亦可能应用