程序在运行时需要请求操作系统分配内存以及释放内存，因此，程序员在编写程序时，需要显式（手动）地编写分配和释放内存的代码，或者隐式（自动，由语言保证）地进行内存管理。对于前者，C/C++ 是代表语言，程序员需要手动管理内存；对于后者，垃圾回收器（Garbage collector, GC）是一种常见的选择，诸如 Go/Java 等都提供了 GC。

事实上，C++ 标准库中提供了智能指针等工具，能够解决一部分的内存管理问题。但是由于 C++ 的高自由度，即使在使用智能指针时，仍十分容易编写出会导致内存错误的代码。

朴素的手动内存管理对程序员的要求更高，也意味着更容易出错，导致一些内存错误的产生，比如：

• 解引用存储已释放空间的地址的指针（Use after free）
• 没有释放空间导致的内存泄漏（Memory leak）
• 重复释放已经被重用的空间（Double free）

一个自动的内存管理机制，可以消除这些常见问题。GC 通过在运行时记录分配的空间和空间的使用信息来实现内存的自动管理，程序员就可以从内存管理中解放。但是，尽管这件事听起来还不错，但它意味着我们编写的程序在运行时，还附带着运行一个 GC，这当然会带来一些运行时的损耗。

如果你不想在运行时带着一个 GC，又不想像 C/C++ 一样手动检查违反了内存安全的代码的存在，那么可以看看 Rust 的解决方案。Rust 提供了一种不借助 GC，又能够保证内存安全的高效内存管理方式。

所有权 —— 大厦的基石

所有权（Ownership）是 Rust 最重要的特性之一，也是 Rust 能够高效地保证内存安全的同时避免引入 GC 的核心机制。

所有权是一组规则，描述了 Rust 程序如何管理内存。在 Rust 中，内存通过所有权系统来管理，该系统有一套由编译器进行检查的规则（即所有权规则），如果违反了任何一条规则，程序就不能被成功编译。因此，所有权是一组静态的、在编译时检查的规则。这意味着所有权系统不会带来运行时的损耗。

所有权规则有且只有如下三条规则：

• Rust 中的每个值都有一个被称为其所有者（Owner）的变量。
• 一个值在任一时刻有且只有一个所有者。
• 当所有者离开作用域时，这个值将被丢弃。

或许你认为这和大部分（OOP）语言中栈上对象在函数结束时进行析构，同时释放资源（RAII）的编程习惯似乎区别不大，事实上也确实如此，区别在于 Rust 将这种规则扩大到了所有值上，包括储存在堆上的值，并且由编译器保证。换言之，Rust enforces RAII。因此，在 Rust 中任何一个值（无论在栈上还是堆上），在不使用时（其所有者离开作用域）都将被丢弃（占用的空间被释放）。你可能已经发现了，没有内存泄漏的世界完成了。

然而，目前的世界十分简陋，如果只有这三条规则，一个简单的实现是在赋值时复制数据并创建一个新值，尽管这样的实现不违背所有权规则，但却是低效的。因此，本文的剩余部分介绍 Rust 中和所有权相关的其它组成部分，这些部分在不违背所有权规则的基础上，和所有权系统共同组成了 Rust 高效的内存安全世界。

移动

通常来说，复制堆上的数据被认为是缓慢的，因为堆上的数据通常较大，并且在复制时需要申请新的空间；而复制栈上的数据被认为是快速的，因为栈上的数据通常较小，并且类型的大小在编译时已知。

以 Rust 中的 String 类型为例，与其它语言中的字符串类型相似，String 类型由三部分组成：一个指向存放字符串内容（占用堆上空间）的指针，一个长度和一个容量。而这些数据存储在栈上。当一个 String 类型的值被丢弃时，就需要根据栈上存储的数据释放占用的堆上空间。

因此，为了避免复制堆上的数据，一种解决方案是允许在赋值时仅复制 String 在栈上的数据，但是这意味着堆上的空间此时分别被两个变量所有，在失效时会重复释放同一处堆上空间导致内存错误，同时也违背了所有权规则。对此，Rust 的解决方案是在复制了栈上数据之后，将该值的所有权转移给新变量，在当前作用域结束后，之前的所有者便不会再尝试释放堆上的空间。值的所有权的转移在 Rust 中被称为值的移动（Move）。同时，移动是 Rust 中赋值的默认行为。

Rust 中，变量的声明通过 let 语句完成，作用域与其它编程语言类似：

1
2
3
4

{ // s 在这里无效，它尚未声明
    let s = String::from("hello"); // 从这里开始 s 是有效的
    // 使用 s
} // 在此之后，s 离开当前作用域，不再有效

在赋值后，变量 s 绑定到了 String 类型的一个值，此时 s 是该值的所有者。而当 s 离开当前作用域后便不再有效，此时其绑定的值会被丢弃。那么当我们允许值的移动时，将另一个拥有 String 类型的值的变量赋值给新变量会发生什么？

1
2
3

let s1 = String::from("hello");
let s2 = s1;
// 此时使用 s1 会发生什么？

答案是 s1 的值会被移动给 s2，Rust 会认为 s1 不再有效，如果你此时使用 s1，编译会失败并得到一个错误：s1 的值已经被移动。而在所有权发生转移时，如前文所说，s2 其实复制了 s1 栈上的数据，并在此时令 s1 失效，避免两者在离开作用域时重复释放同一处堆上空间引发内存错误。

克隆和拷贝

有时我们确实需要复制 String 中的所有数据（包括堆上的数据），在 Rust 中被称为克隆（Clone），可以通过显式调用通用方法 clone 实现这样的功能。克隆会产生一个数据相同的新值，此时 s1 和 s2 分别是两个 String 的所有者：

1
2
3

let s1 = String::from("hello");
let s2 = s1.clone();
// s1 和 s2 都有效

前面提到了，移动时复制的是栈上的数据，而使之前的所有者失效，是为了避免重复释放空间。但是，除了像 String 一样在占用了堆上空间的类型，还有像整型一样所有数据都存储在栈上的类型。这些类型不需要释放堆上空间，意味着不需要令之前的所有者失效。因此，Rust 提供了一个叫做 Copy trait 的类型注解用于这些类型，对于满足 Copy trait 的类型，赋值时会产生一个新值，行为与克隆相似，但不需要显式指定，在 Rust 中被称为拷贝（Copy）：

1
2
3

let x = 42;
let y = x;
// x 和 y 都有效

因此，在 Rust 中，移动是赋值时值的一般行为，而拷贝是当数据仅存储在栈上时值的特殊行为，值的克隆则不会自动发生，需要程序员的显式调用。这隐含了 Rust 在设计时的一个选择：不自动进行数据的“深拷贝”。可以认为任何自动的复制对运行时性能的影响较小。

扩展到函数

事实上，几乎所有的编程语言中都有函数（或者类似的概念），而函数的调用涉及到值的传递和返回，因此我们还需要考虑在涉及到函数时，值和所有权的行为。由于向函数传递值，类似于将值赋值给函数的参数，而函数返回值类似于将返回值赋值给调用者声明的一个变量（或者不可见的临时变量）。因此，一个将所有权扩展到函数的简单实现是，在向函数传递值以及函数返回值时，采用和赋值一样的行为。在 Rust 中，向函数传递值时值的行为和赋值时相同，可能会移动或者拷贝，同样的，函数的返回值也可以移动：

1
2
3
4
5
6
7
8
9

fn main() {
    let s1 = String::from("hello");
    let s2 = foo(s1); // s1 经由 foo 被移动给 s2
    // s1 不再有效
}

fn foo(s: String) -> String { // s 进入作用域
    s // 返回 s 并移动给调用者
}

至此，通过所有权系统检查的代码中，值都能被正确地丢弃，空间都能被正确地回收，并且被移动过的值可以保证不会被再次使用。同时，这一切又都是高效的。

引用和借用

世界在拥有了所有权和移动语义后变得更好了，但是或许还不够好。比如，当我们实现的一个函数只希望使用一个参数的值，又不想获取所有权，并且调用者也希望在调用完成后继续使用它。在目前的世界里，函数需要在获取参数的所有权之后，在返回的时候再将该参数移动给调用者：

1
2
3
4
5
6
7
8
9
10

fn main() {
    let s1 = String::from("hello");
    let (s2, len) = length(s1);
    println!("The length of '{}' is {}.", s2, len);
}

fn length(s: String) -> (String, usize) {
    let len = s.len(); // len() 返回字符串的长度
    (s, len) // 可以使用元组返回多个值
}

尽管这样确实可行，而且对运行时的影响似乎也可以接受（只需要复制一些栈上的数据就行了），但是问题在于，没有人想要这样啰嗦地写代码。Rust 对此的解决方案是，提供了一个不获取值的所有权，但可以暂时获取值的使用权的功能，叫做引用（Reference）。

在 Rust 中，引用存储值的地址，我们可以根据该地址访问属于其它变量的值。在 Rust 中，指向类型为 String 的值的引用的类型为 &String。对于类型为 String 的值 s，我们可以通过 &s 创建一个指向 s 的引用。这些 & 符号表示引用，而 Rust 将创建一个引用的行为称为借用（Borrowing）。同时，引用无需返回值来归还所有权，因为它不具有值的所有权，这与本节开始提出的需求是一致的。因此，我们可以改写本节开始的代码：

1
2
3
4
5
6
7
8
9

fn main() {
    let s1 = String::from("hello");
    let len = length(&s1);
    println!("The length of '{}' is {}.", s1, len);
}

fn length(s: &String) -> usize {
    s.len() // len() 返回字符串的长度
}

生命周期

事实上，许多编程语言中都有和引用类似的概念，但是在没有 GC 的语言中，引用（或者类似的功能）的使用可能会导致一些错误，比如[悬垂引用](Dangling Pointer)，即引用没有指向有效对象。而在 Rust 中，引用确保指向某个特定类型的有效值。引用有效性的保证依赖于生命周期（Lifetime）机制，它是与所有权机制同等重要的内存管理机制。

生命周期是引用必须有效的代码区域（与作用域的概念接近）。与所有权机制相似，生命周期机制也要求编译器保证代码满足一些关于生命周期的规则，事实上，这由编译器中的借用检查器（Borrow checker）来保证。同样的，这些的规则的检查也发生在编译时，因此不会影响运行时效率。

考虑下面的程序，它有一个外部作用域和一个内部作用域：

1
2
3
4
5
6
7
8

{
    let r;                // ---------+-- 'a
    {                     //          |
        let x = 5;        // -+-- 'b  |
        r = &x;           //  |       |
    }                     // -+       |
    println!("r: {}", r); //          |
}                         // ---------+

在注释中，我们将 r 的生命周期标记为 'a，将 x 的生命周期标记为 'b。显然，'b 块要比 'a 块小。在编译时，Rust 比较这两个生命周期的大小，并发现生命周期为 'a 的 r 引用了一个生命周期为 'b 的对象 x。由于生命周期 'b 比生命周期 'a 小，这意味着被引用的对象比它的引用者存在的时间更短，因此程序被拒绝编译。如果成功编译，这将导致悬垂引用。这是借用检查器需要检查的规则之一：一个引用的生命周期不超过其引用的对象的生命周期。

大部分时候，生命周期是隐含并可以推断的（比如在函数体内，局部引用的生命周期通常与作用域保持一致）。但在一些情况下，比如当引用跨越了函数边界（作为参数）时，这种时候，引用的生命周期和调用者有关，编译器此时缺乏足够的信息进行判断。为此，Rust 提供了一种可以描述多个引用生命周期相互的关系，而不影响其生命周期的功能，叫做生命周期注解（Lifetime annotation）。程序员可以通过生命周期注解，提供给编译器足够的信息，以便借用检查器可以进行分析。

总结

或许你作为一名有经验的程序员，在编程中可能已经遵守了上述这些准则，但是 Rust 的贡献在于，它将这些准则和语言的设计良好地结合在一起，通过提高了编译器的能力，减轻了程序员编程时的负担，同时尽可能地避免性能上的损耗。事实上，除了内存安全方面，Rust 也通过许多设计尝试避免包括线程安全和类型安全在内的安全问题。而本文介绍的内容，也只是 Rust 中的冰山一角。

也算是日经问题了, 但我太弱了, 还是得记一下, 首先看下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

struct Test {
    Test() = default;
    Test(const Test&) {
        std::cout << "copy ctor" << std::endl;
    }
    Test(Test&&) {
        std::cout << "move ctor" << std::endl;
    }
};

Test test(Test t) {
    return t;
}

int main() {
    Test t1;
    auto t2 = test(t1);
    return 0;
}

输出为：

1
2

copy ctor
move ctor

第一个 copy ctor 很好理解, 那么第二个是哪里的呢? 答案是 test 返回的时候, 首先因为 t 是形参, 所以在 return 这里不满足 copy elision 的要求, 所以这里不会进行优化, 故需要调用一次构造函数, 比如我们把 auto t2 = test(t1) 修改为 test(t1), 会发现输出没有改变

那为什么 return t 的时候调用的是移动构造函数而不是复制构造呢, 参见class.copy.elision #3, 简单点说就是在需要复制语义时, 如果条件允许, 可以使用移动操作, 那么我们把移动构造删掉应该可以使用复制构造了吧, 那就改成下边这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct Test {
    Test() = default;
    Test(const Test&) {
        std::cout << "copy ctor" << std::endl;
    }
    Test(Test&&) = delete;
};

Test test(Test t) {
    return t;
}

int main() {
    Test t1;
    auto t2 = test(t1);
    return 0;
}

这段代码用 C++17 是可以编译的, 并且打印结果和预期一样, 是两个 copy ctor, 但是在 C++17 之前(以及 C++11 之后)编译是通不过的, 这又是为什么呢?

答案是在复制初始化的时候, 如果初始化器是一个右值, 重载决议的时候会选择移动构造, 而如果移动构造被显式弃置(delete)了, 就会报错, 但是在 C++17 之后, 因为 copy elision 是强制的, 所以这里不需要调用移动构造, 从而也就不会报错, 比如我们还是把 auto t2 = test(t1) 改成 test(t1), 在 C++17 之前也可以通过编译了

但是除此之外还有一个问题, 当我们把显式弃置移动构造的语句删掉时, 变成下边这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

struct Test {
    Test() = default;
    Test(const Test&) {
        std::cout << "copy ctor" << std::endl;
    }
};

Test test(Test t) {
    return t;
}

int main() {
    Test t1;
    auto t2 = test(t1);
    return 0;
}

还是可以正常通过编译的, 尽管当用户声明了复制构造函数之后, 移动构造函数不会被隐式声明, 但是重载决议会忽略掉这件事, 因为会阻止从右值复制初始化, 参见移动构造函数一节中所述:

The deleted implicitly-declared move constructor is ignored by overload resolution (otherwise it would prevent copy-initialization from rvalue).

之前写(抄) parsec 的时候, 在重载 operator>> 的时候, operator>> 需要接收一个 lambda, 之后返回一个 Component<R>, 其中 R 是接收 lambda 的返回值类型, 所以就要搞到 lambda 对应的函数类型

在一开始我是直接用 std::function 做的, 但是众所周知, 下面这样的写法是匹配不了的:

1
2
3
4
5
6

template<typename R, typename ...Args>
ParsecComponent<R> operator>>(std::function<R(Args...)> callback) {
    ParsecComponent<R> component;
    ...
    return component;
}

因为 lambda 表达式到 std::function 要进行类型转换, 毕竟是两个类型, 所以指明 std::function 的模板实参的时候才能进行 lambda -> std::function 的隐式转换, 不过一开始为了偷懒, 而且我只需要拿到 lambda 的返回值类型, 就这样写了:

1
2
3
4
5
6
7

template<typename Func>
auto operator>>(Func &&callback) {
    using NewResult = typename decltype(std::function(callback))::result_type;
    ParsecComponent<NewResult> component;
    ...
    return component;
}

所以说 auto 这种东西还真是好用啊, 类型还可以拖延到函数体里做(

这样做总归有种脱裤子放屁的感觉, 那么怎么不通过 std::function 就能拿到 lambda 表达式对应的函数类型呢?

众所周知, 每一个 lambda 表达式的类型都是不一样的, 比如:

1
2
3
4
5
6
7
8
9
10

template<typename Func>
void print(Func &&f) {
    std::cout << typeid(Func).name() << std::endl;
}

int main() {
    print([](){});
    print([](){});
    return 0;
}

我这里输出的结果是

1
2

Z4mainE3$_0
Z4mainE3$_1

毕竟如果要每个定义相同的 lambda 的类型相同是不现实而而且没有必要的, 何况还有闭包捕获之类的复杂性需要考虑, 但是众所周知, lambda 返回的是一个对象, 也即它的类型重载了 operator(), 而 operator() 又是一个函数, 那么我们不久可以通过推导其重载的 operator() 函数类型拿到 lambda 对应的函数类型了吗(

所以这件事情很清晰明了了, 我们只需要拿到 lambda 表达式产生的匿名类型, 然后根据类成员函数寻址到它的 operator(), 然后推导出 operator() 的函数签名就可以了!

那就划分成三步吧

一, 得到 lambda 对应的匿名类类型

这一步是很简单的, 因为只要模板实参自动推导一下就出来了

1
2

template<typename Func>
void foo(Func &&lambda);

那现在这个 Func 就是我们需要的类型

二, 推导 Func 重载的 operator() 函数签名

因为当前我们只有一个 Func 类型, 但是如果要获取 operator() 的签名的话, 我们还需要对 operator() 的类型做一个特化, 比如

1
2
3
4
5
6
7
8
9

template<typename T> struct lambda_traits;
template<typename R, typename ClassType, typename ...Args>
struct lambda_traits<R(ClassType::*)(Args...) const> {
    using result_type = R;
    using args_type = std::tuple<Args...>;
    template<size_t index>
    using arg_type_at = std::tuple_element_t<index, args_type>;
    static constexpr size_t arity = sizeof...(Args);
};

很简单对吧, 只需要对类的成员函数的类型做一个特化就好了

其实这个时候已经可以用了, 比如

1
2
3

template<typename Func,
    typename R = typename lambda_traits<decltype(&Func::operator())>::result_type>
void foo(Func &&lambda);

三, 包装一下

其实可以看到第二步的时候已经可以用了, 那么我们只需要把调用的过程包装一下, 但是由于我们拿到的是一个 Func, 所以需要把之前的 lambda_traits 变成基类, 然后另 Func 实例化的模板类继承它就可以了

1
2
3
4
5
6
7
8
9
10
11
12

template<typename T> struct lambda_traits_base;
template<typename R, typename ClassType, typename ...Args>
struct lambda_traits_base<R(ClassType::*)(Args...) const> {
    using result_type = R;
    using args_type = std::tuple<Args...>;
    template<size_t index>
    using arg_type_at = std::tuple_element_t<index, args_type>;
    static constexpr size_t arity = sizeof...(Args);
};

template<typename Func>
struct lambda_traits : lambda_traits_base<decltype(&Func::operator())> {};

支持 C++17 的 lambda 现在是没有问题了, 那么有人要问了, C++20 的 lambda 是支持模板 operator() 的, 这个显然是不支持的啊, 是垃圾

那就来接轨一哈 20 吧, 反正接轨了之后是不影响 17 的 lambda 推导的

支持 template operator() 的 lambda 顾名思义就是长这样子的啦:

1
2

auto foo = []<typename T, typename ...Args>(Args...) -> T { return T(); };
foo.operator()<...>(...);

可以看出来(目前)如果要调用这个 lambda 的话, 我们需要显式地指明模板的实参, 所以在推导的时候, 模板实参的信息也是要提供的, 那么只需要简单地修改一下我们的 lambda_traits:

1
2
3
4
5

template<typename Func, typename ...Args>
struct lambda_traits : lambda_traits_base<decltype(&Func::template operator()<Args...>)> {};

template<typename Func>
struct lambda_traits : lambda_traits_base<decltype(&Func::operator())> {};

这样一来就可以了, 不过还有一种特殊情况, 比如说我们有一个这样类似提供了 template operator() 的类:

1
2
3
4
5

struct Foo
{
    template<typename ...Args>
    void operator() {};
};

当我们在获取他无模板实参的 operator() 时, 我们只能通过 &Foo::template operator()<> 而不能写 &Foo::operator(), 当然这也是显而易见的, 不过如果我们的 lambda 支持的 template operator() 能够接收无实参的实例化的话, 就会导致前边的 lambda_traits 失效, 所以我们需要在模板实参 Args 为空的时候判断一下要取 operator() 还是 template operator()<>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

template<typename T, typename = std::void_t<>>
struct call_which {
    using type = decltype(&T::operator());
};
template<typename T>
struct call_which<T, std::void_t<decltype(&T::template operator()<>)>> {
    using type = decltype(&T::template operator()<>);
};
template<typename T>
using call_which_t = typename call_which<T>::type;

template<typename T, typename ...Args>
struct lambda_traits : lambda<decltype(&T::template operator()<Args...>)> {};
template<typename T>
struct lambda_traits<T> : lambda<call_which_t<T>> {};

通过 void_t 判断了一下是不是具有 template operator()<> 就可以了

前一段时间看到了梨梨喵聚聚写的Parser Combinator 在 C++ 里的 DSL, 感觉好厉害, 正好毕设里要写一部分前端, 昨天又把这篇文章看了一遍, 想着我也要用这么酷炫的东西来参与一下毕设, 于是今天仿了一个, 不过由于电脑屏幕太小(理由), 看不懂梨梨喵聚聚的代码, 只好照着文章里的理念自己试着实现一下, 类的设计应该差不多, 不过具体的实现应该鶸了很多, 代码在parsec, 目前还不支持左递归和垃圾回收(

先上一个加减的小例子吧:

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

Parsec<char> Decimal;
Parsec<string> Number;
Parsec<int> Primary, Additive, Additive_;

// Decimal := '0' | ... | '9'
Decimal = ('0'_T | '1'_T | '2'_T | '3'_T | '4'_T | '5'_T | '6'_T | '7'_T | '8'_T | '9'_T );

// Number := Decimal Number | Decimal
Number =
    (Decimal + Number >>
        [](char decimal, string number) {
            return decimal + number;
        }) |
    (Decimal >>
        [](char decimal) {
            return string() + decimal;
        });

// Primary := Number
Primary = Number >> [](string number) {
    return stoi(number);
};

// Additive := Primary Additive_ | Primary
// Additive_ := + Additive | - Additive
Additive =
    (Primary + Additive_ >>
        [](int primary, int additive) {
            return primary + additive;
        }) |
    (Primary >> [](int primary) {
        return primary;
    });
Additive_ = (('+'_T | '-'_T) + Additive >> [](char op, int additive) {
    return (op == '+' ? additive : -additive);
});

cout << Additive("1+2+3") << endl;

例子是改的梨梨瞄聚聚的, 因为不支持左递归, 只能手动提取公因子了(

和梨梨瞄聚聚重复的原理部分就不说了, 想知道的可以看一下梨梨瞄聚聚的那篇文章, 说一下不一样的地方吧, 我的实现里的类型笛卡尔乘积的结果使用 std::tuple<Ts…> 表示的, 类型的和的结果用 std::variant<Ts…> 表示, 当返回值的类型可能有多类型的时候就可以使形参的类型为 std::variant<Ts…>, 保证类型安全的同时还能接收多个类型的结果, 同样可以令组合子返回的是一个 tuple 类型, 可以继续和其它类型相乘或者相加, 后边就可以简化实现.

写了好几个小时, 虽然代码不多, 但是模板多起来密度太大真的眼花缭乱, 希望之后能支持一下左递归之类的操作吧, 毕竟还要拿来写毕设, 边用边改吧(

看到特首写了个编译时的归并，感觉挺好玩，写了个冒泡试试，第一次用模板写这种东西，见笑了（

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <iterator>
#include <type_traits>

using namespace std;

template<int ...vals> struct Vals {};

template<int i, typename T> struct ValueAt;
template<int i, int val0, int ...vals> struct ValueAt<i, Vals<val0, vals...>>
{
    constexpr static int val = ValueAt<i - 1, Vals<vals...>>::val;
};
template<int val0, int ...vals> struct ValueAt<0, Vals<val0, vals...>>
{
    constexpr static int val = val0;
};

template<typename T1, typename T2> struct Combine;
template<int ...vals1, int ...vals2> struct Combine<Vals<vals1...>, Vals<vals2...>>
{
    using type = Vals<vals1..., vals2...>;
};

template<int i, typename T> struct SwapValue;
template<int i, int val, int ...vals> struct SwapValue<i, Vals<val, vals...>>
{
    using type = typename Combine<Vals<val>, typename SwapValue<i - 1, Vals<vals...>>::type>::type;
};
template<int val1, int val2, int ...vals> struct SwapValue<0, Vals<val1, val2, vals...>>
{
    using type = typename Combine<Vals<val2>, typename Combine<Vals<val1>, Vals<vals...>>::type>::type;
};
template<int val1, int val2> struct SwapValue<0, Vals<val1, val2>>
{
    using type = Vals<val2, val1>;
};

template<int i, int j, typename T> struct BubbleSort
{
    using type = typename conditional_t<(ValueAt<j - 1, T>::val > ValueAt<j, T>::val),
        BubbleSort<i, j + 1, typename SwapValue<j - 1, T>::type>,
        BubbleSort<i, j + 1, T>>::type;
};
template<int val> struct BubbleSort<1, 1, Vals<val>>
{
    using type = Vals<val>;
};
template<int j, int ...vals> struct BubbleSort<sizeof...(vals), j, Vals<vals...>>
{
    using type = Vals<vals...>;
};
template<int i, int ...vals> struct BubbleSort<i, sizeof...(vals), Vals<vals...>>
{
    using type = typename BubbleSort<i + 1, 1, Vals<vals...>>::type;
};

template<typename T> struct Sort
{
    using type = typename BubbleSort<0, 1, T>::type;
};

template<int ...vals> void print(Vals<vals...>)
{
    static constexpr auto vs = { vals... };
    copy(begin(vs), end(vs), ostream_iterator<int>(cout, " "));
    endl(cout);
}

int main()
{
    print(Sort<Vals<1>>::type());
    print(Sort<Vals<2,1>>::type());
    print(Sort<Vals<3,5,2,8,7,1,6,9,4>>::type());
    return 0;
}

代码本身很简单，就是冒泡的思路，递归 j 的终止条件应该还可以优化一下

前两天给 Ice 加了 call/cc, 为此还重构了一波, 实现 call/cc 还是因为看了轮子哥的大专系列（

里边说提供 continuation 语言实现 Coroutine 起来很轻松, 后来又查了一些资料, 都说 continuation 表达能力很强, 就实现了一手, 调用方式完全等同 call/cc, 既然是看 Coroutine 才要实现 call/cc, 那实现了之后当然要用 call/cc 实现一手 Coroutine 了(

不过这个 Coroutine 比较简陋, 只提供 create, resume, yield, destroy

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

coroutine: (@() {
    @funcs: [];
    @conts: [];
    @deletes: [];
    @co_cont: none;

    @create(func) {
        if deletes.empty() {
            @id: funcs.size();
            funcs.push(func);
            conts.push(none);
            return id;
        } else {
            @id: deletes.pop();
            funcs[id]: func;
            conts[id]: none;
            return id;
        }
    }

    @resume(id) {
        if conts[id] = none {
            conts[id]: call_with_current_continuation(@(cont) {
                co_cont: cont;
                funcs[id]();
            });
        } else {
            conts[id]: call_with_current_continuation(@(cont) {
                co_cont: cont;
                conts[id](none);
            });
        }
    }

    @yield() {
        call_with_current_continuation(co_cont);
    }

    @destroy(id) {
        funcs[id]: conts[id]: none;
        deletes.push(id);
    }

    return @() {};
})();

测试一下:

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

@foo() {
    @i: 0;
    while i < 5 {
        println(i: i + 1);
        coroutine.yield();
    }
}

@id1: coroutine.create(foo);
@id2: coroutine.create(foo);

@i: 0;
while i < 5 {
    coroutine.resume(id1);
    coroutine.resume(id2);
    i: i + 1;
}

coroutine.destroy(id1);
coroutine.destroy(id2);

输出

1
2
3
4
5
6
7
8
9
10

1
1
2
2
3
3
4
4
5
5

里边唯一我觉得有点意思的地方是 resume 里, 直接在 lambda 里将当前的 continuation 绑定到 co_cont 上, 这样用户 create 的时候传入的函数就只需要调用 yield 了

可惜除了 vsc 都没有 Ice 的高亮(

最近写设计模式作业的时候, 有一个作业是实现装饰器模式 (Decorator Pattern), 由于我不会 Java, 所以只能用 C++ 来实现 :)

在这个背景下, 会有简单(表意)的几个类, 如下:

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

class Base
{
  public:
    virtual ~Base() = 0;
    virtual int getData() const = 0;
};

inline Base::~Base() {}

class DerivedA final : public Base
{
  public:
    DerivedA(int data) : data_(data) {}
    int getData () const override
    {
        return data_;
    }

  private:
    const int data_;
};

class DerivedB final : public Base
{
  public:
    DerivedB(const Base &pre) : pre_(pre) {}
    int getData () const override
    {
        return pre_.getData() + 1;
    }

  private:
    const Base &pre_;
};

简单来写就是上面这样, DerivedB 类型的对象可以接收以 Base 类作为基类的对象引用并且绑定到成员 pre_ 上, 在调用 getData 方法时会调用 pre_ 绑定的对象的 getData 方法, 并在其结果的基础上运算后返回

而这样的设计会导致一种很直觉的使用方法, 如下:

1

cout << DerivedB(DerivedB(DerivedA(10))).getData() << endl;

也即嵌套对象, 实现 getData 的多次调用

但是这样的使用方式会造成与预期不符的结果出现, 如下:

1
2
3
4
5
6

~> g++ -std=c++17 test.cpp -o test
~> ./test
11
~> clang++ -std=c++17 test.cpp -o test
~> ./test
11

会发现结果表明, 只有一个 DerivedB 类型的对象被构造了出来, cppreference 的 copy elision 章节中的解释部分有提到:

Under the following circumstances, the compilers are required to omit the copy and move construction of class objects, even if the copy/move constructor and the destructor have observable side-effects. The objects are constructed directly into the storage where they would otherwise be copied/moved to. The copy/move constructors need not be present or accessible, as the language rules ensure that no copy/move operation takes place, even conceptually:

• In a return statement, when the operand is a prvalue of the same class type (ignoring cv-qualification) as the function return type:

1 2 3 4 5

T f() { return T(); } f(); // only one call to default constructor of T

• In the initialization of a variable, when the initializer expression is a prvalue of the same class type (ignoring cv-qualification) as the variable type:

1	T x = T(T(f())); // only one call to default constructor of T, to initialize x

上面这句被我标粗的文字可以看到, 即使拷贝/移动构造有副作用, 依然只构造一次, 甚至不需要有拷贝/移动构造函数

可以在类中添加如下定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class DerivedB final : public Base
{
  public:
    // new additions
    DerivedB(const DerivedB &) = delete;
    DerivedB(DerivedB &&) = delete;

    DerivedB(const Base &pre) : pre_(pre) {}
    int getData () const override
    {
        return pre_.getData() + 1;
    }

  private:
    const Base &pre_;
};

会发现依然可以通过编译并且运行结果与之前相同 ( 因为在 C++17 中 Copy Elision 已经不再是可选项 ), 但是在 C++17 之前如果 delete 了这两个拷贝/移动构造函数, 会导致无法通过编译, 尽管有可以匹配 const Base & 类型的构造函数, 也依然不可以:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

test.cpp:45:13: error: functional-style cast from 'DerivedB'
      to 'DerivedB' uses deleted function
    cout << DerivedB(DerivedB(DerivedA(10))).getData...
            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
test.cpp:31:5: note: candidate constructor has been
      explicitly deleted
    DerivedB(DerivedB &&) = delete;
    ^
test.cpp:30:5: note: candidate constructor has been
      explicitly deleted
    DerivedB(const DerivedB &) = delete;
    ^
test.cpp:33:5: note: candidate constructor
    DerivedB(const Base &pre) : pre_(pre) {}
    ^
1 error generated.

感谢 禽牙 在评论中提出, 事实上如果我们在尚未 delete 那两个构造函数通过如下的方式调用, 也依然不可行:

1
2
3
4

DerivedA a(10);
DerivedB b1(a);
DerivedB b2(b1);
cout << b2.getData() << endl;

结果依然是 11, 这是因为重载决议后其实我们调用的是匹配类型为 const DerivedB & 的构造函数, 同样如果我们约定在代码中都是用这样的方式编写程序, 我们就可以获得一种解决方式, 编写匹配类型的构造函数, 如下:

1
2
3

...
DerivedB(const DerivedB &pre) : pre_(pre) {}
...

再通过声明中间变量的方式调用就可以获得正确结果, 但是通过纯右值的形式依然不行:

1
2
3
4
5
6
7
8
9
10

...
DerivedA a(10);
DerivedB b1(a);
DerivedB b2(b1);
cout << b2.getData() << endl;
// print 12
...
cout << DerivedB(DerivedB(DerivedA(10))).getData() << endl;
// print 11
...

所以如何才能在这种设计下通过这种方式正常使用呢?

一种可以显著增加代码程度的方式是, 手动添加强制转换:

1
2

cout << DerivedB(static_cast<const Base &>(DerivedB(DerivedA(10)))).getData() << endl;
cout << DerivedB((const Base &)(DerivedB(DerivedA(10)))).getData() << endl; // C-style

当然这种方式其实还是可以接受的

还有一种可以不会增加太多冗余代码的方式是在构造函数里增加一个冗余参数, 区分开就可以了, 比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

...
class DerivedB final : public Base
{
  public:
    DerivedB(const Base &pre, int) : pre_(pre) {}
    int getData () const override
    {
        return pre_.getData() + 1;
    }

  private:
    const Base &pre_;
};
...
cout << DerivedB(DerivedB(DerivedA(10), 0), 0).getData() << endl;

当然以上两种都是在不涉及模板的情况下完成的, 但是都会对调用的方便性产生影响

还有一种不会更改调用方式, 通过模板区分嵌套的相同类型的方式, 感谢 91khr 提供:

首先先将 DerivedB 变成一个类模板, 之后添加模板推导指引来实现嵌套区分

1
2
3
4
5
6
7
8

...
template <int Lv>
class DerivedB;
...
template <typename Ty> DerivedB(Ty) -> DerivedB<0>;
template <int Lv> DerivedB(DerivedB<Lv>) -> DerivedB<Lv + 1>;
...
cout << DerivedB(DerivedB(DerivedA(10))).getData() << endl;

在此条件之下, 结果与预期相同, 完美解决问题:

1
2
3

~> clang++ -std=c++17 test.cpp -o test
~> ./test
12