Project 0

发表于 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 6 分钟

Foreword

做的是2023 spring的版本，只会C with STL的人有难了

dynamic_cast

如果指向的对象(*pt)的类型为Type或是从Type直接或间接派生而来的类型，运算符将返回对象的地址，否则返回一个空指针

1
dynamic_cast<Type *>(pt)

std::shared_ptr

能够记录多少个shared_ptr共同指向一个对象，从而消除显示的delete调用，当引用计数变为零的时候将对象自动删除

1
2
3
4
5
6
std::shared_ptr<int> p1 = std::make_shared<int>(10);
auto p2 = p1; // 引用计数加1
int *p = p1.get(); // get方法获取原始指针
std::cout << p1.use_count() << '\n'; // 2
p2.reset(); // 引用计数减1
std::cout << p1.use_count() << '\n'; // 1

std::unique_ptr

独占的智能指针，禁止其他智能指针与其共享同一个对象，从而保证代码的安全

1
2
3
std::unique_ptr<int> p1 = std::make_unique<int>(10);
std::unique_ptr<int> p2 = p1; // 非法
std::unique_ptr<int> p3 (std::move(p1)); // 可通过std::move获得所有权

std::weak_ptr

std::shared_ptr仍然存在着可能无法释放资源的问题

比如经典的循环引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct A;
struct B;

struct A {
    std::shared_ptr<B> pointer;
    ~A() {
        std::cout << "A 被销毁" << std::endl;
    }
};
struct B {
    std::shared_ptr<A> pointer;
    ~B() {
        std::cout << "B 被销毁" << std::endl;
    }
};
int main() {
    auto a = std::make_shared<A>();
    auto b = std::make_shared<B>();
    a->pointer = b;
    b->pointer = a;
}

解决方法就是把一个std::shared_ptr改成std::weak_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct A;
struct B;

struct A {
    std::weak_ptr<B> pointer;  // 改为 weak_ptr
    ~A() {
        std::cout << "A 被销毁" << std::endl;
    }
};
struct B {
    std::shared_ptr<A> pointer;
    ~B() {
        std::cout << "B 被销毁" << std::endl;
    }
};

主要是用于检查std::shared_ptr是否存在

右值引用

左值：表达式后依然存在的持久对象

右值：表达式结束后不再存在的临时对象

纯右值：不是将亡值的右值

将亡值：即将被销毁，却能够被移动的值

1
2
3
4
5
6
7
std::vector<int> foo() {
    std::vector<int> temp = {1, 2, 3, 4};
    return temp;
}
std::vector<int> v = foo();
// 对于传统理解，这段代码的运行过程是：v获得foo的返回值temp时，会把temp拷贝一份，然后把temp销毁，开销大
// 对于C++11之后，编译器会将左值temp隐式右值转换，等价于static_cast<std::vector<int> &&>(temp)，然后v移动foo返回的值

要拿到一个将亡值，就需要用到右值引用：T &&

其中 T 是类型，右值引用的声明让这个临时值的生命周期得以延长

只要变量还活着，那么将亡值将继续存活

移动语义

std::move本身只是起到类型转换的作用，把左值转换成右值引用

是移动构造函数或移动赋值符的内部实现进行移动(交换指针、重置原对象等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream> // std::cout
#include <utility> // std::move
#include <vector> // std::vector
#include <string> // std::string

int main() {

    std::string str = "Hello world.";
    std::vector<std::string> v;

    // 将使用 push_back(const T&), 即产生拷贝行为
    v.push_back(str);
    // 将输出 "str: Hello world."
    std::cout << "str: " << str << std::endl;

    // 将使用 push_back(const T&&), 不会出现拷贝行为
    // 而整个字符串会被移动到 vector 中，所以有时候 std::move 会用来减少拷贝出现的开销
    // 这步操作后, str 中的值会变为空
    v.push_back(std::move(str));
    // 将输出 "str: "
    std::cout << "str: " << str << std::endl;

    return 0;
}

std::string_view

提供对std::string的只读视图，本身不持有数据，用于只读函数，性能更好

Task1

实现支持单线程操作的可持久化Trie

Get

沿key遍历路径，利用dynamic_cast判断终点是否确实是值节点

Put

遍历key，若当前字符的路径存在，clone一个node，否则创建一个node

遍历到倒数第二个字符的时候，特殊处理最后一个字符对应的node是否存在

如果不存在，新创建一个值节点，否则用已有节点的children_和value创建一个值节点

Remove

递归地删，写一个辅助函数形如dfs(root, index)

当index == key.size()时，到达递归出口，如果这个节点没有孩子，直接返回nullptr说明删掉就好，否则return没有值的node，保留children_

自下往上地判断要不要把每一个节点删掉就好了

Task2

实现支持并发操作的可持久化Trie

并发场景是多reader单writer

get照伪代码写，put和remove对于写操作开大锁就好了

Task3

debug能力测试

用vscode的可视化debug就能直接看出前两个答案

第三个可以先用vscode的可视化找到需要的节点地址

然后在vscode的debug console里直接用类型强转命令比如

1
-exec p *(TrieNodeWithValue<unsigned int>*)0x608000000630

然后再通过这个东西的value_ptr的地址得到真实值

1
-exec print *($1.value_.get())

Task4

实现大小写转换逻辑，注册到sql层