Press "Enter" to skip to content

Posts published in “Programming Language”

Morden C++

之前在B站发起的编程语言投票已经有了结果,没想到C++居然是第一名!因为我用C++,所以我的受众大部分用C++,这就是所谓的幸存者偏差吗?做这期节目的主要原因是由于 1.注册了某OJ,发现连C++11都不支持,代码写得太别扭了,放弃。2. 由于我自己也在不断学习morden C++,使用一些新的语法和API然后一直有同学在问这是什么东西啊?之前没看到过嘛。于是我就稍微整理了一下。这一切还要从41年前说起。

C++ 诞生于1979年,相信比花花和绝大部分的同学年纪还要大。最早的时候还不叫C++,而是叫C with classes。C++的第一次标准化C++98则是在其诞生整整19年之后的1998年才完成的(标准化委员会到是早在1990/1991年就成立了),放在今天这是绝对不能想象的事情。C++98完善了模版,增加了STL containers,包含我们最常用的vector, set, deque, list, map等,iterator,iostream,complex,algorithms (std::sort, std::upper_bound, std::fill, std::swap)等这些都是在C++98标准化的。可以说C++98奠定了Classic C++的地位,易用性和可移植性都大幅提高,对C++的普及起到了关键的作用。之后的C++03在C++98的基础上做了小幅的改进。至此C++的标准化告一段落,C++也迎来了“黄金时期”,并于2003年8月21号达到TIOBE编程语言排行榜的历史最高成绩:17.531%,排名第三。上面有地位不可撼动的老大哥C语言还有领跑多年的Java,后面则有JavaScript/C#/Python等新秀奋起直追(PHP说:还有我!还有我!),老态龙钟的C++有些力不从心,在2003年之后就一直走下坡路,到2014年中旬一度跌破5%。

廉颇老矣尚能饭否?C++痛定思痛,10年磨一剑,终于在2011年推出了C++11标准,在C++98的基础上增加了许许多多的新功能,拉开了C++现代化的帷幕。有同学要问了:这么强大的C++11标准推出之后为什么C++的排名不降反升了?正是因为C++11的改动太大了,直到2020年,还有一些(主流)编译器没有完整实现C++11。这然我想起了早些年坊间的一则流言:“没有一款编辑器完整地实现了C++”,那时候很多东西没有标准化这么说当然是可以的。但放到标准化之后的今天,这条流言好像也不假。标准虽然在2011就提出了,但完全实现和普及已经是几年之后的事情了。之后的C++标准委员会就像打了鸡血一样,每隔三年就制定一个新标准C++14,C++17。C++20也已经FC(feature complete)了。新的标准让C++更强大,更优雅,更高效,但这一切的代价就是用户的学习成本也陡然上升,并且会有一些抵触情绪,拒绝接受新事物。任何人都不能否认现代C++变得更难了,如果有谁和你说他精通C++,你可以反问他是不是还在用VC98。反正我只敢说略懂皮毛。

以为这期节目就是听花花说书吗?当然不只是这些,下面花花作为一名普通C++用户给大家列举一些现代C++(C++11/14/17)一些好用的语法、类和函数,也欢迎大家留言补充。

1. std::unordered_map / std::unordered_set C++11

想不到吧,hashtable是在C++11才正式标准化的,虽然之前各编译器都有支持,但毕竟不是标准版。unordered_*提供了O(1)时间的查找、插入和删除。是一个非常高效的数据结构(C用户哭晕在厕所)。为什么叫unorderd_map这么奇怪的一个名字而不直接叫hash_map呢?只是为了告诉用户key是无序的吗?标准委员会给出的回答是:hash_map已经被各大vendor抢注了,同名容易造成冲突… 哎,谁让你这么晚才标准化呢!?域名抢注要趁早!
Java对应:HashMap,HashSet
Python对应:dict, set

2. initializer_list C++11

initializer_list方便了(容器)对象的初始化

int a = 2; // Before, assignment
int a{2}; // After, construction

vector<int> v; // Before
v.push_back(1);
v.push_back(2);
v.push_back(3);

vector<int> v = {1,2,3}; // After, assignment
vector<int> v{1,2,3}; // After, construction
对于vector<int> v{1,2,3}; 编译器做了两件事情:
1. 用{1,2,3}字面量创建 initializer_list<int> l
2. 调用vector<int>的拷贝构造函数,传入l
所以说使用initializer_list还是有一些些overhead的

pair<int, float> p{1, 3.14}; // After
map<string, int> m{{“hello”, 1}, {“world”, 2}}; // After

vector<int> foo() { // Before
set<int> s = …
return vector<int>(begin(s), end(s));
}
vector<int> foo() { // After
set<int> s = …
return {begin(s), end(s)};
}

Java对应:多种不同方法…
Python对应:[], (), {}

3. auto 关键词 C++11

新增的auto关键词让人又爱又恨,编译器做了类型推断省去了冗长的类型名称的拼写,但需谨慎使用。

int a = 2;
auto a = 2; // a is int

float a = 2; // implicit conversion
auto a = 2; // a is int not float
auto a = 2.0; // a is double not float
auto a = 2.0f; // a is flot

auto v{1,2,3}; // does not compile
auto v = {1,2,3}; // v is initializer_list not vector
auto v = vector<int>{1,2,3,4}; // ok, but longer
vector<int> v{1,2,3,4}; // best

std::unique_ptr<Foo> p = std::make_unique<Foo>(…); // Before
auto p = std::make_unique<Foo>(…); // OK, shorter

有多少人是被iterator劝退的?
for (std::unordered_map<std::string, int>::const_iterator it = s.begin(); it != s.end(); ++it) // Before
for (auto it = s.begin(); it != s.end(); ++it) // After

Java对应:var Java10
Python对应:傲娇地说:类型是神马?

4. Structured Binding C++17

有了类型推断和auto关键词之后我们就可以做结构化绑定了

// Before
pair<int, float> p(1, 3.14);
int x = p.first;
float y = p.second;

// After
auto [x, y] = p; // must use auto
// x is int, x = 1;
// y is float, y = 3.14

// Before
set<int> s;
auto kv = s.insert(x);
auto it = kv.first; // iterator
bool success = kv.second; // inserted or not

// After
set<int> s;
auto [it, success] = s.insert(x);

我们在下面还会看到结构化绑定的身影

Java 对应:null
Python 对应:a, b = c, d

5. Range based for loop C++11

这也是一个非常好用的功能,配合上auto和structured binding简直了。

for (int i = 0; i < v.size(); ++i) cout << v[i] << endl; // Before
for (int x : v) cout << x << endl; // After

for (std::unordered_map<std::string, int>::const_iterator it = s.begin(); it != s.end(); ++it) // Before
for (auto it = s.begin(); it != s.end(); ++it) // w/ auto
for (auto&& kv : s) cout << kv.first << “->” << kv.second << endl; // range based for loop
for (auto&& [k, v] : s) cout << k << “->” << v << endl; // w/ structured binding

Java 对应 for (int x : v)
Python 对应 for k, v in s.items()

6. Lambda Expressions C++11

我们可以用lambda表达式来捕获对象并创建closure(闭包)。

最简单的用法是创建function对象,你可以把它看做在函数里面定义函数。

也可以用来自定义排序

通过捕获非状态参数,减少递归函数的参数

Java 对应:->
Python 对应:lambda or nested functions

好了今天先讲到这里,给大家一点时间消化一下。也可以在YouTube/B站上看视频版本。

花花酱 LeetCode 10. Regular Expression Matching

Problem

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution 1: Recursion

Time complexity: O((|s| + |p|) * 2 ^ (|s| + |p|))

Space complexity: O(|s| + |p|)

C++