C++ 20 STL Cookbook

Preface

Abbreviated Function Template

注意这是 C++20 的新语法,可能有老版本支持应该是编译器私货。

auto add(auto a, auto b);
// replaced
template<typename T>
T add(T a, T b);

Why Use Braced Initilization

  1. 避免 implicit narrowing conversion
  2. using T{} to zero-initialize
     int x;        // unintialized
     int x = 0;    // zero (copy-initialized)
     int x {};     // zero (zero-initialized)
    

Chapter 1. New C++20 Features

std::format and String Formatting

到我写到这里的时候,gcc(12)和 clang(15)还是不支持 format。

format 库是抄 Python 3 的 str.format 的。于是有 {} 作为 placeholders,里面也可以加参数序号。

可以使用 <>^ 来进行对齐:

format("{:.<10}", ival); // 42........
format("{:.>10}", ival); // ........42
format("{:.^10}", ival); // ....42....

可以表示小数精度:

format("π: {:.5}", std::numbers::pi); // π: 3.1416

”{{” and “}}” prints single braces.

format 返回一个 std::string

设置 std::formatterFrac 类的特化版本,以使 std::format 支持 Frac 对象:

struct Frac {
    long n;
    long d;
};

template<>
struct std::formatter<Frac> {

    template<typename ParseContext>
    constexpr auto parse(ParseContext& ctx) {
        return ctx.begin();
    }

    template<typename FormatContext>
    auto format(const Frac& f, FormatContext& ctx) {
        return std::format_to(ctx.out(), "{}/{}", f.n, f.d);
    }

};

std::formatstd::make_format_argsstd::vformat 实现,可以自己造一个新的 print 函数:

template<typename... Args>
void print(const std::string_view fmt_str, Args&&... args) {
    auto fmt_args {std::make_format_args(args...)};
    auto outstr {std::vformat(fmt_str, fmt_args)};
    std::puts(outstr.c_str());
}

编译期 string 和 vector

vector 常量(?)可以作为 constexpr 返回。

constexpr std::vector<int> make_vector() {
    return {1, 2, 3, 4};
}

constexpr auto size {make_vector().size()};

string 同理:

constexpr string make_string() {
    return "abc";
}

constexpr auto s {make_string().length()};

Safely Compare Integers of Different Types

    int a {-3};
    unsigned b {7};

    if (a < b) {
        std::puts("YES");
    } else {
        std::puts("NO");
    }
    // output is "YES"
    // because a of `int` compares with b of `unsigned`,
    // the `int` one would be casted to `unsigned` implicitly,
    // and *negative* signed integer will be a large *postive* number

    if (std::cmp_less(a, b)) {
        std::puts("YES");
    } else {
        std::puts("NO");
    }
    // output is "YES"

Three-way Comparisons and Spaceship Operator

The spaceship operator will return a value equal to 0 if the operands are equal, negative if the left-hand operand is less than the right-hand operand, or positive if the left-hand operand is greater than the right-hand operator.

constexpr int a {2};
constexpr int b {3};
static_cast((a <=> b) < 0);
static_cast((b <=> a) > 0);

But it doesn’t return an integer, it’s a kind of objects can implicit casting to integers.

If operands are integers, will return std::strong_ordering,and the categories of this kind of object are:

  1. strong_ordering::equal // operands are equal
  2. strong_ordering::less // lhs is less than rhs
  3. strong_ordering::greater // lhs is greater than rhs

And if operands are floating-points numbers, will return partial_ordering object:

  1. partial_ordering::equivalent // operands are equivelant
  2. partial_ordering::less // lhs is less than rhs
  3. partial_ordering::greater // lhs is greater than rhs
  4. partial_ordering::unordered // if an operand is unordered

Three-way comparisons are more precise than conventional comparsions.

to Use the Default operator<=>

struct Num {
    int n;
    constexpr Num() : n{} {}
    constexpr Num(int n) : n{n} {}
    auto operator<=>(const Num& rhs) const = default;
};

The default <=> operator is constexpr safe.

?: Nowadays 42 > a may be syntax sugar to 42 <=> a < 0, maybe.

to Overload operator<=> by Yourself

struct Frac {
    long n, d;
    constexpr Frac(long n, long d) : n{n}, d{d} {}
    constexpr double db1() const {
        return static_cast<double>(n) / static_cast<double>(d);
    }
    constexpr auto operator<=>(const Frac& rhs) const {
        return this->db1() <=> rhs.db1();
    } 
    constexpr bool operator==(const Frac& rhs) const {
        return this->db1() == rhs.db1();
    }
};

int main()
{
    constexpr Frac f1 {5, 3};
    constexpr Frac f2 {10, 6};
    constexpr Frac f3 {5, 4};

    static_assert(f1 == f2);
    static_assert(f1 > f3);
    static_assert(f3 <= f1);
    static_assert(f2 != f3);

    return 0;
}

注意到这里其实 6 个比较运算符都可以使用了。上面说是语法糖应该是没什么问题的。

version 库

本来 version 就可以获取支持某一个语言特性的具体版本,大概?这些宏以 __cpp_ 开头,比如:__cpp_lib_three_way_comparison,想 include compare 只需要判断这个宏是否存在即可:

#include <version>
#ifdef __cpp_lib_three_way_comparison
# include <compare>
#else
# error Spaceship has not yet landed
#endif

现在可以使用新语法:

#if __has_include(<compare>)
# include <compare>
#else
# error Spaceship has not yet landed
#endif

__has_include 是 C++17 引入的语法。

Concepts and Constraints

引入 requires 为模板参数提供约束。该约束可以由 type trait 提供:

template<typename T>
requires std::is_integral_v<T>
T add(const T& r) {
    return 42 + r;
}

可以使用逻辑运算符构造复合的 concept:

template<typename T>
concept Number = std::integral<T> || std::floating_point<T>;

template<typename T>
requires Number<T>
T add(const T& r) {
    return 42 + r;
}

或者有:

template<typename T>
constexpr bool is_gt_byte {sizeof(T) > 1};

template<typename T>
concept Number = is_gt_byte<T> && (std::integral<T> || std::floating_point<T>);

单参数的约束可以直接取代 typename 的位置:

template<Number T>
T add(const T& r) {
    return 42 + r;
}

More Concept Syntax

  1. 普通
     template<typename T>
     requires Number<T>
     T add(const T& r) {
         return 42 + r;
     }
    
  2. 还是很普通
     template<Number T>
     T add(const T& r) {
         return 42 + r;
     }
    
  3. requires in function signature
     template<typename T>
     T add(const T& r) requires Number<T> {
         return 42 + r;
     }
    
  4. auto 大法,奇怪的语法。混合 abbreviated function template 语法。
     auto add(Number auto& r) {
         return 42 + r;
     }
    

Terms

标准中使用这些词汇来表示约束的构造运算:&& 是 constraint conjunction(约束交),|| 是 constraint disjunction(约束并),! 是一个 atomic constraint(原子约束)。

Avoid Re-compiling Template Libraries with Modules

因为标准库在逐渐变大,而且模板的代码要写进头文件,于是对模板库的 re-compile 产生的负担越来越重。

虽然说我们可以使用 include guard 来保护不让 function prototypes 或模板本身重定义,但是不能避免多个库对同一个库中某一个模板实例化而导致的多个模板实例化出的函数间的冲突。这也是日益健壮的 STL 迟早会暴露出的隐患。

所以引入 modules、import、export 的语法来解决这种问题。

创建文件 bw_math.ixxixx 后缀是 Visual Studio 规定的模块扩展名,目前只有 MSVC 有不完全的标准库 module 实现,其它编译器是完全不支持:

export module bw_math;

export template<typename T>
T add(T lhs, T rhs) {
    return lhs + rhs;
}

到 cpp 文件中可以 import 使用:

import bw_math;
import std.core;

int main()
{
    std::cout << std::format("add: {}", add<std::string>("a", "b")) << std::endl;
}

可见其实上面出现的两个特性目前都只有 MSVC 支持……

export 和 import 的部分很像 Rust,在这里就不赘述了,奇怪的语法。

Views and Ranges

<ranges> 库使用 std::rangesstd::ranges::view 这两个名称空间。这里说到 to save the fingers!,还是用下 namespace aliases 比较好。

用法

  1. view 应用到 range:

     #include <iostream>
     #include <ranges>
     #include <vector>
     namespace ranges = std::ranges;
     namespace views = ranges::views;
    
     int main()
     {
         const std::vector nums {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
         auto result = ranges::take_view(nums, 5);
         for (auto v : result)
             std::cout << v << ' ';
         return 0;
     }
    

    这里的代码使用 g++ 编译,clang++ 的 ranges 库的实现好像不太一样。

    take_view 取前 n 个元素。

    也可以使用 take_view 对应的 view adapter:

     auto result = nums | views::take(5);
    

    A view adapter takes the range operand from the left-hand side of the | operator(maybe named “pipe”?), and is evaluated left-to-right.

  2. 因为 view adapter 也是可迭代的,所以它也满足作为一个 range 使用:

     auto result = nums | views::take(5) | reverse;
    
  3. filter view

     for (auto v : nums | views::filter([](int i) { return i % 2 == 0; })) {
         std::cout << v << ' ';
     }
     // 
    
  4. transform view

     for (auto v : nums | views::transform([](int i) { return i * i; })) {
         std::cout << v << ' ';
     }
     // 1 4 9 16 25 36 49 64 81 100
    
  5. range factories

    比如 views::iota

     auto rnums = views::iota(1, 10);
     auto rnums = views::iota(1) | views::take(200);
    

达到 range 的基本要求 iff 对象至少有 begin()end() 迭代器,其中 end() 作为一个 sentinel。

有关 algorithms

比如 std::sort

  1. std::sort(v.begin(), v.end());
    

    现在可以写成:

    ranges::sort(v);
    
  2. std::sort(v.begin() + 5, v.end());
    

    可以写成:

    ranges::sort(ranges::drop_view(v, 5));
    
  3. std::sort(v.rbegin() + 5, v.rend());
    

    可以写成

    ranges::sort(v | views::reverse | views::drop(5))
    

关于 ranges::xxxx_viewview::xxxx

测试了一下:

views::take(v, 5);         // pass
ranges::take_view(v, 5);   // pass
v | views::take(v);        // pass
v | ranges::take_view(5);  // dame!!

所以都用 views 下的 view adapters 就好了。

Chapter 2. General STL Features

Span

std::span 是 C++20 引入的,一个简单在连续序列上创建 view 的 wrapper。

用法

C 风格数组传参会损失大小信息:

void parray(int* a);

所以可以使用 std::span wrap 一层:

#include <iostream>
#include <span>

template<typename T>
void pspan(std::span<T> s) {
    std::cout << "number of elements: " << s.size() << std::endl;
    std::cout << "size of span: " << s.size_bytes() << std::endl;
    for (auto e : s)
        std::cout << e << ' ';
    endl(std::cout);
}

int main()
{
    int carray[] {1, 2, 3, 4, 5};
    pspan<int>(carray);  // can't deduce
    return 0;
}

实现

template<typename T, size_t Extent = std::dynamic_extent>
class span {
    T * data;
    size_t count;
public:
    ...
};

Extent 在编译期自动推断,默认是 dynamic_extent 是为了适配 vector 这样的不定长容器。

Structured Binding

C++17 引入的语法。我平时主要用来 bind std::pair 类型的返回值。

新用法

C++20 开始,除了 std::pairstd::tuplestd::arraystruct,现在也可以绑定 C 风格数组了。

其它用法没有区别。

Initialize Variables Within if and switch Statements

这是 C++17 的语法,没有新内容,但是例子很有趣:

  1. 一个互斥锁的例子:

     if (lock_guard<mutex> lg{ my_mutex }; condition) {
         // interesting things happen here
     }
    
  2. 操作 SQLite 的例子:

     if (
         sqlite3_stmt** stmt,
         auto rc = sqlite3_prepare_v2(db, sql, -1, &_stmt,
             nullptr);
         !rc) {
             // do SQL things
     } else {     // handle the error
         // use the error code
         return 0;
     }
    

嗯,看起来挺扯的,if 写成这样。

Class Template Argument Deduction

C++17 引入的语法。有下面的例子:

#include <iostream>

template<typename T>
class Sum {
    T v{};
public:
    template<typename... Ts>
    Sum(Ts&&... values) : v{ (values + ...) } {}
    const T& value() const { return v; }
};

int main()
{
    Sum s {1u, 2.0, 3, 4.0f};
    return 0;
}

这个参数是推不出来的:

deduction.cc: In function ‘int main()’:
deduction.cc:14:29: error: class template argument deduction failed:
   14 |     Sum s {1u, 2.0, 3, 4.0f};

但是可以使用 template deduction guide 修复这个问题:

#include <iostream>

template <typename T>
class Sum {
    T v{};
public:
    template<typename... Ts>
    Sum(Ts&&... values) : v{ (values + ...) } {}
    const T& value() const { return v; }
};

template<typename... Ts>
Sum(Ts&&... values) -> Sum<std::common_type_t<Ts...>>;

int main()
{
    Sum s {1u, 2.0, 3, 4.0f};
    return 0;
}

Chapter 3. STL Containers

总览一下现代 C++ 的所有容器类型:

Uniform Erasure Function

std::erase 现在可以直接作用于 4 种序列型容器(当然不包括 std::array)。注意,这个新版的 std::erasestd:erase_if 在它们对应的容器头文件中定义。

并且,最重要的是,它是真正的 remove。

Insert Elements into a Map

C++17 引入的 map::try_emplace 在 emplace 的基本上加了仓检(?),返回 std::pair<iterator, bool> 用于指示插入位置和是否成功。

Modify the Keys of Map Items

map<int, string> mymap { ... };
auto it = mymay.begin();
it->first = 42;

这个代码是无法正确编译的。

这时可以使用 C++17 引入的 extractextract 返回一个特殊的 node_type 对象。Node handler 没有规定具体的实现,但是需要提供一些必要的成员函数,如 emptykeymapped 等等。下面是使用 extract 交换 keys 的例子:

#include <iostream>
#include <map>
#include <string>

template<typename Map, typename Key>
bool swap_key(Map& m, const Key& k1, const Key& k2) {
    auto n1 { m.extract(k1) };
    auto n2 { m.extract(k2) };
    if (!n1 || !n2) return false;
    std::swap(n1.key(), n2.key());
    m.insert(std::move(n1));
    m.insert(std::move(n2));
    return true;
}

template<typename Map>
void printm(const Map& m) {
    std::cout << "Rank: " << std::endl;
    for (const auto& [k, v] : m) {
        std::cout << k << ": " << v << std::endl;
    }
}

int main()
{

    std::map<int, std::string> m {
        {1, "Mario"}, {2, "Luigi"}, {3, "Bowser"}, 
        {4, "Peach"}, {5, "Donkey Kong Jr"}
    };
    printm(m);
    swap_key(m, 3, 5);
    printm(m);

    return 0;
}

cppref 上是这样描述 extract 的:
If the container has an element with key equivalent to k, unlinks the node that contains that element from the container and returns a node handle that owns it. Otherwise, returns an empty node handle.
In either case, no elements are copied or moved, only the internal pointers of the container nodes are repointed.

只是移交所有权(怪怪?)。

Cookbook 上说:The extract function disassociates the node while leaving it in place, and returns a node_handle object.

这里的 disassociate 就是 unlink 的意思。

对于 multiset 来说,extract 也只能作用于一组 k-v pair。

并且 insert 是对应了新增了接收 node_type 的版本的,这个 overload 的返回值是新引入的 insert_return_type 对象,定义为:

template<class Iter, class NodeType>
struct /*unspecified*/
{
    Iter     position;
    bool     inserted;
    NodeType node;
};

可以使用 .inserted 判断是否 insert 成功(当有 duplicated key 的时候就不成功)。

Use unordered_map with Custom Keys

unordered_map 依赖于 std::hash<Key>std::equal_to<Key>,所以应该提供 operator== 重载和 std::hash<Key> 版本的特化:

#include <unordered_map>
#include <iostream>

struct Coord {
    int x {};
    int y {};
};

bool operator==(const Coord& lhs, const Coord& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y;
}

namespace std {
template<>
struct hash<Coord> {
    std::size_t operator()(const Coord& c) const {
        return static_cast<size_t>(c.x) + static_cast<size_t>(c.y);
    }
};
}

using Coordmap = std::unordered_map<Coord, int>;

void print_cm(Coordmap& cm) {
    for (const auto& [key, value] : cm) {
        std::cout << "{(" << key.x << ", " << key.y << "), " << value << "} ";
    }
    endl(std::cout);
}

int main()
{
    Coordmap m {
        { {0, 0}, 1 },
        { {0, 1}, 2 },
        { {2, 1}, 3 }
    };

    print_cm(m);

    return 0;
}

Input Iterators

经典例子。

#include <iostream>
#include <iterator>
#include <string>
#include <algorithm>
#include <set>

using input_it = std::istream_iterator<std::string>;

int main()
{
    std::set<std::string> words;
    input_it it { std::cin };
    input_it end {};
    std::copy(it, end, std::inserter(words, words.end()));

    for (const std::string& w : words) {
        std::cout << w << ' ';
    }
    endl(std::cout);

    return 0;
}

逆波兰表达式求值器

#include <cctype>
#include <deque>
#include <limits>
#include <sstream>
#include <utility>
#include <functional>
#include <map>
#include <cmath>
#include <iostream>

bool is_numeric(const std::string& s) {
    for (const char c : s) {
        if (c != '.' && !std::isdigit(c)) return false;
    }
    return true;
}

class RPN {
    std::deque<double> deq_ {};
    constexpr static double zero_ { 0.0 };
    constexpr static double inf_ { std::numeric_limits<double>::infinity() };
public:
    double op(const std::string& s) {
        if (::is_numeric(s)) {
            auto v { std::stod(s, nullptr) };
            deq_.push_front(v);
            return v;
        }
        else return optor(s);
    }

    void clear() {
        deq_.clear();
    }

    std::string get_stack_string() const {
        std::stringstream ss;
        for (auto v : deq_) {
            ss << v << ' ';
        }
        return ss.str();
    }

    std::pair<double, double> pop_get2() {
        if (deq_.size() < 2) return {zero_, zero_};
        auto v1 { deq_.front() };
        deq_.pop_front();
        auto v2 { deq_.front() };
        deq_.pop_front();
        return {v2, v1};
    }

    double optor(const std::string& op) {
        static std::map<std::string, std::function<double(double, double)>> opmap {
            {"+", [](double l, double r) { return l + r; }},
            {"-", [](double l, double r) { return l - r; }},
            {"*", [](double l, double r) { return l * r; }},
            {"/", [](double l, double r) { return l / r; }},
            {"^", [](double l, double r) { return std::pow(l, r); }},
            {"%", [](double l, double r) { return std::fmod(l, r); }},
        };
        if (!opmap.contains(op)) return zero_;
        auto [l, r] = pop_get2();
        if (op == "/" && r == zero_) deq_.push_front(inf_);
        else deq_.push_front(opmap.at(op)(l, r));
        return deq_.front();
    }
};

int main()
{
    RPN rpn;

    for (std::string o {}; std::cin >> o; ) {
        rpn.op(o);
        auto stack_str { rpn.get_stack_string() };
        std::cout << o << ": " << stack_str << std::endl;
    }

    return 0;
}

简单 Word Counter

#include <regex>
#include <ranges>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <utility>
#include <iostream>

namespace ranges = std::ranges;
namespace regex_constants = std::regex_constants;

namespace bw {
constexpr const char* re {"(\\w+)"};
}

int main()
{
    std::map<std::string, int> wordmap {};
    std::vector<std::pair<std::string, int>> wordvec {};
    std::regex word_re(bw::re);
    std::size_t total_words {};

    for (std::string s {}; std::cin >> s; ) {
        auto words_begin { std::sregex_iterator(s.begin(), s.end(), word_re) };
        auto words_end { std::sregex_iterator() };

        for (auto r_it { words_begin }; r_it != words_end; ++r_it) {
            std::smatch match { *r_it };
            auto word_str { match.str() };
            ranges::transform(word_str, word_str.begin(), [](unsigned char c) { return std::tolower(c); });
            auto [map_it, result] = wordmap.try_emplace(word_str, 0);
            auto& [w, count] = *map_it;
            ++total_words;
            ++count;
        }
    }

    auto unique_words = wordmap.size();
    wordvec.reserve(unique_words);
    ranges::move(wordmap, back_inserter(wordvec));
    ranges::sort(wordvec, [](const auto& a, const auto& b) {
        if (a.second != b.second) {
            return a.second > b.second;
        }
        return a.first < b.first;
    });

    std::cout << "total word count: " << total_words << std::endl;
    std::cout << "unique word count: " << unique_words << std::endl;

    for (int limit {20}; auto& [w, count] : wordvec) {
        std::cout << count << ", " << w << std::endl;
        if (--limit == 0) break;
    }

    return 0;
}

Chapter 4. Compatible Iterators

std::begin()std::end() 能兼容 primitive arrays,而且 range-based for 调用的是这对函数,而且 begin()end() 只是一些容器的成员函数。推荐用前者,但是我跟这个书的作者一样 favor 后者。

Which are Fundamental

The Hierarchical Iterator Categories

更上面的是更基类,括号中的是 capability:

上面的所有 iterators 类型都是 mutable iterators。

还有一种与 Input Iterator 对应的 Output Iterator,可以 write & increment once。

Iterator Concepts

从 C++20 开始 STL 开始使用 concepts 定义 iterators 以取代原来的 categories。下面的这些 concepts 都包含在 std:: 名称空间中:

举个例子:

#include <iostream>
#include <iterator>
#include <list>

template<std::random_access_iterator T>
void printc(const T& c) {
    for (auto e : c) {
        std::cout << e << ' ';
    }
    endl(std::cout);
    std::cout << "element 0: " << c[0] << std::endl;
}

int main()
{
    std::list<int> c {1, 2, 3, 4, 5};
    printc(c);
    return 0;
}

报错:

iterator_concepts.cc: In function ‘int main()’:
iterator_concepts.cc:17:11: error: no matching function for call to ‘printc(std::__cxx11::list<int>&)’
   17 |     printc(c);
      |     ~~~~~~^~~
iterator_concepts.cc:6:6: note: candidate: ‘template<class T>  requires  random_access_iterator<T> void printc(const T&)’
    6 | void printc(const T& c) {
      |      ^~~~~~
...
/usr/include/c++/12/bits/iterator_concepts.h:615:33: note: the required expression ‘* __i’ is invalid
  615 |       = requires(_Iter __i) { { *__i } -> __detail::__can_reference; }
      |                                 ^~~~

Create a Iterable Range

下面的方法能最小化支持 range-based for:

#include <iostream>

template<typename T>
class Seq {
    T start_ {};
    T end_ {};
public:
    Seq(T start, T end) : start_{start}, end_{end} {}
    class iterator {
        T value_ {};
    public:
        explicit iterator(T position = 0) : value_{position} {}
        T operator*() const { return value_; }
        iterator& operator++() {
            ++value_;
            return *this;
        }
        bool operator!=(const iterator& rhs) const {
            return value_ != rhs.value_;
        }
    };

    iterator begin() const {
        return iterator{start_};
    }
    iterator end() const {
        return iterator{end_};
    }
};

int main()
{
    Seq<int> r {100, 110};
    for (auto v : r) {
        std::cout << v << ' ';
    }
    endl(std::cout);
    return 0;
}

需求

满足 range-based for 使用的最小化要求是:

Make Your Iterators Compatible with STL Iterator Traits

上面的 Seq 类还不支持 STl 的 algorithms,使用了会报错。这里出现了一句描述:

The error messages are vague, cryptic, and cascading.

首先需要添加 operator== 的支持:

bool operator==(const iterator& rhs) const {
    return value_ == rhs.value_;
}

我测试到这里 g++ 已经可以编译通过了。

再需要添加 iterator_traits 类,这是一个 type definitions 的集合。说是一个类,其实是直接添加在 iterator 类中的:

public:
    using iterator_concept  = std::forward_iterator_tag;
    using iterator_category = std::forward_iterator_tag;
    using value_type        = std::remove_cv_t<T>;
    using difference_type   = std::ptrdiff_t;
    using pointer           = const T*;
    using reference         = const T&;

Create a Generator as Iterators

#include <string_view>
#include <iostream>
#include <ranges>
#include <cstddef>
#include <type_traits>

void printc(const auto& v, const std::string_view s = "") {
    if (s.size()) std::cout << s << ": ";
    for (auto e : v) std::cout << e << ' ';
    endl(std::cout);
}

class fib_generator {
    using fib_t = unsigned long;
    fib_t stop_ {};
    fib_t count_ {};
    fib_t a_ {0};
    fib_t b_ {1};

    constexpr void do_fib() {
        const fib_t old_b = b_;
        b_ += a_;
        a_ = old_b;
    }

public:
    // to make the generator work with the algorithm library (include C++20 range versions)
    using iterator_concept  = std::forward_iterator_tag;
    using iterator_category = std::forward_iterator_tag;
    using value_type        = std::remove_cv_t<fib_t>;
    using difference_type   = std::ptrdiff_t;
    using pointer           = const fib_t*;
    using reference         = const fib_t&;

public:
    explicit fib_generator(fib_t stop = 0) : stop_{stop} {}

    fib_t operator*() const {
        return b_;
    }
    constexpr fib_generator& operator++() {
        do_fib();
        ++count_;
        return *this;
    }
    fib_generator operator++(int) {
        auto temp {*this};
        ++*this;
        return temp;
    }
    bool operator!=(const fib_generator& rhs) const {
        return count_ != rhs.count_;
    }
    bool operator==(const fib_generator& rhs) const {
        return !this->operator!=(rhs);
    }
    const fib_generator& begin() const { return *this; }
    const fib_generator end() const {
        auto sentinel = fib_generator();
        sentinel.count_ = stop_;
        return sentinel;
    }
    fib_t size() { return stop_; }
};

int main()
{
    printc(fib_generator(10) | std::ranges::views::transform([](const auto a) { return a * a; }));
    return 0;
}

Example for Iterating C-string

#include <iostream>

class cstr_itr {
    using sentinel_t = const char;
    constexpr static sentinel_t nullchar = '\0';
    const char* s_ {};
public:
    explicit cstr_itr(const char* str) : s_{str} {}
    char operator*() const { return *s_; }
    cstr_itr& operator++() {
        ++s_;
        return *this;
    }
    bool operator!=(sentinel_t) const {
        return s_ != nullptr && *s_ != nullchar;
    }
    cstr_itr begin() const { return *this; }
    sentinel_t end() const { return nullchar; }
};

void print_cstr(const char* s) {
    std::cout << s << ": ";
    for (char c : cstr_itr(s)) {
        std::printf("%02x ", c);
    }
    endl(std::cout);
}

int main()
{
    const char carray[] {"array"};
    print_cstr(carray);

    const char* cstr {"c-string"};
    print_cstr(cstr);

    return 0;
}

Build a Zip Iterator Adapter

#include <iostream>
#include <vector>
#include <string>

template<typename T>
class zip_iterator {
    using val_t = typename T::value_type;
    using ret_t = std::pair<val_t, val_t>;
    using it_t  = typename T::iterator;

    it_t ita_ {};
    it_t itb_ {};
    it_t ita_begin_ {};
    it_t itb_begin_ {};
    it_t ita_end_ {};
    it_t itb_end_ {};
    zip_iterator(it_t ita, it_t itb) : ita_{ita}, itb_{itb} {}

public:
    using iterator_concept  = std::forward_iterator_tag;
    using iterator_category = std::forward_iterator_tag;
    using value_type        = std::pair<val_t, val_t>;
    using difference_type   = long int;
    using pointer           = const val_t*;
    using reference         = const val_t&;

    zip_iterator(T& a, T& b) : ita_{a.begin()}, itb_{b.begin()}, ita_begin_{ita_},
            itb_begin_{itb_}, ita_end_{a.end()}, itb_end_{b.end()} {}

    zip_iterator& operator++() {
        ++ita_;
        ++itb_;
        return *this;
    }
    bool operator==(const zip_iterator& o) const {
        return ita_ == o.ita_ || itb_ == o.itb_;
    }
    bool operator!=(const zip_iterator& o) const {
        return !operator==(o);
    }
    ret_t operator*() const {
        return { *ita_, *itb_ };
    }

    zip_iterator begin() const {
        return zip_iterator(ita_begin_, itb_begin_);
    }
    zip_iterator end() const {
        return zip_iterator(ita_end_, itb_end_);
    }
};

int main()
{
    std::vector<std::string> vec_a {"Bob", "John", "Joni"};
    std::vector<std::string> vec_b {"Dylan", "Williams", "Mitchell"};

    std::cout << "zipped: ";
    for (const auto& [a, b] : zip_iterator(vec_a, vec_b)) {
        std::cout << '[' << a << ", " << b << ']' << ' ';
    }
    endl(std::cout);

    return 0;
}

Create a Random-access Iterator

#include <memory>
#include <cstddef>
#include <initializer_list>
#include <stdexcept>
#include <iostream>
#include <ranges>

template<typename T>
class Container {
    std::unique_ptr<T[]> c_ {};
    std::size_t n_elements_ {};
    class iterator {
        T* ptr_;
    public:
        using iterator_concept  = std::contiguous_iterator_tag;
        using iterator_category = std::contiguous_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;

        iterator(T* ptr = nullptr) : ptr_{ptr} {}
        const auto operator<=>(const iterator& rhs) const {
            return ptr_ <=> rhs.ptr_;
        }
        const bool operator==(const iterator& rhs) const {
            return ptr_ == rhs.ptr_;
        }
        T& operator*() const {
            return *ptr_;
        }
        iterator operator+(const std::size_t n) const {
            return iterator(ptr_ + n);
        }
        friend const iterator operator+(const std::size_t n, const iterator& rhs) {
            return iterator(rhs.ptr_ + n);
        }
        const iterator operator-(const size_t n) {
            return iterator(ptr_ - n);
        }
        const std::size_t operator-(const iterator& rhs) {
            return ptr_ - rhs.ptr_;
        }
        iterator& operator++() {
            ++ptr_;
            return *this;
        }
        iterator operator++(int) {
            auto ret = *this;
            ++ptr_;
            return ret;
        }
        iterator& operator--() {
            --ptr_;
            return *this;
        }
        iterator operator--(int) {
            auto ret = *this;
            --ptr_;
            return ret;
        }
    };

public:
    Container(std::initializer_list<T> l) : n_elements_{l.size()} {
        c_ = std::make_unique<T[]>(n_elements_);
        std::size_t index {};
        for (T e : l) {
            c_[index++] = e;
        }
    }
    Container(std::size_t sz) : n_elements_{sz} {
        c_ = std::make_unique<T[]>(n_elements_);
    }

    std::size_t size() const { return n_elements_; }
    const T& operator[](const size_t index) const {
        return c_[index];
    }
    T& at(const std::size_t index) const {
        if (index > n_elements_ - 1) {
            throw std::out_of_range("Container::at(): index out of range");
        }
        return c_[index];
    }
    iterator begin() const { return iterator(c_.get()); }
    iterator end() const { return iterator(c_.get() + n_elements_); }
};

int main()
{
    Container<int> c {4, 2, 5, 1, 3};
    std::cout << c.at(3) << std::endl;
    for (auto e : c | std::ranges::views::reverse) {
        std::cout << e << ' ';
    }
    endl(std::cout);
    return 0;
}

Chapter 5. Lambda Expressions

This ability to capture variables outside its own scope is what makes a lambda a closure.

Use Lambdas as Predicates with the Algorithm Library

这里一个有趣的例子:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

auto is_div_by(int divisor) {
    return [divisor](int i) { return i % divisor == 0; };
}

int main()
{
    const std::vector<int> v {1, 7, 4, 9, 4, 8, 12, 10, 20};
    for (int i : {3, 4, 5}) {
        auto pred = is_div_by(i);
        int count = std::count_if(v.begin(), v.end(), pred);
        std::cout << "numbers divisible by " << i << ": " << count << std::endl;
    }

    return 0;
}

Concatenate Lambdas with Recursion

#include <iostream>
#include <functional>

template<typename T, typename ...Ts>
auto concat(T t, Ts ...ts) {
    if constexpr (sizeof...(ts) > 0) {
        return [&](auto ...params) {
            return t(concat(ts...)(params...));
        };
    } else {
        return t;
    }
}

int main()
{
    auto twice = [](auto i) { return i * 2; };
    auto thrice = [](auto i) { return i * 3; };
    auto combined = concat(thrice, twice, std::plus<int>{});
    std::cout << combined(2, 3) << std::endl;
    return 0;
}

Jump Table

#include <string>
#include <iostream>
#include <cctype>
#include <map>

const char prompt(const char* p) {
    std::string r;
    std::cout << p << " > ";
    std::getline(std::cin, r);

    if (r.size() < 1) return '\0';
    if (r.size() > 1) {
        std::cout << "Response too long" << std::endl;
        return '\0';
    }
    return toupper(r[0]);
}

using jumpfunc = void(*)();
std::map<const char, jumpfunc> jumpmap {
    { 'A', []{ std::cout << "func A" << std::endl; } },
    { 'B', []{ std::cout << "func B" << std::endl; } },
    { 'C', []{ std::cout << "func C" << std::endl; } },
    { 'D', []{ std::cout << "func D" << std::endl; } },
    { 'X', []{ std::cout << "Bye!" << std::endl; } },
};

int main()
{
    char select {};
    while (select != 'X') {
        if ((select = prompt("select A/B/C/D/X"))) {
            auto it = jumpmap.find(select);
            if (it != jumpmap.end()) it->second();
            else std::cout << "Invalid response" << std::endl;
        }
    }
    return 0;
}

Chapter 6. STL Algorithms

std::clamp

C++17 的新算法,用一个最小值和一个最大值将一个数值标量(numeric scalar)限制在这个范围内,举个例子:

int main() {
    auto il = { 0, -12, 2001, 4, 5, -14, 100, 200,
        30000 };
    ...
    vector<int> voi { il };
    cout << "vector voi before:\n";
    printc(voi);
    cout << "vector voi after:\n";
    for (auto& e : voi) e = clamp(e, ilow, ihigh);
    printc(voi);
}

运行结果是:

vector voi before:
0 -12 2001 4 5 -14 100 200 30000
vector voi after:
0 0 500 4 5 0 100 200 500

std::sample

挺有趣的代码,对正态分布进行采样:

#include <algorithm>
#include <array>
#include <vector>
#include <map>
#include <iostream>
#include <cmath>
#include <random>
#include <string>

int iround(const double d) {
    return static_cast<int>(std::round(d));
}

int main()
{
    constexpr std::size_t n_data { 200000 };
    constexpr std::size_t n_samples { 500 };
    constexpr int mean { 0 };
    constexpr std::size_t dev { 3 };

    std::random_device rd;
    std::mt19937 rng(rd());
    std::normal_distribution<> dist {mean, dev};

    std::array<int, n_data> v {};
    for (auto& e : v) e = iround(dist(rng));
    std::array<int, n_samples> samples {};
    std::sample(v.begin(), v.end(), samples.begin(), n_samples, rng);

    std::map<int, std::size_t> hist {};
    for (const int i : samples) ++hist[i];

    constexpr size_t scale {3};
    std::printf("%3s %5s %s/%d\n", "n", "count", "graph", scale);
    for (const auto& [value, count] : hist) {
        std::printf("%3d (%3d) %s\n", value, count, std::string(count / scale, '*').c_str());
    }

    return 0;
}

运行结果如下:

  n count graph/3
 -9 (  1) 
 -8 (  1) 
 -7 (  4) *
 -6 ( 12) ****
 -5 ( 17) *****
 -4 ( 33) ***********
 -3 ( 50) ****************
 -2 ( 59) *******************
 -1 ( 48) ****************
  0 ( 70) ***********************
  1 ( 57) *******************
  2 ( 55) ******************
  3 ( 37) ************
  4 ( 29) *********
  5 ( 13) ****
  6 (  6) **
  7 (  5) *
  8 (  3) *

Chapter 7. Strings, Streams, and Formatting

std::string_view as a Lightweight String Object

std::string_view 是一个字符串引用。

Concatenate Strings

看 benckmarks:

Concatenation method Benchmark in milliseconds
append() 425ms
operator+() 660ms
format() 783ms
ostringstream 3,462ms

嗯,我以前一直以为 std::stringstream 会更快,其实是错误的。std::stringstream 会在每次修改时都创建一个对象。

所以正常情况下都应该用 + 直接拼接,append 虽然性能更好一点点但是很丑。需要用到 std::stringstream 的时候只有不同类型拼接的时候(因为用的是 operator<<)。

Transform Strings

std::string 是一个 contiguous container。

Regex

对于正则表达式,可以使用 () 来标识 sub-match。

std::sregex_token_iterator 的第四个参数 const std::vector<int>& submatches,可以填入迭代器接下来需要迭代的某一个 sub-match,其中 sub-match 0 是代表整个匹配的特殊值。

Chapter 8. Utility Classes

部分内容就大概过一遍,需要的时候再去查就好了。

std::optional

std::optional 提供接收 T 类型的非 explicit 的构造函数,可以使用 dereference operation 取得里面可能存在的 T 类型值,可以直接隐式转为 bool 值(相当于 ::has_value::operator bool 是同一个函数)。

有个 std::bad_optional_access 的非法访问异常。

std::any

std::any::type() 会返回一个 std::type_info,可以通过 std::type_info::name() 得到里面元素类型名。typeid(T) 也返回一个 std::type_info, so you know。

std::any_cast<T>(a) 可以为 any a of std::any 提取/解引用一个 T 类型的值出来。对应的有个 std::bad_any_cast 异常。

std::variant

std::visit 可以调用为 types holden by variant 重载 operator() 函数的 functor。举个例子:

using v_animal = std::variant<Cat, Dog, Wookie>;
list<v_animal> pets {...};

struct animal_speaks {
    void operator()(const Dog& d) const { d.speak(); }
    void operator()(const Cat& c) const { c.speak(); }
    void operator()(const Wookie& w) const { w.speak(); }
};

for (const v_animal& a : pets) {
    std::visit(animal_speaks{}, a);
}

或者可以使用 type indexes + get 的组合,这个 indexes of types 由 variant 的可变模板参数的顺序确定:

for (const v_animal &a : pets) {
    auto idx {a.index()};
    if (idx == 0) get<Cat>(a).speak();
    if (idx == 1) get<Dog>(a).speak();
    if (idx == 2) get<Wookie>(a).speak();
}

可以用 get_if<T>(a) 去 tests a given element against a type,返回 T 类型的指针。

std::holds_alternative<T>(a) 返回一个 bool,跟上面的 get_if<T> 的目的类似。

std::chrono

Prerequisites:

// <chrono>
using std::chrono::system_clock;
using std::chrono::steady_clock;
using std::chrono::high_resolution_clock;
using std::chrono::duration;
using seconds = duration<double>;
using milliseconds = duration<double, std::milli>;
using microseconds = duration<double, std::micro>;
using fps24 = duration<unsigned long, std::ratio<1, 24>>;  // <ratio>

chrono library 里提供了 std::time_point 版本的 std::format 特化,这个特化调用了 std::strftime 函数。于是关于各种方式输出这个 time point:

#include <iostream>
#include <chrono>     // std::chrono
#include <ctime>      // std::strftime, std::localtime
#include <iomanip>    // std::put_time

using std::cout, std::endl;
using std::chrono::system_clock;

int main()
{
    auto t/* : std::chrono::time_point<std::chrono::system_clock> */ = system_clock::now();

    // Nice one!
    // cout << format("system_clock::now is {:%F %T}\n", t);

    // Stupid method!
    char tstr[100];
    auto tt = system_clock::to_time_t(t);
    std::strftime(tstr, sizeof(tstr), "%F %T", std::localtime(&tt));
    std::puts(tstr);

    // Compromise method
    cout << std::put_time(std::localtime(&tt), "%F %T") << endl;

    return 0;
}

chrono library 提供了三种钟,system_clocksteady_clockhigh_resolution_clock

其中 steady_clock 好像是说会记录相对时间(第一次启动会从 UNIX 时间戳的 0 也就是 1 January 1970, 00:00 UTC 开始?好像是这个意思),所以用来计算时差比较好,应该是比 system_clock 走得更准一点。

两个同类的 clock 可以作差,可以返回一个 duaration

seconds d {t2 - t1};

std::millistd::micro 是对应的千分、百万分的 std::ratio

Fold Expression and Variadic Tuples

#include <iostream>
#include <tuple>

template<typename... T>
constexpr void print_t(std::tuple<T...>& tup) {
    auto lpt = [&tup]<std::size_t... I>(std::index_sequence<I...>) constexpr {
        const char* s[2] {"", ", "};
        (..., (std::cout << s[I > 0] << std::get<I>(tup)));
        std::cout << std::endl;
    };
    lpt(std::make_index_sequence<sizeof...(T)>());
}

int main()
{
    std::tuple lables{ "ID", "Name", "Scale" };
    std::tuple employee{ 123456, "John Doe", 3.7 };
    std::tuple nums{ 1, 7, "forty-two", 47, 73L, -111.11 };
    print_t(lables);
    print_t(employee);
    print_t(nums);
    return 0;
}