Hi, 👋, I’m Cookie

stl算法 算法把迭代器作为中介从而间接操作容器中的元素，而不直接操作容器本身。所有标准库算法都实现为函数模板的形式，其中模板类型参数一般都是迭代器类型。模板化的函数通常可通过函数参数推导出模板类型，因此通常情况下可以像调用普通函 数(而非模板)那样调用算法。 简单例子 1.find和find_if find()在某个迭代器范围内查找特定元素。可将其用于任意容器类型。这个算法返回所找到元素的迭代器: 如果没有找到元素，则返回迭代器范围的尾迭代器。注意调用 find()时指定的范围不要求是容器中元素的完整范围，还可以是元素的子集。 注意： 如果 fnd()没有找到元素，那么返回的迭代器等于函数调用中指定的尾迭代器，而不是底层容器的尾迭代器 auto endIt =cend(myVector); auto it = find(cbegin(myVector),endIt,num); // it == endIt -> not find // c++17 if (auto it = find(cbegin(myVector),endIt,num); it == endIt) { // not find } 一些容器(例如 map和 set)以类方法的方式提供自己的 find()函数。如果容器提供的方法具有与泛型算法同样的功能，那么应该使用容器相应的方法，那样速度更快。比如，泛型算法 find()的复杂度为线性时间，用于 map 迭代器时也是如此; 而 map 中find()方法的复杂度是对数时间。 find_if find_if()和 find()类似，区别在于 find _f()接收谓词函数回调作为参数，而不是简单的匹配元素。谓词返回true或false。find_if()算法对范围内的每个元素调用谓词，直到谓词返回ture: 如果返回了true,find if()返回这个元素的迭代器。 find_if(cbegin(myVector),endIt,Prec); 2.accumulate 我们经常需要计算容器中所有元素的总和或其他算术值。acumulate函数就提供了这种功能，该函数在(而非)中定义。通过这个函数的最基本形式可计算指定范围内元素的总和。 // 总和 int sum = accumulate(cbegin(nums)， cend(nums)， 0); // 给accumulate提供的二元回调。也可以是lambda int product(int num1，int num2) { return numl *num2; } // 计算乘积 double mult = accumulate(cbegin(nums)， cend(nums)，1，product); std:function std:function 在头文件中定义，可用来创建指向函数、函数对象或lambda 表达式的类型; 从根本上说可以指向任何可调用的对象。它被称为多态函数包装器，可以当成函数指针使用，还可用作实现回调的函数的参数。...

unique_ptr 考虑下面的函数，这个函数在堆上分配了一个 Simple 对象，但是不释放这个对象，故意产生内存泄漏。 void leaky() { Simple* mySimplePtr = new Simple(); // BUG! Memory is never released! mySimplePtr->go(); } 有时你可能认为，代码正确地释放了动态分配的内存。遗憾的是，这种想法几乎总是不正确的。比如这个函数: void couldBeLeaky() { Simple*mySimplePtr =new Simple(); mySimplePtr->go(); delete mySimplePtr; } 上面的函数动态分配一个 Simple 对象，使用该对象，然后正确地调用 delete。但是，这个例子仍然可能产生内存泄漏! 如果 go方法抛出一个异常，将永远不会调用 delete，导致内存泄漏。 这两种情况下应使用 unique_ptr。对象不会显式删除，但实例 unique_ptr离开作用域时(在函数的末尾，或者因为抛出了异常)，就会在其析构函数中自动释放 Simple 对象: void notLeaky() { auto mySimpleSmartPtr =make unique<Simple>(); mySimpleSmartPtr->go(); } 这段代码使用 C++14 中的 make_unique和 auto 关键字，所以只需要指定指针的类型，本例中是 Simple,如果Simple构造函数需要参数，就把它们放在make_unique()调用的圆括号中。 如果编译器不支持make_unique, 可以这种方式创建。 unique_ptr<Simple> p(new Simple()); 像标准指针一样，仍可以使用*或->对智能指针进行解引用。 get()方法可用于直接访问底层指针。这可将指针传递给需要普通指针的函数。例如 void processData(Simple* simple)( /* Use the simple pointer....

catch2用法 定义测试案例 测试案例在 Catch2 中通过 TEST_CASE 宏定义。TEST_CASE 宏接受两个参数：测试案例的名称和一个可选的标签。 #define CATCH_CONFIG_MAIN // 这行让 Catch 自己提供一个 main() 函数 #include <catch2/catch.hpp> TEST_CASE("A test case", "[tag]") { REQUIRE(1 == 1); } 如果你有多个测试文件，只需要在一个文件中定义 CATCH_CONFIG_MAIN。 断言 Catch2 提供了多种断言宏，最常用的是 REQUIRE 和 CHECK： REQUIRE：如果断言失败，当前的测试案例会立即停止。 CHECK：即使断言失败，当前的测试案例也会继续运行，允许多个断言失败。 TEST_CASE("Testing addition") { REQUIRE(1 + 1 == 2); CHECK(2 + 2 == 4); } 测试固件 测试固件允许你在每个测试案例之前和之后运行一些代码。测试固件允许你设置和清理测试环境，这对于需要在多个测试案例中重用相同的初始化和清理逻辑非常有用。测试固件通过定义一个结构体或类来实现，你可以在其中定义构造函数（用于设置）和析构函数（用于清理）。然后，使用 TEST_CASE_METHOD 宏来指定哪个固件类应该被用于哪个测试案例。 struct DatabaseFixture { Database db; DatabaseFixture() : db("my_database") { // 初始化代码，比如打开数据库连接 db.connect(); } ~DatabaseFixture() { // 清理代码，比如关闭数据库连接 db....

overview Lock Manager：锁管理器，利用 2PL 实现并发控制。支持 REPEATABLE_READ、READ_COMMITTED 和 READ_UNCOMMITTED 三种隔离级别，支持 SHARED、EXCLUSIVE、INTENTION_SHARED、INTENTION_EXCLUSIVE 和 SHARED_INTENTION_EXCLUSIVE 五种锁，支持 table 和 row 两种锁粒度，支持锁升级。Project 4 重点部分。 Deadlock Detection：死锁检测，运行在一个 后台线程，每间隔一定时间检测当前是否出现死锁，并挑选合适的事务将其 abort 以解开死锁。 Concurrent Query Execution：修改之前实现的 SeqScan、Insert 和 Delete 算子，加上适当的锁以实现并发的查询。 Lock Manager 首先理一理 Lock Manager 的成员： table_lock_map_：记录 table 和与其相关锁请求的map。 row_lock_map_：记录 row 和与其相关锁请求的map。 这两个 map 的值均为锁请求队列 LockRequestQueue： request_queue_：实际存放锁请求的队列 cv_ & latch_：条件变量和锁，配合使用可以实现经典的等待资源模型。 upgrading_：正在此资源上尝试锁升级的事务 id。 锁请求以 LockRequest 表示： txn_id_：发起此请求的事务 id。 lock_mode_：请求锁的类型,有S,X,IS,IX,SIX。 oid_：在 table 粒度锁请求中，代表 table id。在 row 粒度锁请求中，表示 row 属于的 table 的 id。 rid_：仅在 row 粒度锁请求中有效。指 row 对应的 rid。 granted_：是否已经对此请求授予锁 on_table_: 锁请求是在表上还是在行上 Lock Manager 的作用:...

实验中给出的 B+ 树接口非常简单，基本只有查询、插入和删除三个接口，内部基本没有给出别的辅助函数，可以让我们自由发挥（无从下手）。因此，任何合法的 B+ 树实现都是允许的。 B+ 树索引在 Bustub 中的位置如图所示: B+树种需要的page都需要使用在 Project 1 中实现的 buffer pool manager 来获取。 Checkpoint1 Single Thread B+Tree Checkpoint1 分为两个部分： Task1: B+Tree pages，B+树中的各种 page。在 Bustub 索引 B+ 树中，所有的节点都是一个 page。包含 leaf page，internal page ，和它们的父类 tree page。 Task2：B+Tree Data Structure (Insertion, Deletion, Point Search)。Checkpoint1 的重点，即 B+树的插入、删除和单点查询。 Task1 B+Tree Pages task1 主要实现leaf page和internal page这两个类，都继承自BPlusTreePage这个父类，实现一些Getter和Setter方法。 首先介绍一下page的内存布局 其中，data_ 是实际存放 page 数据的地方，大小为 BUSTUB_PAGE_SIZE，为 4KB。其他的成员是 page 的 metadata。 B+树中的 tree page 数据均存放在 page 的 data 成员中，也就是B+树中的节点是Page的data数据成员。...