在C++17中的部分新特性

C++17已经发布了有一些时候,并且很多的编译器已经完成了对C++17的支持,那对于C++17中的新特性,我也好奇的玩了一些,其中的几个新特性特别吸引我的注意。

if-init

Grammar

if ( init-statement condition ) init-statement 可以是:

  • 表达式语句(可以是空语句,仅;
  • 声明语句

Thinking

if-init 这个 feature 尝试着让我们的代码更可读和干净,并且可以帮助我们更好的控制对象的生命周期。在从前的 if 语句中,我们经常会做类似的事情:

void foo(int a) {
    auto iter = a_map.find(a);
    if (iter != a_map.end()) {
        // do_something
    } else {
        // do_something_else
    }
    // do_something_next
}

这个叫做iter的变量其实我们除了用于这个if判断和语句块中的操作之外,我们可能再也不会用到它。它的生命周期其实无形的被延长到了整个函数的结束。就像我们在for语句中做的一样,我们为什么不把这个对象的生命周期限定在一个if语句块中呢?所以就有了 if-init 这个 feature。

void foo(int a) {
    if (auto iter = a_map.find(a); iter != a_map.end()) {
        // do_something
    } else {
        // do_something_else
    }
    // do_something_next
}

这里的写法就像在for语句中的那样自然,我们在一个if中初始化一个对象,并且使用它,当离开if语句的时候,这个对象就被销毁了。 一些更多的用法:

// with temporary read buffer
if (char buf[64]; std::fgets(buf, 64, stdin)) { m[0] += buf; }

// with lock
if (std::lock_guard<std::mutex> lock(mx); shared_flag) { unsafe_ping(); shared_flag = false; }

// with temporary input param
if (int s; int count = ReadBytesWithSignal(&s)) { publish(count); raise(s); }

structured-bingds

Grammar

attr(optional) cv-auto ref-operator(optional) [ indentifier-list ] = expression ; attr(optional) cv-auto ref-operator(optional) [ indentifier-list ] { expression }; attr(optional) cv-auto ref-operator(optional) [ indentifier-list ] ( expression ); 这里在绑定时候的基本规则是:(这里用 Expression 来表示 expression 表达式的类型)

  1. 如果 Expression 是数组类型,则一次绑定到数组元素
  2. 如果 Expression 是非联合体类型,且std::tuple_size<Expression>是完整类型,则使用类tuple绑定
  3. 如果 Expression 是非联合体类型,且std::tuple_size<Expression>不是完整类型,则以此绑定到类的公开数据成员

Case 1:Binding an array

每个 indentifier-list 中的标识符绑定到数组的每一个元素,标识符数量必须和数组大小一致。

int a[2] = {1,2};
 
auto [x,y] = a;
auto& [xr, yr] = a;

Case 2: Binding a tuple-like type

std::tuple_size<Expression>::value必须是一个合法的编译时期常量,并且标识符的数量和std::tuple_size<Expression>::value的值相等。 在 ref-operator&或者&&时: 对于每一个标识符,若其对应的初始化表达式是左值,则为左值引用;若为右值则为右值引用。 每个标识符对应的初始化表达式使用如下规则:

  • expression.get<i>(),表达式包含了一个如此的声明
  • get<i>(expression),仅按照 ADL1 规则查找对应的声明(在这种使用中,如果 expression 对象是一个左值,那么传入的参数也为左值;如果 expression 对象是一个右值,那么传入的对象也为右值)
float x{};
char  y{};
int   z{};
 
const auto& [a,b,c] = std::tuple<float&,char&&,int>(x,std::move(y),z);

Case 3: Binding to public data members

每个 Expression 的非静态公开成员变量都会被依次绑定,并且标识符个数要和非静态公开成员变量个数相等。 所以的非静态公开成员都应该是无歧义的,且不能有任何的匿名联合体成员。 标识符最后的类型的 CV限定符会合并其类成员变量的类型中的CV限定符和声明中的的CV限定符。

struct S {
    int x1 : 2;
    volatile double y1;
};
S f();
 
const auto [x, y] = f();

Thinking

structured-binding 带给我们在书写上方便的同时也带来了相应的更大的心智负担,它让我们不仅要关注一个变量的类型,我们还要关注它所指向的对象的类型。因为在这里创建的不是一个引用,也不是对象的拷贝,而是一个既存对象的别名。 比如下面这个例子:

BarBar foo(Bar bar) {
    // do_something
    return bar.bar;
}

如果我们如此明显的书写的话,我们都知道,返回一个 sub-object 是不能触发 RVO2 的。那么我们如果用了结构化绑定的方式之后呢?

BarBar foo(Bar bar) {
    auto [..., b, ...] = bar;
    // do_something
    return b;
}

很遗憾的是,这里依旧不能触发 RVO 的,因为这里的b是一个对象的别名,既不是引用也不是什么别的,它依旧会被认为是一个 sub-object。

if-init with structured-bindings

将 if-init 和 structured-bindings 可以帮助我们在很多地方缩减我们的代码:

if (auto [iter, inserted] = m.insert({"foo", "bar"}); inserted) {
    // do_something
} else {
    // do_other_things
}

if-constexpr

if-constexpr 可以帮助我们简化原本很多需要用 SFINAE 来实现的代码,用来模板中使用哪一部分的实现。

Sample 1

Before C++17

#include <type_traits>

template<typename T>
auto get_value_impl(T t, std::false_type) {
    return t;
}
template<typename T>
auto get_value_impl(T t, std::true_type) {
    return *t;
}
template<typename T>
auto get_value(T t) {
    return get_value_impl(t, std::is_pointer<T>());
}

After C++17

template <typename T>
auto get_value(T t) {
    if constexpr (std::is_pointer_v<T>)
        return *t;
    else
        return t; 
}

Sample 2

Before C++17

template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }

After C++17

template<int N>
constexpr int fibonacci()
{
    if constexpr (N>=2)
        return fibonacci<N-1>() + fibonacci<N-2>();
    else
        return N;
}

Summary

if-constexpr 的出现我感觉不是为了解决什么特别的问题,而是为了简化我们的代码,让我们在写的时候可以更自然,更符合直觉。

fold expression

Grammar

( pack op ... ) ( ... op pack ) ( pack op ... op init ) ( init op ... op pack ) 上面四个分别对应了一元右折叠、一元左折叠、二元右折叠、二元左折叠。

Explain

上面的四种折叠,分别会被展开成:

\text{一元右折叠:} E_1 \  \text{op}\ (\dots\ \text{op}\ (E_{N-1}\ \text{op}\ E_N))\\
\text{一元左折叠:} ((E_1\ \text{op}\ E_2)\ \text{op}\ \dots)\ \text{op}\ E_N)\\
\text{二元右折叠:} E_1 \  \text{op}\ (\dots\ \text{op}\ (E_{N-1}\ \text{op}\ (E_N\ \text{op}\ I)))\\
\text{二元左折叠:} (((I\ \text{op}\ E_1)\ \text{op}\ E_2)\ \text{op}\ \dots)\ \text{op}\ E_N)

在使用二元折叠的时候,注意两个运算符必须是一样的,并且 init 如果是一个表达式的话,优先级必须低于 op,如果一定要高于的话,可以用括号括起来。

Example

端序交换:

template<class T, std::size_t... N>
constexpr T bswap_impl(T i, std::index_sequence<N...>) {
  return (((i >> N*CHAR_BIT & std::uint8_t(-1)) << (sizeof(T)-1-N)*CHAR_BIT) | ...);
}
template<class T, class U = std::make_unsigned_t<T>>
constexpr U bswap(T i) {
  return bswap_impl<U>(i, std::make_index_sequence<sizeof(T)>{});
}

Thinking

折叠表达式是在参数包的展开上面的又一次进步和改进,弥补了原本的参数包展开不易计算的问题。

noexcept

noexcept 成为了类型系统的一部分,这也是C++17对以前代码的唯一影响,可能会导致以前的代码不能通过编译。 void f();void f() noexcept; 不再被认为是同一个类型,所以可能要为从前的实现提供额外的模板,或者提供额外的重载,再或者可以在模板中使用C++17中的新特性指定模板类型推导(template type deduction guide)。

template type deduction

为了实例化一个类模板,我们必须清楚的知道每个模板的类型,并且显示的写出他们,但是很多时候这是不必要的。

Thinking

这个新特性看起来似乎并没有那么吸引我:在类成员定义的时候,我没法使用到这个特性,可是这是我使用模板类最多的地方;在其他的很多地方,我似乎又可以使用auto来替代写出一个变量的类型来。


References:

  1. http://en.cppreference.com/w/cpp/language/if
  2. http://en.cppreference.com/w/cpp/language/structured_binding
  3. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0144r0.pdf
1

ADL: Argument-dependent lookup 2: RVO: Return Value Optimization

Const Reference of Pointer

问题起源: 在子类中实现一个模板父类的纯虚函数的时候,不能正确的通过编译。

template<typename T>
struct Fuck {
    virtual void shit(const T&) = 0;
}

shit函数接受一个常量引用,当我们使用一个指针类型(A*)来实例化这个模板类的时候,函数shit的类型就应该是:

void shit(const T&) = 0; <value T = A*>

当我尝试用下面这样的表示来实现这个函数的时候发生了编译错误:

struct FuckImpl : Fuck<A*> {
    void shit(const A*&) override;
}

这里正确的写法应该是:

struct FuckImpl : Fuck<A*> {
  void shit(A* const&) override;
};

这个问题大概由于const修饰符的结合性的问题,在前一种写法中const并没有修饰后面的引用,而是由于结合性的原因修饰了前面的指针。所以后一种写法中,const明确的修饰了后面引用。提供了正确的类型。


额外的吐槽:这里就要吐槽g++的报错了,我用clang编译的时候就给出了正确的表达式写法,只要抄上去就好了。2333

编译时期常量数组及常用操作

文中所有的代码均遵循C++11的标准并编译通过。

const_array 的实现

在 C++11 标准中的使用constexpr修饰的函数的要求比较严格,只允许在函数体内有一个return语句。那么在这样的限制下,很多的表达式就只能使用递归来完成。

#include <iostream>
#include <cstddef>

template<typename T>
using Invoke = typename T::type;

template<size_t...>
struct index_sequence {
  using type = index_sequence;
};

template<typename S1, typename S2>
struct _concat_sequence;
template<size_t... I1, size_t... I2>
struct _concat_sequence<index_sequence<I1...>, index_sequence<I2...>>
    : index_sequence<I1..., (sizeof...(I1) + I2)...> {};
template<typename S1, typename S2>
using concat_sequence = Invoke<_concat_sequence<S1, S2>>;

template<size_t Length>
struct _make_index_sequence;
template<size_t Length>
using make_index_sequence = Invoke<_make_index_sequence<Length>>;
template<size_t Length>
struct _make_index_sequence
    : concat_sequence<make_index_sequence<Length/2>, make_index_sequence<Length - Length / 2>> {};
template<>
struct _make_index_sequence<0> : index_sequence<> {};
template<>
struct _make_index_sequence<1> : index_sequence<0> {};
template<size_t offset, typename S>
struct _make_offset;
template<size_t offset, size_t... I>
struct _make_offset<offset, index_sequence<I...>> : index_sequence<(I + offset)...> {};
template<size_t offset, typename S>
using make_offset = Invoke<_make_offset<offset, S>>;

template<typename ValueType, size_t Size>
class const_array {
  ValueType data_[Size];
  template<size_t SZ1, size_t SZ2>
  constexpr const_array(const_array<ValueType, SZ1> first, ValueType second, const_array<ValueType, SZ2> third)
      : const_array(first, second, third, make_index_sequence<SZ1>(), make_index_sequence<SZ2>()) {}
  template<size_t... I1, size_t... I2>
  constexpr const_array(const_array<ValueType, sizeof...(I1)> first, ValueType second, const_array<ValueType, sizeof...(I2)> third, index_sequence<I1...>, index_sequence<I2...>)
      : data_{ first[I1]..., second, third[I2]... } {}
  template<size_t... I>
  constexpr const_array(const_array<ValueType, Size - 1> arr, ValueType value, index_sequence<I...>)
      : data_{ arr[I]..., value } {}
  constexpr const_array(const_array<ValueType, Size - 1> arr, ValueType value)
      : const_array(arr, value, make_index_sequence<Size - 1>()) {}
  template<size_t L1, size_t L2, size_t... I1, size_t... I2>
  constexpr const_array(const_array<ValueType, L1> arr1,
                        const_array<ValueType, L2> arr2,
                        index_sequence<I1...>,
                        index_sequence<I2...>)
      : data_{ arr1[I1]..., arr2[I2]... } {};
  template<size_t... I>
  constexpr const_array(ValueType (&arr)[Size], index_sequence<I...>)
      : data_{ arr[I]... } {}

  friend class const_array<ValueType, Size - 1>;
public:
  // construct const_array from only one element
  constexpr explicit const_array(ValueType value) : data_{ value } {}
  constexpr explicit const_array(ValueType (&arr)[Size])
      : const_array(arr, make_index_sequence<Size>()) {}

  template<size_t length, size_t... I>
  constexpr const_array(const_array<ValueType, length> rhs, index_sequence<I...>)
      : data_{ rhs[I]... } {}
  template<size_t L1, size_t L2>
  constexpr const_array(const_array<ValueType, L1> arr1, const_array<ValueType, L2> arr2)
      : const_array(arr1, arr2, make_index_sequence<L1>(), make_index_sequence<L2>()) {};

  template<size_t length, size_t st = 0>
  constexpr const_array<ValueType, length> sub_array() const {
    return const_array<ValueType, length>(*this, make_offset<st, make_index_sequence<length>>());
  }

  template<size_t i>
  constexpr const_array<ValueType, Size> set(ValueType value) const {
    return const_array<ValueType, Size>(
        sub_array<i>(), value, sub_array<Size - i - 1, i + 1>()
    );
  }
  template<size_t length>
  constexpr const_array<ValueType, Size + length> append(const_array<ValueType, length> rhs) const {
    return const_array<ValueType, Size + length>(*this, rhs);
  };

  constexpr const_array<ValueType, Size + 1> append(ValueType value) const {
    return const_array<ValueType, Size + 1>(*this, value);
  }
  constexpr ValueType operator[] (size_t i) const {
    return data_[i];
  }
  constexpr size_t size() const {
    return Size;
  }
};

在实现的过程中,借助了一个部分实现类。使用二分递归的方式实现了一个用于生成制定长度的数列的辅助类,避免了当 N 过大的时候递归过深的问题。

template<typename T>
using Invoke = typename T::type;

template<size_t...>
struct index_sequence {
  using type = index_sequence;
};

template<typename S1, typename S2>
struct _concat_sequence;
template<size_t... I1, size_t... I2>
struct _concat_sequence<index_sequence<I1...>, index_sequence<I2...>>
    : index_sequence<I1..., (sizeof...(I1) + I2)...> {};
template<typename S1, typename S2>
using concat_sequence = Invoke<_concat_sequence<S1, S2>>;

template<size_t Length>
struct _make_index_sequence;
template<size_t Length>
using make_index_sequence = Invoke<_make_index_sequence<Length>>;
template<size_t Length>
struct _make_index_sequence
    : concat_sequence<make_index_sequence<Length/2>, make_index_sequence<Length - Length / 2>> {};
template<>
struct _make_index_sequence<0> : index_sequence<> {};
template<>
struct _make_index_sequence<1> : index_sequence<0> {};
template<size_t offset, typename S>
struct _make_offset;
template<size_t offset, size_t... I>
struct _make_offset<offset, index_sequence<I...>> : index_sequence<(I + offset)...> {};
template<size_t offset, typename S>
using make_offset = Invoke<_make_offset<offset, S>>;

接下来就是借助上面的辅助类,来生成对应的数组下标帮助完成 const_array 的拷贝。我们并不能修改一个编译时期常量的类,所以这里有关于修改的操作都是通过返回一个新的对象来完成的,比如 appendset

使用智能指针的默认行为来避免内存泄漏

2016年的 cppcon 上,Herb Sutter 的演讲中提出了一些关于常用的数据结构如何使用智能指针自动的构造和析构来避免内存泄漏的情况发生。 可以在这里找到这个演讲的链接:https://youtu.be/JfmTagWcqoE

智能指针

unique_ptr

  1. 唯一所有权
  2. 离开作用域时,会同时析构指向的对象

shared_ptr

  1. 共享所有权
  2. 最后一个指向对象的 shared_ptr 被销毁时,析构指向的对象

weak_ptr

  1. 不表示所有权
  2. 使用之前需要先创建一个 shared_ptr(通过 wp.lock(),这个操作会延长指向对象的生命周期到这个临时的 shared_ptr 被销毁时)

所有权(Ownership)

在这里我借用了 Rust 中的一个概念:所有权(Ownership),也就是表示一个对象持有(HAS-A)另一个对象,被持有的对象的生命周期应该和其父对象的生命周期相同。通常,在 C++ 中,我们都会使用数据成员(data member)的方式去表示这样的关系。

class MyClass {
  Data data;
  /*...*/
};

在这用的使用情况下,如果我们需要一个更灵活一些的方案,可是同时也要具有这种持有的关系,这时候可以选择 unique_ptr,即有了如下方案:(这种方案也可以被称作 Decoupled HAS-A

class MyClass {
  unique_ptr<Data> pdata;
  /*...*/
};

常见使用场景

指向实现的指针(Pimpl Idiom)

很多时候我们会有需要将一些实现抽象出来到一个单独的类中,来实现接口和实现分离。在这样的场景下,我们对 pImpl 是不会有改变的,在这样的情况下,使用 const unique_ptr

template<class T>
using PImpl = const unique_ptr<T>;

class MyClass {
  class Impl;
  PImpl<Impl> pImpl;
  /*...*/
};

动态数组成员(Dynamic Array Member)

这里有两种方案,一种是使用 STL 里的 vector,另一种就是使用 unique_ptr。对于那些长度可能会变化的需求,我倾向于 unique_ptr<vector>;而对于长度偏固定的场景下,直接使用数组的指针我觉得会是一个较好的选择:

class MyClss {
  const unique_ptr<Data[]> array;
  int array_size;
  /*...*/
  MyClass (size_t num_data) :
    array(make_unique<Data[]>(num_data)) {}
}

树(Tree)

一个我们想象中常见的二叉树,在每个节点上保存了其子节点和要保存的数据。

在这样的结构里,我们可以发现父节点持有着它的两个子节点,而且每个子节点仅被其父节点持有,在这样的情况下,显然应该使用 unique_ptr

class Tree {
  struct Node {
    vector<unique_ptr<Node>> children;
    /*...*/
  };
  unique_ptr<Node> root;
  /*...*/
};

那如果每个节点上还保存了其父节点的信息呢,显然我们不能再使用一个 unique_ptr 来保存父节点的指针,因为这样就和 unique_ptr 的意义冲突了,并且会导致内存泄漏的情况。所以这里,就直接使用 raw pointer 去表示一个节点的父节点就可以了。

如果我们在程序的其他地方,需要一些额外的指针来指向树中节点所保存的信息,看起来和下图差不多:

在这种情况下,每个节点的所有权就不是唯一的,不再是它的父节点,可能是外部可能的任何一个对象,在这种情况下,就需要把使用的 unique_ptr 变成 shared_ptr。在这个基础上,我们可以方便的对外提供任意节点保存信息的指针(也是一个 shared_ptr)。

class Tree {
  struct Node {
    vector<shared_ptr<Node>> children;
    Data data;
  };
  shared_ptr<Node> root;
  shared_ptr<Data> find(/*...*/) {
    /*...*/
    return {spn, &(spn->data)};
  }
};

代码的倒数第三行中使用了 shared_ptraliasing constructor,提供了指向的内容的指针和用于管理这个指针的另一个 shared_ptr 对象。

双向链表(Doubly Linked List)

在一个双向链表中,我们用两个指针去表示前节点和后节点,在这样的情况下,我们会出现和上面树中相似的问题,在这种情况下,我们依旧可以使用 unique_ptr + raw pointer 的解决方案。

class LinkedList {
  struct Node {
    unique_ptr<Node> next;
    Node* prev;
    /*... data ...*/
  };
  unique_ptr<Node> root;
  /*...*/
};

有向无环图(DAG)

一个 DAG 和一棵树的区别是:在树中一个节点只能是另一个节点的子节点;而在 DAG 中,一个节点可以是多个节点的后继节点。在这样的基础下,我们把每个节点的 unique_ptr 改成 shared_ptr 就可以工作了。

class DAG {
  struct Node {
    vector<shared_ptr<Node>> children;
    vector<Node*> parents;
  /*… data …*/
  };
  vector<shared_ptr<Node>> roots;
};

环形链表(Circular List)

在环形链表中,我们不可避免的要处理一个节点被多个对象拥有的情况。但是,仔细考虑一下,这样的冲突只会发生在链表的头部,因为它会同时被最后一个节点和表示链表的头指针持有,那在这种情况下,我们可以选择断开最后一个节点和头节点的关系,即按照一个非环的单项链表存储,然后在最后一个节点的部分对其做特殊处理。

class CircularList {
  class Node {
    unique_ptr<Node> next;
    unique_ptr<Node>& head;
  public:
    auto get_next() { return next ? next.get(): head.get(); }
  };
  unique_ptr<Node> head;
};

Reference

  1. http://en.cppreference.com/w/cpp/memory/unique_ptr
  2. http://en.cppreference.com/w/cpp/memory/shared_ptr
  3. http://en.cppreference.com/w/cpp/memory/weak_ptr

Python元编程 - 在Python中实现重载

避免重复的代码,避免复制粘贴一些逻辑的时候,我们使用了函数。那么避免复制粘贴定义一些类似的,或者较为相像的类的时候,我们就需要一个生成类的方法,在Python中,我们使用的方法就是元类(MetaClass)。

元编程的应用(1)函数重载

在 Python 中,如果我们想要实现一个可以接受多种参数的函数,我们通常的方法都是在函数体里判断参数的个数,和各个的类型。这个办法很麻烦,并且也不容易维护,我也很希望可以像 C++ 一样可以简单的使用同样的名字去重载函数。利用元编程就可以做到。

我想做到像下面这样:

class Fuck:
	def shit(self, x: int, y: int):
    	pass
    def shit(self, p: str):
    	pass

fuck = Fuck()
fuck.shit(1, 2)
fuck.shit("f")

首先是一个用来存重复函数的类,负责把一个函数的签名提取出来,存到一个 dict 里,在被运行的时候,按照参数类型找到存好的重载。

import inspect, types
class MultiMethod:
   def __init__(self, name):
       self._methods = {}
       self.__name__ = name

   def insert_method(self, key, method):
       if key in self._methods:
           raise TypeError(
               "Can't insert arguments {}, already exists.".format(",".join([str(x) for x in key]))
           )
       self._methods[key] = method

   def register(self, method):
       sig = inspect.signature(method)

       arguments = []
       for name, parm in sig.parameters.items():
           if name == "self":
               continue
           if parm.annotation is inspect.Parameter.empty:
               raise TypeError(
                   "Argument {} must be annotated with a type.".format(name)
               )
           if not isinstance(parm.annotation, type):
               raise TypeError(
                   "Argument {} annotation must be a type.".format(name)
               )
           if parm.default is not inspect.Parameter.empty:
               self.insert_method(tuple(arguments), method)
           arguments.append(parm.annotation)
       self.insert_method(tuple(arguments), method)

   def __call__(self, *args):
       arguments = tuple(type(arg) for arg in args[1:])
       method = self._methods.get(arguments, None)
       if method:
           return method(*args)
       else:
           raise TypeError("No matching method for types {}".format(arguments))

   def __get__(self, instance, cls):
       if instance is not None:
           return types.MethodType(self, instance)
       else:
           return self

dict 类的子类,用于 __prepare__ 函数的返回值,在 __setitem__ 方法中进行实际的注册工作。

class MultiDict(dict):
    def __setitem__(self, key, value):
        if key in self:
            current_value = self[key]
            if isinstance(current_value, MultiMethod):
                current_value.register(value)
            else:
                mvalue = MultiMethod(key)
                mvalue.register(current_value)
                mvalue.register(value)
                super().__setitem__(key, mvalue)
        else:
            super().__setitem__(key, value)

最后是支持函数重载的元类。

class MultipleMeta(type):
    def __new__(cls, name, bases, clsdict):
        return type.__new__(cls, name, bases, clsdict)

    @classmethod
    def __prepare__(cls, name, bases):
        return MultiDict()

C++ 中的类型推导

auto 的基本使用

auto 关键字被在变量声明或者作为函数返回值的占位符,在这两个位置的使用是可以通过单个等号右边,或者函数调用来确定 auto 具体应该成为什么类型的,比如像下面这样:

auto iter = map.begin();
template<typename T, typename U>
auto func(T a, U b) -> decltype(a + b);

在 C++14 中,后面的 decltype 部分也可以被省略,可以通过返回的表达式来直接推导,比如这样:

template<typename T, typename U>
auto func(T a, U b) {
  return a + b;
}

for-range loop

还可以被用于在 for-range loop 中使用,作为循环变量类型的占位。

for-range loop 的展开

{
  auto&& __range = range_expression;
  for (auto __begin = begin_expr, __end = end_expr; __begin != __end; ++__begin) {
    range_declaration = *__begin;
    loop_statement;
  }
}

展开中的 begin_exprend_expr 都分别用 std::begin(you_container)std::end(you_container) 来得到其实和终止的迭代器。 在这两个函数的内部会分别调用 begin()end() 的成员函数来确定边界,边界应该是左闭右开的。

所以如果想要通过 for-range loop 来遍历自定义的数据结构的话,需要为这个数据结构提供 begin()end() 两个成员函数,并且提供一个迭代器类型, 迭代器类型需要可以拷贝,并且重载了 != 、前置 ++ 运算符和解引用(*)运算符。

auto 占位符的使用

for (auto x: m) {
  ...
}

这个占位符有四种写法:

for (auto x: m);
for (auto& x: m);
for (const auto& x: m);
for (auto&& x: m);

for (auto x: m)

这种写法情况,被遍历的每一个元素都会被拷贝一次,也就是说在 for 的代码块中使用的是被遍历元素的一个拷贝。 所以这里就有一个情况是不能使用的,就是如果被遍历元素的类型不能拷贝,那么就不能用,比如 std::unique_ptr

for (auto& x: m)

这样的写法大部分情况是没有问题的,元素不会被拷贝,而且可以在遍历的时候被修改。那么唯一会出问题的情况就是被遍历的对象是 vector<bool> 的时候。 vector<bool>vector<T> 的一个特化,使用了位去存储元素,所以在遍历的时候返回的是一个 bit reference 对象,这个对象是不能被非 const 的 左值引用中。所以在这种情况下,是不能用这种遍历方法的。

for (const auto& x: m)

const 的左值引用作为在 C++ 中的万能类型,可以接受这个类型的任何对象,除了元素不能修改之外,可以在大部分情况中使用。作为引用,也不会引起额外的拷贝开销。

for (auto&& x: m)

auto&& 可以被称为 Universal References,这里不是指它能兼容所有的引用类型,而是会因为引用折叠的原因可以根据 auto 推导出来的类型对实际类型做出改变。 所以如果在这里使用这种写法的话,就可以接受任意类型,并且可以修改其中的元素。

autodecltype 的推导

auto 的推导

不包含引用的推导:

auto a = 1; // auto -> int, a -> int
auto b = new auto(2); // auto int*, a -> int*

包含指针的推导:

int a = 1;
auto *b = &a; // auto -> int, b -> int*
auto c = &a; // auto - int*, c -> int*

包含引用的推导:

int a = 1;
auto& d = a; // auto -> int, d -> int&
auto e = a; // auto -> int, e -> int

// CV 限定会在 auto 的推导中被丢弃
const auto f = a; // auto -> int, f -> const int
auto g = f; // auto -> int, g -> int

// 如果 auto 被引用修饰,那么表达式的 CV 限定将会被保留
auto const &h = a; // auto -> int, h -> int const&
auto &i = h; // auto -> const int, i -> cosnt int&
auto *j = &h; // auto -> const int, j -> const int*

decltype 的推导

const std::vector<int> v;
auto a = v[0];// a -> int
decltype(v[0]) b = 0; // b -> const int&

int c = 0;
decltype(c) d; // d -> int
decltype((c)) e; // e -> int&

大概就是 decltype 会反映里面表达式的类型,不会去掉对应的CV限定符。


  • https://zh.wikipedia.org/wiki/C%2B%2B11#.E5.9E.8B.E5.88.A5.E6.8E.A8.E5.B0.8E
  • https://isocpp.org/blog/2012/11/universal-references-in-c11-scott-meyers

在 CLion 中配置 gtest

最近在学习 googletest 这个用于 C++ 的单元测试框架的时候,遇到了一个问题。就是希望可以在 CLion 中配置好一个制定项目的测试,然后由 CLion 运行并且给出一个结果。 结果当然是成功了的,这篇文章主要就记录一下整个配置的过程,配置过程整体很简单,主要就是写 CMakeLists.txt 的过程(因为 CLion 使用 CMakeLists 管理整个 C++ 的项目)。

项目目录结构

+ project_home
  + ext // external library
    + gtest // google test framework
	  - CMakeLists.txt
  + include // project headers
  + src // project source files
  + test // test files
  - CMakeLists.txt

这里假定我们把 gtest 放在 ext 这个目录下。我们不需要手动的从 github 上下载 gtest,CMake 可以替我们做到这个部分。具体的命令在后面会写到。 test 目录就是用于存放单元测试文件的地方,这部分的 cpp 文件是不需要写 main 的,在链接的时候,会把 main 函数链接上去。

ext/gtest/CMakeLists.txt

这部分的 CMakeLists.txt 会作为一个子文件夹在整个项目的 CMakeLists.txt 被使用。所以,这里是一个单独的 project。

cmake_minimum_required(VERSION 3.6)
project(gtest_builder)
include(ExternalProject)

set(GTEST_FORCE_SHARED_CRT ON)
set(GTEST_DISABLE_PTHREADS OFF)

ExternalProject_Add(googletest
    GIT_REPOSITORY https://github.com/google/googletest.git
    CMAKE_ARGS -DCMAKE_ARCHIVE_OUTPUT_DIRECTORY_DEBUG:PATH=DebugLibs
    -DCMAKE_ARCHIVE_OUTPUT_DIRECTORY_RELEASE:PATH=ReleaseLibs
    -DCMAKE_CXX_FLAGS=${MSVC_COMPILER_DEFS}
    -Dgtest_force_shared_crt=${GTEST_FORCE_SHARED_CRT}
    -Dgtest_disable_pthreads=${GTEST_DISABLE_PTHREADS}
    -DBUILD_GTEST=ON
    PREFIX "${CMAKE_CURRENT_BINARY_DIR}"
    # Disable install step
    INSTALL_COMMAND ""
    )

# Specify include dir
ExternalProject_Get_Property(googletest source_dir)
set(GTEST_INCLUDE_DIRS ${source_dir}/googletest/include PARENT_SCOPE)

# Specify MainTest's link libraries
ExternalProject_Get_Property(googletest binary_dir)
set(GTEST_LIBS_DIR ${binary_dir}/googlemock/gtest PARENT_SCOPE)

这里用到了 CMake 的一个模块 ExternalProject,文档在这里:传送门。 最后把下载好的 googletest 的头文件目录和编译好的链接库的目录返回给项目的 CMakeLists.txt。

CMakeLists.txt

cmake_minimum_required(VERSION 3.6)
set(PROJECT_NAME_STR gtest_usage)
project(${PROJECT_NAME_STR})

find_package(Threads REQUIRED)

add_definitions(-Wall -std=c++11 -Wno-deprecated -pthread)

set(COMMON_INCLUDES  ${PROJECT_SOURCE_DIR}/include)
set(EXT_PROJECTS_DIR ${PROJECT_SOURCE_DIR}/ext)

add_subdirectory(${EXT_PROJECTS_DIR}/gtest)

enable_testing()

set(PROJECT_TEST_NAME ${PROJECT_NAME_STR}_test)
include_directories(${GTEST_INCLUDE_DIRS} ${COMMON_INCLUDES})

file(GLOB TEST_SRC_FILES ${PROJECT_SOURCE_DIR}/test/*.cpp)
add_executable(${PROJECT_TEST_NAME} ${TEST_SRC_FILES})
add_dependencies(${PROJECT_TEST_NAME} googletest)

if(NOT WIN32 OR MINGW)
  target_link_libraries(${PROJECT_TEST_NAME}
      ${GTEST_LIBS_DIR}/libgtest.a
      ${GTEST_LIBS_DIR}/libgtest_main.a
      )
else()
  target_link_libraries(${PROJECT_TEST_NAME}
      debug ${GTEST_LIBS_DIR}/DebugLibs/${CMAKE_FIND_LIBRARY_PREFIXES}gtest${CMAKE_FIND_LIBRARY_SUFFIXES}
      optimized ${GTEST_LIBS_DIR}/ReleaseLibs/${CMAKE_FIND_LIBRARY_PREFIXES}gtest${CMAKE_FIND_LIBRARY_SUFFIXES}
      )
  target_link_libraries(${PROJECT_TEST_NAME}
      debug ${GTEST_LIBS_DIR}/DebugLibs/${CMAKE_FIND_LIBRARY_PREFIXES}gtest_main${CMAKE_FIND_LIBRARY_SUFFIXES}
      optimized ${GTEST_LIBS_DIR}/ReleaseLibs/${CMAKE_FIND_LIBRARY_PREFIXES}gtest_main${CMAKE_FIND_LIBRARY_SUFFIXES}
      )
endif()

target_link_libraries(${PROJECT_TEST_NAME} ${CMAKE_THREAD_LIBS_INIT})
add_test(test1 ${PROJECT_TEST_NAME})

这里的前面和配置一个正常的项目没什么不同的,都是配置头文件位置,配置链接库位置。唯一的区别是最后不是 add_executable 而是 add_test

到这里应给整个项目都配置好了,然后就可以在 CLion 的右上角找到。这样的部分:

CLion 可以识别出来这个是使用的 gtest 框架。然后就可以成功的运行啦!CLion 会在下面给出单元测试的报告,包括了每个 test case 的运行时间和结果。

快去试一试吧~


参考链接:

  • https://github.com/snikulov/google-test-examples
  • https://github.com/google/googletest

Two Ways Algorithm

Two Ways Algorithm 是一个用于字符串匹配的算法,算法类似 KMP 会返回所有 pattern 出现在 text 里的位置。但是和 KMP 不同的是 two ways algorithm 只使用常数大小的额外空间。

算法使用 \(O(m)\) 的时间预处理,并且可以在 \(O(n)\) 时间完成匹配,在最差的情况下会遍历 text 串两次。

算法细节

模式串 \(x\) 被分成两个部分,\(x_l\) 和 \(x_r\)。在匹配的过程中先从左向右匹配 \(x_r\),如果没有失配再从右向左匹配 \(x_l\)。

所以算法的关键就在于怎么找到一个合理的划分,把模式串划分成两个不相交的子串。

预处理部分

定义period of pattern \(x\),有整数 \(p\) 满足:\[x[i]=x[i+p]\] 换句话说,就是在模式串中任意两个相距为 period 的字符都相同。

所有满足上面条件的 \(p\) 中最小的一个,叫做这个串的 period,记做 \(p(x)\)。

定义:对于任意一个位置 \(l\)(这里指的是字母之间的位置,包括最开始和最后,所以一共有 \(m+1\) 个。)有整数 \(r\) 满足 \[x[i]=x[i+r],l-r+1\le i \le l\] 所有满足上面条件的 \(r\) 中最小的一个,叫做在位置 \(l\) 上的 local period,记做 \(r(x,l)\)。

这里显然可以知道的是,对于在所有位置上的 local period 都应该有:\(1 \le r(x,l) \le |x|\)

一个位置叫做 critical position 当且仅当 \[r(x,l)=p(x)\]

把这个串以这些 critical position 分开都是可以的。

匹配部分

。。。TODO。。

Rust Ownership System

Rust Ownership System

基于作用域和栈的内存管理是很符合直觉的,就像下面这样。

fn main() {
	let i = 5;
}

这里的变量 i 最后离开了作用域,然后内存被回收。

而在下面这个例子里,变量被析构了两次。

fn main() {
	let i = 5;
    foo(i);
}
fn foo(i: i64) {
	// do something...
}

第一次析构发生在 foo 结束的时候,第二次发生在 main 函数结束的时候。如果在 foo 中修改了这个变量的话,并不会影响到在 main 中的值。因为这里是的变量是被 拷贝 了一份,用于 foo 的。

在 Rust 中,使用了一套特别的基于 Ownership 的条件,除非一个类型被声明了具有Copy的特性。

Copy Trait

声明一个类型具有 Copy 标记,会在赋值或者作为函数调用参数的时候,使用 Copy ,而非 Move 的方式。

#[derive(Copy, Clone)]
struct Info {
	value: i64,
}

Ownership

Ownership rules 保证在任何的时间,对于一个非拷贝标记的对象,有且只有一个 owner 可以修改。

因此,当一个函数退出要清理变量的时候,可以保证在今后不会被访问,修改或者删除。

use std::io;
use std::fmt;

struct Fuck {
    shit: String,
}

impl Fuck {
    fn new (shit: &str) -> Fuck {
        println!("New... {}", shit);
        Fuck { shit: shit.to_string() }
    }
}

impl Drop for Fuck {
    fn drop(&mut self) {
        println!("Drop... {}", self.shit);
    }
}

impl fmt::Debug for Fuck {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "fuck shit:{:?}", self.shit)
    }
}

fn foo(fuck: Fuck) {
    println!("Call foo... {:?}", fuck);
}

对于一个简单的 main 函数:

fn main() {
	let mut a = Fuck::new("A");
}

结果是:

New... A
End Main...
Drop... A

对于这个复杂一点的版本:

fn main() {
    let mut a = Fuck::new("A");
    foo(a);
}

结果是:

New... A
Call foo... fuck shit:"A"
Drop... A
End Main...

会发现在函数 foo 结束的时候,对象就被回收了。这是因为这个对象的 owner 在函数调用这个过程中从 main 函数里的 a 变成了 foo 函数里的 fuck

当尝试在调用一次 foo 之后再调用一次 foo 的话,就会报错。

fn main() {
    let mut a = Fuck::new("A");
    foo(a);
    foo(a);
    println!("End Main...");
}
src/main.rs:34:9: 34:10 error: use of moved value: `a` [E0382]
src/main.rs:34     foo(a);
                       ^
src/main.rs:33:9: 33:10 note: value moved here
src/main.rs:33     foo(a);
                       ^

通过这样的编译时期的检查,保证了同一时间只有一个变量拥有这个对象。

Simple Rules

为了实现 没有垃圾回收机制的内存安全, 编译器不用去追踪每一个变量在代码中的使用,而是只要很简单的关注一个 作用域 就可以了。

其实可以总结成一个简单的规则:

  • 不被使用的返回值会被销毁。
  • 所有和变量绑定的对象在离开作用域的时候会被销毁,除非这个变量不再持有这个对象。

Reference and Borrowing

上面说了,当一个变量作为函数调用的参数或者赋值操作的右值的时候,这个变量会失去这个对象的所有权。就像这样:

fn main() {
    let mut a = Fuck::new("A");
    foo(a);
    println!("HAHA... {}", a.shit);
    println!("End Main...");
}
src/main.rs:34:28: 34:34 error: use of moved value: `a.shit` [E0382]
src/main.rs:34     println!("HAHA... {}", a.shit);
                                          ^~~~~~
src/main.rs:33:9: 33:10 note: value moved here
src/main.rs:33     foo(a);
                       ^

如果希望拿回变量的所有权,我们可以把对象作为返回值传回来。就像这样:

fn foo(fuck: Fuck) -> Fuck {
    println!("Call foo... {:?}", fuck);
    fuck
}

fn main() {
    let mut a = Fuck::new("A");
    a = foo(a);
    println!("HAHA... {}", a.shit);
    println!("End Main...");
}

但是不能每次都这么做啊,所以就有了 borrowreference

一个borrow的变量绑定最大的区别就是,它只是暂时的获得对象的所有权,会在离开作用域或者更换绑定的时候归还。

规则:

  • 一个引用的生命周期不能比它的拥有者还要长。
  • 你可以有多个引用,但是必须满足:1. 可以有多个引用(&T,不可变);2. 只能有一个可变的引用(&mut T)。

Lifetime

每一个变量都有它自己的生命周期,而生命周期的不同是 danging pointer 发生的主要原因。当你仍然持有一个对象的引用,而这个对象的拥有者的生命周期结束了,那么这个引用就无效了。

所以,Rust 中不会允许这样的事情发生。Rust 通过整个所有权系统的 生命周期(lifetime) 这一概念来实现这个需求。它明确的指出了每一个引用有效的作用域。

当我们定义了一个形参为引用的函数,就涉及到了引用的生命周期。

fn foo(x: &i32) {
}
fn foo2<'a>(x: &'a i32) {
}

上面的例子中第一个写法省略了引用 x 的生命周期的声明,第二个例子是声明生命周期的显式写法。

这里的写法有点类似于 C++ 中的模板函数,需要先在函数名后面的 <> 中提到所用的生命周期,才能在后面的形参列表或者返回值中用到它。

生命周期并不会改变变量的类型,所以 &i32&'a i32 拥有同样的类型。

同理,不光函数会涉及到生命周期,含有引用的结构体也会有生命周期的问题,显式声明的写法和函数类似。

struct Foo<'a> {
	x:&'a i32,
}

被省略了声明周期的函数会遵循着以下条件推导变量的生命周期:

  • 每一个被省略的函数参数成为一个不同的生命周期参数;
  • 如果刚好有一个生命周期,不管是否省略,这个生命周期都将成为被省略的返回值的生命周期;
  • 如果有多个生命周期,并且没有 &self 或者 &mut self 的时候,省略返回值的生命周期是不允许的,如果有 &self 或者 &mut self 的话,被省略的返回值的生命周期将是 self 的生命周期。

总结

OwnershipBorrowLifetime 三个部分共同构成了 Rust 的 Ownership System。成为了它保证零运行成本的内存安全的关键。这也成为了 Rust 陡峭学习曲线的一个很重要的部分。慢慢熟悉起来之后,会越来越顺手的。

Garbage Collection: Mark-Sweep

1.2 Automatic dynamic memory management

原则上,回收器最终都会将所有不可达对象回收。

  1. 追踪式回收 引入 垃圾 这一具有明确判定标准的概念,但它不一定包含所有不再使用的对象。
  2. 出于效率原因,某些对象可能不会被回收。

1.3 Comparing garbage collection algorithms

用什么来衡量各种垃圾回收算法的好坏呢:

  1. 安全性。在任何时候都不能回收活的对象。
  2. 吞吐量。**标记 / 构造率(mark / cons ratio)**来衡量,它表示回收器(对存活对象进行标记)与赋值器(创建或者构造新的链表单元)活跃度的比值。
  3. 完整性和及时性。完整性即所有的垃圾被回收的情况,及时性就是垃圾产生之后多久被回收。
  4. 停顿时间。在进行垃圾回收的时候中断赋值器线程的时间。【最小赋值器使用率(MMU)和界限赋值器使用率(BMU)的概念,去衡量停顿时间的分布。】
  5. 空间开销。
  6. 针对结构的特别优化。
  7. 可扩展性和可移植性。

2.1 The mark-sweep algorithm

  • 如果将标记位白存在对象中,那么mark方法处理的将是那些刚刚被标记的对象,因此这些对象可能还在缓存中。那么回收过程的高速缓存相关行文会影响到回收器的性能。
  • 标记-清扫回收器要求堆布局满足一定的条件:
  1. 标记-清扫回收器不会移动对象,因此内存管理器必须能够控制堆内存碎片,过多的内存碎片可能会导致分配器无法满足新分配请求,从而增加垃圾回收的频率,甚至于根本无法分配。
  2. 清扫器必须能够遍历堆中的每一个对象,不管是否存在一定用于对齐的字节,sweep方法必能够准确的找到下一个对象。
Mark-Sweep: Allocate
``` New(): ref <- allocate() if ref == null: collect() ref <- allocate() if ref == null: error "Out of memory." return ref atomic collect(): markFromRoots() sweep(HeapStart, HeapEnd) ```
Mark-Sweep: Mark
``` markFromRoots(): initialise(work_list) for each fld in Roots: ref <- *fld if ref != null and not isMarked(ref): setMarked(ref) add(work_list, ref) mark()

initialise(work_list): work_list <- empty

mark(): while not isEmpty(work_list): ref <- remove(work_list) for each fld in Pointers(ref): child <- *fld if child != null and not isMarked(child): setMarked(child) add(work_list, child)


<center>Mark-Sweep: Sweep</center>

sweep(start, end): scan <- start while scan < end: if isMarked(scan): unsetMarked(scan) else: free(scan) scan <- nextObject(scan)


#### 2.4 Bitmap marking
- 可以应用于保守式回收器(conservative collector)。
- 减少回收过程中的换页次数。

mark(): cur <- nextInBitmap() while cur < HeapEnd: add(work_list, cur) markStep(cur) cur <- nextBitmap()

markStep(start): while not isEmpty(work_list): ref <- remove(work_list) for each fld in Pointers(ref): child <- *fld if child != null and not isMarked(child): setMarked(child) if child < start: add(work_list, child)

#### 2.5 Lazy sweeping
<ul>
<li>优化清扫阶段高速缓存行为的一种方案是使用对象预取。回收器可以按照固定步幅对大小相同的对象进行清扫。</li>
<li>对象及其标志位存在两个特征:
<ol>
<li>一旦某个对象成为垃圾,它将一直都是垃圾,不可能再被赋值器访问或者复活。</li>
<li>赋值器永远不会访问对象的标记位。</li>
</ol>
</li>
</ul>


<center>Block structure heep: lazy sweeping</center>

atomic collect(): markFromRoots() for each block in Blocks: if not isMarked(block): add(blockAllocator, block) else: add(reclaimList, block) atomic allocate(sz): result <- remove(sz) if result == null: lazySweep(sz) result <- remove(sz) return result

lazySweep(sz): repeat block <- nextBlock(reclainmList, sz) if block != null: sweep(start(block), end(block)) if spaceFound(block): return until block == null allocSlow(sz)

allocSlow(sz): block <- allocateBlock() if block != null: initialise(block, sz)


#### 2.6 Cache misses in the marking loop

<center>mark procedure base on FIFO prefetch buffer</center>

add(work_list, item): markStack <- getStack(work_list) push(markStack, item)

remove(work_list): markStack <- getStack(work_list) addr <- pop(markStack) prefetch(addr) fifo <- getFifo(work_list) prepend(fifo, addr) return remove(fifo)

<center>Mark edge not node in object graph</center>

mark(): while not isEmpty(work_list): obj <- remove(work_list) if not isMarked(obj): setMarked(obj) for each fld in Pointers(obj): child <- *fld if child != null: add(work_list, child)