始于
分类:C++
Tags: [ C++ ]
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
- 避免 implicit narrowing conversion
- using
T{}
to zero-initializeint 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::formatter
对 Frac
类的特化版本,以使 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::format
由 std::make_format_args
和 std::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:
- strong_ordering::equal // operands are equal
- strong_ordering::less // lhs is less than rhs
- strong_ordering::greater // lhs is greater than rhs
And if operands are floating-points numbers, will return partial_ordering
object:
- partial_ordering::equivalent // operands are equivelant
- partial_ordering::less // lhs is less than rhs
- partial_ordering::greater // lhs is greater than rhs
- 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
- 普通
template<typename T> requires Number<T> T add(const T& r) { return 42 + r; }
- 还是很普通
template<Number T> T add(const T& r) { return 42 + r; }
requires
in function signaturetemplate<typename T> T add(const T& r) requires Number<T> { return 42 + r; }
- 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.ixx
,ixx
后缀是 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
- A Range 是一个可迭代的对象集合(a collection of objects which can be iterated)。
- A View 是由另外的基础 range 变换而来的 range(a range that transforms another underlying range)。
- A View Adapter 是取一个 range 返回一个 view 对象的对象(an object that takes a range and returns a view object)。
<ranges>
库使用 std::ranges
和 std::ranges::view
这两个名称空间。这里说到 to save the fingers!,还是用下 namespace aliases 比较好。
用法
-
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. -
因为 view adapter 也是可迭代的,所以它也满足作为一个 range 使用:
auto result = nums | views::take(5) | reverse;
-
filter view
for (auto v : nums | views::filter([](int i) { return i % 2 == 0; })) { std::cout << v << ' '; } //
-
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
-
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
:
-
std::sort(v.begin(), v.end());
现在可以写成:
ranges::sort(v);
-
std::sort(v.begin() + 5, v.end());
可以写成:
ranges::sort(ranges::drop_view(v, 5));
-
std::sort(v.rbegin() + 5, v.rend());
可以写成
ranges::sort(v | views::reverse | views::drop(5))
关于 ranges::xxxx_view
与 view::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::pair
、std::tuple
、std::array
、struct
,现在也可以绑定 C 风格数组了。
其它用法没有区别。
Initialize Variables Within if
and switch
Statements
这是 C++17 的语法,没有新内容,但是例子很有趣:
-
一个互斥锁的例子:
if (lock_guard<mutex> lg{ my_mutex }; condition) { // interesting things happen here }
-
操作 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++ 的所有容器类型:
- 序列型容器(sequential containers):
array
,定长数组vector
,可变数组forward_list
,单链表list
,双链表deque
,双端队列
- 关联型容器(associative containers):
set
,每一个元素的 key 是它自己的关联型容器multiset
,非唯一 key 版本的set
unordered_set
,迭代中无序版本的set
unordered_multiset
map
multimap
unordered_map
unordered_multimap
- 容器适配器(container adapters):
stack
,提供 FILO 的接口queue
,提供 FIFO 的接口priority_queue
,优先队列/堆,默认是遵循严格弱序(strict weak ordering)的大根堆
Uniform Erasure Function
std::erase
现在可以直接作用于 4 种序列型容器(当然不包括 std::array
)。注意,这个新版的 std::erase
和 std: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 引入的 extract
,extract
返回一个特殊的 node_type
对象。Node handler 没有规定具体的实现,但是需要提供一些必要的成员函数,如 empty
、key
、mapped
等等。下面是使用 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:
- Input Iterator (read, increment once)
- Forward Iterator (increment multiple times)
- Bidirectional Iterator (decrement)
- Random Access Iterator (random access)
- Contiguous Iterator (contiguous storage like an array)
上面的所有 iterators 类型都是 mutable iterators。
还有一种与 Input Iterator 对应的 Output Iterator,可以 write & increment once。
Iterator Concepts
从 C++20 开始 STL 开始使用 concepts 定义 iterators 以取代原来的 categories。下面的这些 concepts 都包含在 std::
名称空间中:
indirectly_readable
:can be read by the dereference operator(*
)indirectly_writeable
:*itr
which is writableweakly_incrementable
: can++
but can’t preserve equiality. e.g.: wherea == b
, maybe++a != ++b
incrementable
: can++
and preserve equialityinput_or_output_iterator
: which can be incremented and dereferenced. Every iterator must satisfy this conceptsentinel_for
: which is used to find the end of an object of indeterminate size, such as an input streamsized_sentinel_for
: based onsentinel_for
, and may be used with another iterator and the-
operator to determine its distance in constant timeinput_iterator
ouput_iterator
forward_iterator
bidirectional_iterator
random_access_iterator
contiguous_iterator
举个例子:
#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 使用的最小化要求是:
begin()
和end()
迭代器- 需要支持
!=
不等于比较运算 - 需要支持
++
前缀运算 - 需要支持
*
解引用
Make Your Iterators Compatible with STL Iterator Traits
上面的 Seq
类还不支持 STl 的 algorithms,使用了会报错。这里出现了一句描述:
The error messages are vague, cryptic, and cascading.
- vague a. not clear in a person’s mind; of uncertain, indefinite, or unclear character or meaning
- cryptic a. with a meaning that is hidden or not easily understood; having a meaning that is mysterious or obscure
- cascade v. to flow downwards in large amounts (like waterfall)
首先需要添加 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
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_clock
、steady_clock
和 high_resolution_clock
:
system_clock
– provides wall clock time.steady_clock
– provides guaranteed monotonic ticks for duration measurements.high_resolution_clock
– provides the shortest available tick period. It may be an alias of system_clock or steady_clock on some systems.
其中 steady_clock
好像是说会记录相对时间(第一次启动会从 UNIX 时间戳的 0 也就是 1 January 1970, 00:00 UTC 开始?好像是这个意思),所以用来计算时差比较好,应该是比 system_clock
走得更准一点。
两个同类的 clock 可以作差,可以返回一个 duaration
:
seconds d {t2 - t1};
std::milli
、std::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;
}