Jiez19971225‘s Blog

做自己爱做的事

0%

发表于 更新于 分类于   |   字数统计: 497(字)   |   阅读时长: 1(分)

uri 匹配规则

location 规则类型

这部分内容来自详细解析 nginx uri 如何匹配 location 规则

= exact uri

完全匹配规则，要求 url 和规则完全相同

1
2
3
location ~ /api/v1 {
    ....
}
~ case-sensitive regex

区分大小写的正则表达式匹配规则

1
2
3
location ~ /api/v1 {
    ....
}
~* case-insensitive regex

不区分大小写的正则表达式匹配规则

1
2
3
location ~ /api/v1 {
    ....
}
~* case-insensitive regex

不大小写的正则表达式匹配规则

1
2
3
location ~ /api/v1 {
    ....
}
^～ disable regex prefix

匹配流程与 prefix 规则相同，有一点区别在于，如果最长匹配是当前规则，则之后不进行 正则表达式 规则的搜索。

1
2
3
location ~ /api/v1 {
    ....
}

uri 如何选择 location

  1. 如果存在 exact uri 规则与 uri 匹配，至步骤 6

  2. 在所有 prefix 规则和 disable regex prefix 规则中进行匹配（与这些规则定义的顺序无关），
    如果没有匹配到规则，至步骤 3；如果存在匹配的规则，选择出最长匹配 uri 的规则：

    • 如果规则是 disable regex prefix 类型，至步骤 6
    • 如果规则是 prefix 类型，记住当前匹配的 prefix 规则，选为待定，至步骤 3

  3. 逐个遍历 case-sensitive regex 规则和 case-insensitive regex 规则（按照这些规则定义的前后顺序）:

    • 如果规则匹配，则遍历终止，至步骤 6
    • 如果规则没有匹配，则继续

  4. 如果之前有 prefix 规则条目被选择为待定，至步骤 6

  5. 匹配失败，返回 404，结束
  6. 选择当前规则，使用其配置，结束

try_files 解析

$uri 指代访问的 uri 资源，$uri/语法可以用来检测一个目录的存在，如果没有找到，一个内置的重定向将请求重定向到最后一个参数
最后一个参数可以指向一个命名的 location

1
2
3
4
5
6
7
8
9
10
11
12
location / {
    try_files $uri $uri/ index.html $uri.html =404;
}
location / {
    try_files /system/maintenance.html
              $uri $uri/index.html $uri.html
              @mongrel;
}

location @mongrel {
    proxy_pass http://mongrel;
}

发表于 更新于 分类于   |   字数统计: 1.7k(字)   |   阅读时长: 8(分)

基本概念

高阶函数

JS 中 函数是一等公民
函数可以作为参数和返回值传递

回调函数的问题

  1. 不能 trycatch
  2. 不能 return
  3. 回调地狱

解决回调地狱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let EventEmitter = require("events");
let eve = new EventEmitter();
let html = {}
eve.on("ready", function(key, value) {
  html[key] = value;
  if(Object.keys(html).length === 2){
      console.log("ok)
  }
});

fs.readFile("./node/template.txt", "utf8", function(err, data) {
  eve.emit("ready", "template", data);
});
fs.readFile("./node/data.txt", "utf8", function(err, data) {
  eve.emit("ready", "data", data);
});

哨兵函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let html = {};
function done(key, value) {
  html[key] = value;
  if (Object.keys(html).length === 2) {
    console.log("ok");
  }
}

fs.readFile("./node/template.txt", "utf8", function (err, data) {
  done("template", data);
});
fs.readFile("./node/data.txt", "utf8", function (err, data) {
  done("data", data);
});

进一步优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function render(length,cb){
    return function(key,value){
        html[key] = value
        if(Object.keys(html).length === length){
            cb()
        }
    }
}
function done = render(2,function(){
    console.log("ok")
})

fs.readFile("./node/template.txt", "utf8", function(err, data) {
  done("template", data);
});
fs.readFile("./node/data.txt", "utf8", function(err, data) {
  done("data", data);
});

generator

生成器是一个函数，可以用来生成迭代器，生成器函数和普通函数不同，生成器函数中间可以暂停

1
2
3
4
5
6
7
8
9
10
11
12
13
async function read(){
    let template = await readFile('./template.txt)
    let data = await readFile('./data.txt')
    return template + data
}
// 等同于
return read(){
    return co(function*(){
        let template = yield readFile('./template')
        let data = yield readFile('./data')
        return template + data
    })
}

co

1
2
3
4
5
6
7
8
9
10
11
12
13
function co(gen){
    let it = gen();  // gen是一个genarator函数
    return new Promise((resolve,reject) => {
        !function next(lastVal){
            if{value,done} = it.next(lastVal);
            if(done){
                resolve(value);
            }else{
                value.then(next,reject)
            }
        }
    })
}

Promise 详解

生命周期

Promise 的生命周期，初始为 pending state，表示异步操作尚未结束。挂起状态可以认为是未决的 unsettled，一旦异步操作结束， Promise 就会被认为是 已决的，进入两种可能状态

  • 已完成( fulfilled ): Promise 的异步操作已成功结束;
  • 已拒绝( rejected ): Promise 的异步操作未成功结束,可能是一个错误,或由其他原
    因导致。
    then()方法在所有的 Promise 上都存在,并且接受两个参数。第一个参数是 Promise 被完成时要调用的函数,与异步操作关联的任何附加数据都会被传入这个完成函数。第二个参数则是 Promise 被拒绝时要调用的函数,与完成函数相似,拒绝函数会被传入与拒绝相关联的任何附加数据。用这种方式实现 then() 方法的任何对象都被称为一个 thenable 。所有的 Promise 都是
    thenable ,反之则未必成立。
    Promis 也具有一个 catch() 方法,其行为等同于只传递拒绝处理函数给 then()。

创建未决的 Promise

使用 Promise 构造函数，Promise 执行器被调用的时候立即运行，当 resolve 或 reject 在执行器内部被调用时，一个作业被添加到作业队列，以决议这个 Promise。这和 setTimeout 或 setInterval 类似。

1
2
3
4
5
6
7
8
let promise = new Promise(function (resolve, reject) {
  console.log("Promise");
  resolve();
});
promise.then(function () {
  console.log("Resolved.");
});
console.log("Hi!");

输出:
Promise
Hi!
Resolved

完成处理函数与拒绝处理函数总是会在执行器的操作结束后被添加到作业队列的尾部，所以 then 中的操作会在最后执行。

创建已决的 Promise

使用 Promise.resolve 或者 Promise.reject

1
2
3
4
let promise = Promise.resolve(42);
promise.then(function (value) {
  console.log(value); // 42
});

经过我自己的测试，书上内容有误。以下为我自己测试的结果
若传入的 Promise 为挂起态,则 Promise.resolve 调用会将该 Promise 原样返回。此后如果决议原 Promise，在 then() 中可以接收到参数，如果拒绝，可以在 catch 中接收到参数。
Promise.resove 始终会返回原 Promise，而 Promise.reject 始终会对 Promise 重新包装，包装后的 Promise 处于拒绝态，且其 catch 接受的参数是原先处于拒绝态度的 Promise

thenable

当一个对象拥有一个能接受 resolve 与 reject 参数的 then() 方法,该对象就会被认为是一个非 Promise 的 thenable

1
2
3
4
5
6
7
8
9
let thenable = {
  then: function (resolve, reject) {
    resolve(42);
  },
};
let p1 = Promise.resolve(thenable);
p1.then(function (value) {
  console.log(value); // 42
});

Promise.resolve 方法会将其转换为 Promise，其状态为 Thenable 的 then 方法返回的状态，而 Promise.reject 方法会始终返回一个 reject 态的 Promise，传递给 catch 的参数为原 Thenable 对象

执行器错误

如果在执行器内部抛出了错误,那么 Promise 的拒绝处理函数就会被调用。

Promise A+ 实现

对照 https://promisesaplus.com/实现就好。

需要注意的规范中的 3.1 注明了 then 中的 onFulfilled and onRejected 需要在本次事件循环结束后方可执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
const PENDING = "pending";
const FULFILLED = "fulfilled";
const REJECTED = "rejected";
function Promise(executor) {
  let self = this; // 缓存 promise 实例
  self.status = PENDING;
  self.onResolvedCallbacks = [];
  self.onRejectedCallbacks = [];

  // 2.1
  function resolve(value) {
    setTimeout(() => {
      if (self.status === PENDING) {
        self.status = FULFILLED;
        self.value = value;
        self.onResolvedCallbacks.forEach((cb) => cb());
      }
    });
  }
  function reject(reason) {
    setTimeout(() => {
      if (self.status === PENDING) {
        self.status = REJECTED;
        self.value = reason;
        self.onRejectedCallbacks.forEach((cb) => cb());
      }
    });
  }
  try {
    executor(resolve, reject);
  } catch (err) {
    reject(err);
  }
}

Promise.prototype.then = function (onFulfilled, onRejected) {
  onFulfilled =
    typeof onFulfilled === "function" ? onFulfilled : (value) => value;
  onRejected =
    typeof onRejected === "function"
      ? onRejected
      : (reason) => {
          throw reason;
        };

  const self = this;
  let promise2;
  if (self.status === FULFILLED) {
    return (promise2 = new Promise((resolve, reject) => {
      setTimeout(() => {
        try {
          let x = onFulfilled(self.value);
          resolvePromise(promise2, x, resolve, reject);
        } catch (err) {
          reject(err);
        }
      });
    }));
  }
  if (self.status === REJECTED) {
    return (promise2 = new Promise((resolve, reject) => {
      setTimeout(() => {
        try {
          let x = onRejected(self.value);
          resolvePromise(promise2, x, resolve, reject);
        } catch (e) {
          reject(e);
        }
      });
    }));
  }
  if (self.status === PENDING) {
    return (promise2 = new Promise(function (resolve, reject) {
      self.onResolvedCallbacks.push(function () {
        try {
          let x = onFulfilled(self.value);
          resolvePromise(promise2, x, resolve, reject);
        } catch (e) {
          reject(e);
        }
      });
      self.onRejectedCallbacks.push(function () {
        try {
          let x = onRejected(self.value);
          resolvePromise(promise2, x, resolve, reject);
        } catch (e) {
          reject(e);
        }
      });
    }));
  }
};

// 根据 then 的传入处理函数 决定 then 返回的 promise 的状态
function resolvePromise(promise2, x, resolve, reject) {
  if (x === promise2) {
    return reject(new TypeError("Circular reference"));
  }
  let called = false;
  if (x !== null && (typeof x === "object" || typeof x === "function")) {
    try {
      let then = x.then;
      if (typeof then === "function") {
        then.call(
          x,
          function (y) {
            if (called) return;
            called = true;
            resolvePromise(promise2, y, resolve, reject);
          },
          function (err) {
            if (called) return;
            called = true;
            reject(err);
          }
        );
      } else {
        if (called) return;
        called = true;
        resolve(x);
      }
    } catch (err) {
      if (called) return;
      called = true;
      reject(err);
    }
  } else {
    resolve(x);
  }
}

Promise.prototype.catch = function (onRejected) {
  return this.then(null, onRejected);
};

Promise.prototype.resolve = function (value) {
  new Promise(function (resolve) {
    resolve(vzlue);
  });
};
Promise.reject = function (reason) {
  return new Promise(function (resolve, reject) {
    reject(reason);
  });
};
Promise.deferred = function () {
  let res, rej;
  const promise = new Promise((resolve, reject) => {
    res = resolve;
    rej = reject;
  });
  return {
    promise,
    resolve: res,
    reject: rej,
  };
};

module.exports = Promise;

发表于 更新于 分类于   |   字数统计: 1.8k(字)   |   阅读时长: 7(分)

记录一下自己不太清楚的知识点

第二章 URL 与资源

URL

url 的语法 <scheme>://<user>:<password>@<host>:<port>/<path>;<params>?<query>#<frag>

基础 URL HTML 标记<BASE>，可以设定基础 URL

URL 编码机制 urlencode 通过转义表示不安全的字符 包含一个百分号(%)，后面跟着两个表示字符 ASCII 码的十六进制数

第三章 HTTP 报文

报文的组成

组成 对报文进行描述的其实航 包含属性的首部块 可选的包含数据的主题 body
一般只有 PUT 和 POST 方法包含 body
PUT 方法的语义是让服务器用请求的主体部分来创建一个由所请求的 URL 命名的新文档，如果那个 URL 已经存在的话，就用这个主题来替代它

Http 协议中的 Header 与 Body。Header 的每行最后要加\r\n。Header 与 Body 之间要用\r\n 隔开。Body 后无需加\r\n。

ACSII 码中

‘\n’ 10 换行

‘\r’ 13 回车

也可以表示为’\x0a’和’\x0d’.(16 进制)

示例：HTTP 开始部分为 header，html 部分为 body。

1
2
3
4
5
6
7
8
9
HTTP/1.1 200 OK\r\n
Content-Encoding: gzip\r\n
Content-Type: text/xml\r\n
Content-Length: 399\r\n
Connection: keep-alive\r\n
X-Varnish-Cache: HIT\r\n
X-Varnish-Cache-Hits: 1241\r\n
\r\n
<html.....</html>

状态码

  • 101 Switching Protocols
  • 300 Multiple Choices 请求一个实际指向多个资源的 URL
  • 301 Moved Permanently 响应的 Location 首部包含资源现在所处的 URL
  • 302 Found 响应的 Location 首部的 URL 来临时定位资源 HTTP 1.0
  • 303 See Other HTTP 1.1
  • 307 Temporary Redirect POST 不会转为 GET

当 HTTP/1.0 客户端发起一个 POST 请求,并在响应中收到 302 重定向状态码时,它会接受 Location 首部的重定向 URL,并向那个 URL 发起一个 GET 请求(而不会像原始请求中那样发起 POST 请求)。
问题出在 HTTP/1.1。HTTP/1.1 规范使用 303 状态码来实现同样的行为(服务器发送 303 状态码来重定向客户端的 POST 请求,在它后面跟上一个 GET 请求)。
为了避开这个问题,HTTP/1.1 规范指出,对于 HTTP/1.1 客户端,用 307 状态码取代 302 状态码来进行临时重定向。这样服务器就可以将 302 状态码保留起来,为 HTTP/1.0 客户端使用了。

Keep-Alive

在 HTTP1.1 中默认开启，可以用 Connection:close 关闭，在 HTTP1.0 默认关闭，通过 Connection:keep-alive 开启

哑代理问题，所谓哑代理，是不会处理 Keep-Alive 连接，而是直接将其转发的代理。
在网景的变通做法是,浏览器会向代理发送非标准的 Proxy-Connection 扩展首部,而不是官方支持的著名的 Connection 首部。如果代理是盲中继,它会将无意义的 Proxy-Connection 首部转发给 Web 服务器,服务器会忽略此首部,不会带
来任何问题。但如果代理是个聪明的代理(能够理解持久连接的握手动作),就用一个 Connection 首部取代无意义的 Proxy-Connection 首部,然后将其发送给服务器,以收到预期的效果。

HTTP1.1 会使用管道优化，将一连串请求放入管道中，但是对于 POST 这个样非幂等的请求不应该放在管道中

代理和网关的区别

严格来说,代理连接的是两个或多个使用相同协议的应用程序,而网关连接的则是两个或多个使用不同协议的端点。网关扮演的是“协议转换器”的角色,即使客户端和服务器使用的是不同的协议,客户端也可以通过它完成与服务器之间的事务处理。

缓存

缓存有两种，强缓存和协商缓存
强缓存使用 Expired 和 Cache Control 字段，不需要向服务器通信
协商缓存需要携带协商字段与服务器通信，如果服务器返回 304 NOT Modified 信息，就使用缓存中的资源，并在相应中插入新鲜度信息
no-store 不缓存
no-cache 在与服务器进行新鲜度验证前不使用缓存

代理缓存

为什么要有代理缓存

对于源服务器，它是有缓存的，如 Redis，Memcache。但对于 HTTP 缓存来说，如果每次客户端缓存失效都从源服务器获取，那么给源服务器的压力是很大的。
由此引入了缓存代理机制，让代理服务器接管一部分的服务端 HTTP 缓存。客户端缓存过期后就近到代理服务器缓存中获取，代理缓存过期了才请求源服务器。

缓存代理的控制分为两部分，一部分是源服务器的控制，一部分是客户端的控制。

源服务器的缓存控制
private 和 public

在源服务器的响应头中，会加上 Cache-Control 字段进行缓存的控制，它的值中可以加入 private 或 public 表示是否允许代理服务器缓存。public 表示允许。

proxy-revalidate

must-revalidate 的意思是客户端缓存过期就去源服务器获取，而proxy-revalidate表示代理服务器的缓存过期后到源服务器获取

前者使用范围主体更广，后者不应用于用户代理的本地缓存，应用在缓存服务器上

s-maxage

s 是 share 的意思，限定了缓存在代理服务器中可以存放多久，和限制客户端缓存时间的 max-age 并不冲突

客户端的缓存控制
客户端宽容设置

在客户端的请求中，可以加入这两个字段，来对代理服务器上的缓存进行宽容和限制操作

1
max-stale:5

表示客户端到代理服务器上拿缓存的时候，只要过期时间在 5s 之内，依然可以从代理中获取

1
min-fresh:5

表示客户端到代理服务器上拿缓存的时候，一定要在过期前 5s 之前的时间内

only-if-cached

表示客户端只会接受代理缓存，而不会接受源服务器的响应，如果代理缓存无效，则直接返回 504

安全

CSRF Cross Site Request Forgery
点击劫持 设置 X-FRAME-OPTIONS

1
Set-cookie: user="mary17"; domain="airtravelbargains.com"

将 cookie user=”mary17” 发送给域 “.airtravelbargains.com” 中的所有站点:

cookie 规范允许用户将 cookie 与部分 Web 站点关联起来

1
Set-cookie: pref=compact; domain="airtravelbargains.com"; path=/autos/

如果用户访问 http://www.airtravelbargains.com/specials.html,就只会获得这个 cookie:
Cookie: user=”mary17”
但 如 果 访 问 http://www.airtravelbargains.com/autos/cheapo/index.html, 就会获得这两个 cookie:
Cookie: user=”mary17”
Cookie: pref=compact
Cache-Control:no-cache=” Set-Cookie” 除了 cookie 以外是可以缓存的

附录

HTTP 首部参考

  • Accept
1
2
3
Accept */* 表示所有类型
Accept: text/*, image/* 图片
Accept: text/*, image/gif, image/jpeg; q=1 图片 q表示质量
  • Age HTTP/1.1 缓存必须在发送的每条响应中都包含一个 Age 首部

发表于 更新于 分类于   |   字数统计: 4k(字)   |   阅读时长: 16(分)

闭关学习 react！

核心概念

jsx

1
2
3
const name = "Josh Perez";
const element = <h1>Hello, {name}</h1>;
ReactDOM.render(element, document.getElementById("root"));

在大括号中可以填入任何有效的 javascript 表达式。

在编译之后，JSX 表达式会被转为普通 JavaScript 函数调用，并且对其取值后得到 JavaScript 对象。

也就是说，你可以在 if 语句和 for 循环的代码块中使用 JSX，将 JSX 赋值给变量，把 JSX 当作参数传入，以及从函数中返回 JSX：

React DOM 在渲染所有输入内容之前，默认会进行转义。这可以有效防止 XSS 攻击。

Babel 会把 JSX 转译成一个名为 React.createElement() 函数调用。他会创建这样一个虚拟 dom 对象。

1
2
3
4
5
6
7
const element = {
  type: "h1",
  props: {
    className: "greeting",
    children: "Hello, world!",
  },
};

元素渲染

React 元素是不可变对象，一旦被创建，就无法更改他的子元素或者属性。更新 UI 的唯一方式就是创建一个新的元素，将其传入 ReactDOM.render()。

React 只更新它需要更新的部分。React DOM 会将元素和它的子元素与它们之前的状态进行比较，并只会进行必要的更新来使 DOM 达到预期的状态。

组件&props

函数组件，接受 props，返回 jsx

1
2
3
function Welcome(props) {
  return <h1>Hello, {props.name}</h1>;
}

组件可以是用户自定义的组件，这时它会将 jsx 所接收的属性以及自组件转换为单个对象传给组件。组件必须以大写字母开头。

1
2
3
4
5
6
function Welcome(props) {
  return <h1>Hello, {props.name}</h1>;
}

const element = <Welcome name="Sara" />;
ReactDOM.render(element, document.getElementById("root"));

解构写法

1
ReactDOM.render(<Comment {...data}>,document.getElementById('root'));

props 应该是只读的，函数组件都应该为纯函数

所有 React 组件都必须像纯函数一样保护它们的 props 不被更改。

当然，应用程序的 UI 是动态的，并会伴随着时间的推移而变化。在下一章节中，我们将介绍一种新的概念，称之为 “state”。在不违反上述规则的情况下，state 允许 React 组件随用户操作、网络响应或者其他变化而动态更改输出内容。

组件的运作方式

  • render 发现一个用户自定义组件，如果标签名是大写字母开头的，就会认为它是一个用户自定义组件
  • 先把 jsx 属性封装为一个 props 对象
  • 把它作为参数传递给组件
  • render 方法会把次 react 元素渲染到页面上

state&生命周期

不要直接修改 state

1
2
// Wrong
this.state.comment = "Hello";

而应该使用 setState()

1
2
// Correct
this.setState({ comment: "Hello" });

state 更新可能是异步的

不要依赖他们的值来跟新下一个状态

1
2
3
4
// Wrong
this.setState({
  counter: this.state.counter + this.props.increment,
});

可以让 setState() 接收一个函数而不是一个对象。这个函数用上一个 state 作为第一个参数，将此次更新被应用时的 props 做为第二个参数：

1
2
3
4
// Correct
this.setState((state, props) => ({
  counter: state.counter + props.increment,
}));

state 的更新可以被合并

数据向下流动

state 是局部的，除了拥有并且设置了它的组件，其他组件都无法访问。组件可以选择把它的 state 作为 props 向下传递给它的子组件中

事件处理

react 事件命名采用小驼峰。

使用 jsx 语法时，需要传入一个函数作为事件处理函数，而不是一个字符串，不能使用 return false 的方式组织默认行为，必须显式使用 preventDefault。

传参的方式

默认会将 e 作为最后一个参数传递，如果使用箭头函数的方式绑定，需要使用如下形式

1
(e) => handleFunc(e);

条件渲染

if && || 三目运算符

阻止组件渲染

让 render 函数返回 null

列表&key

渲染多个组件

使用 map 数组方法，渲染列表时应该提供一个 key 属性，通常使用数据中的 id 来作为元素的 key。

表单

受控组件

在 HTML 中，表单元素（如 input、 textarea 和 select）之类的表单元素通常自己维护 state，并根据用户输入进行更新。而在 React 中，可变状态（mutable state）通常保存在组件的 state 属性中，并且只能通过使用 setState()来更新。

我们可以把两者结合起来，使 React 的 state 成为“唯一数据源”。渲染表单的 React 组件还控制着用户输入过程中表单发生的操作。被 React 以这种方式控制取值的表单输入元素就叫做“受控组件”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class NameForm extends React.Component {
  constructor(props) {
    super(props);
    this.state = { value: "" };

    this.handleChange = this.handleChange.bind(this);
    this.handleSubmit = this.handleSubmit.bind(this);
  }

  handleChange(event) {
    this.setState({ value: event.target.value });
  }

  handleSubmit(event) {
    alert("提交的名字: " + this.state.value);
    event.preventDefault();
  }

  render() {
    return (
      <form onSubmit={this.handleSubmit}>
        <label>
          名字:
          <input
            type="text"
            value={this.state.value}
            onChange={this.handleChange}
          />
        </label>
        <input type="submit" value="提交" />
      </form>
    );
  }
}

textarea

在 html 中，textarea 使用子元素定义其文本，在 react 中，使用 value 属性代替

select

在 html 中 使用 selected 表明属性默认选中，react 在根 select 标签使用 value 属性

input type=file

在 react 中，它是一个非受控组件

处理多个输入

当需要处理多个 input 元素时，我们可以给每个元素添加 name 属性，并让处理函数根据 event.target.name 的值选择要执行的操作。

受控输入空值

在受控组件上指定 value 的 prop 会阻止用户更改输入。如果你指定了 value，但输入仍可编辑，则可能是你意外地将 value 设置为 undefined 或 null
如果确实是只读属性，应当加上 readOnly 属性

1
2
3
4
5
ReactDOM.render(<input value="hi" />, mountNode);

setTimeout(function () {
  ReactDOM.render(<input value={null} />, mountNode);
}, 1000);

状态提升

传递共同父组件的 props，props 是只读的，要在子组件中改变它，通常使用受控组件来解决，将父组件中改变 state 的函数作为 props 传递给子组件调用。

组合&继承

使用组合而非继承实现组件之间的代码重用

类似于 vue 的 slot，默认放在组件内部会作为 props.children 传递给子组件，当需要区分的时候，需要自定约定传入的 props

高级指引

无障碍

语义化

使用 React Fragments 来组合各个组件，类似于 Vue 中的 template
简写形式是 <></ >

其他内容看起来不是那么重要，略过

Context

react.createContext

创建一个 Context 对象。当 React 渲染一个订阅了这个 Context 对象的组件，这个组件会从组件树中离自身最近的那个匹配的 Provider 中读取到当前的 context 值。
只有当组件所处的树中没有匹配到 Provider 时，其 defaultValue 参数才会生效。

1
const MyContext = React.createContext(defaultValue);

Class.contextType

挂载在 class 上的 contextType 属性会被重赋值为一个由 React.createContext() 创建的 Context 对象。这能让你使用 this.context 来消费最近 Context 上的那个值。你可以在任何生命周期中访问到它，包括 render 函数中。不对其赋值是无法使用 this.context 获取值的。

refs 转发

refs 提供了一种方式，允许我们访问 DOM 节点或者在 render 方法中创建的 React 元素

基本用法 首先声明引用

1
const ref = React.createRef();

然后再你希望获取引用的节点上

1
<input type="text" ref={ref} value={props.content} />

这样在声明周期函数中，就可以使用 ref.current 获取到该节点的引用的

在高阶组件转发 refs

一般我们用高阶组件，会将所有 props 传递到其包裹的组件。但是 refs 不会传递，

1
2
3
render() {
      return <WrappedComponent {...this.props} />;
    }

可以使用 React.forwardRef API 明确地将 refs 转发到内部的组件。React.forwardRef 接受一个渲染函数，其接收 props 和 ref 参数并返回一个 React 节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function logProps(Component) {
  class LogProps extends React.Component {
    componentDidUpdate(prevProps) {
      console.log("old props:", prevProps);
      console.log("new props:", this.props);
    }

    render() {
      const { forwardedRef, ...rest } = this.props;

      // 将自定义的 prop 属性 “forwardedRef” 定义为 ref
      return <Component ref={forwardedRef} {...rest} />;
    }
  }

  // 注意 React.forwardRef 回调的第二个参数 “ref”。
  // 我们可以将其作为常规 prop 属性传递给 LogProps，例如 “forwardedRef”
  // 然后它就可以被挂载到被 LogProps 包裹的子组件上。
  return React.forwardRef((props, ref) => {
    return <LogProps {...props} forwardedRef={ref} />;
  });
}

如果不使用 React.forwardRef,普通的函数组件是不会获得该参数的，因为函数组件没有实例。
不管怎样，你可以在函数组件内部使用 ref 属性，只要它指向一个 DOM 元素或 class 组件：
使用 hooks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function CustomTextInput(props) {
  // 这里必须声明 textInput，这样 ref 才可以引用它
  const textInput = useRef(null);

  function handleClick() {
    textInput.current.focus();
  }

  return (
    <div>
      <input type="text" ref={textInput} />
      <input type="button" value="Focus the text input" onClick={handleClick} />
    </div>
  );
}

现在有个问题，useRef 和 createRef 看起来没啥区别啊

百度之后得到的答案是 createRef 每次渲染都会返回一个新的引用，而 useRef 每次都会返回相同的引用。

useRef 仅能用在 FunctionComponent，createRef 仅能用在 ClassComponent。！！！

错误边界

如果一个 class 组件中定义了 static getDerivedStateFromError() 或 componentDidCatch() 这两个生命周期方法中的任意一个（或两个）时，那么它就变成一个错误边界。当抛出错误后，请使用 static getDerivedStateFromError() 渲染备用 UI ，使用 componentDidCatch() 打印错误信息。

珠峰前端

生命周期详解

初始渲染阶段

componentWillMount -> render -> componentDidMount

更新阶段

shouldComponentUpdate

  • 返回 true -> componentWillUpdate -> render -> componentDidUpdate
  • 返回 false 不处理

从父组件传来的 props 改变
componentWillReceiveProps

  • 返回 true -> shouldComponentUpdate -> 走上面的流程
  • 返回 false 不处理

销毁阶段

componentWillUnmount
在这个生命周期勾子中清除定时器，防止内存泄漏

生命周期

react16.3 生命周期的变化

我看的这个视频时 18 年的，在之后 react 的生命周期有一次大的变动，增加了 getDerivedStateFromProps 和 getSnapshotBeforeUpdate 这两个生命周期函数，同时 componentWillMount 和 componentWillReceiveProps 已经不推荐使用，将在未来的 react 版本中移除

getDerivedStateFromProps

这个生命周期会在每次 re-rendering 之前被调用
意味着即使你的 props 没有任何变化，而是父 state 发生了变化，导致子组件发生了 re-render，这个生命周期函数依然会被调用

生命周期新

PropTypes 类型检查

  • array 数组
  • bool 布尔值
  • func 函数
  • number 数字
  • object 对象
  • string 字符换
  • symbol 符号
  • node 任何节点 numbers strings elements 或者包含这些类型的数组或者片段
  • element React 元素
  • instanceOf(Message) 类的一个实例
  • oneOf([‘News’,’Photos’]) 枚举值
  • oneOfType([PropTypes.string,PropTypes.number]) 多种类型中其中之一
  • arrayOf(PropTypes.number) 某种类型的数组
  • objectOf(PropTypes.number) 某种类型的对象
  • shape 特定形式的对象
  • .required 必填
  • function(){return new Error()} 自定义验证器

性能分析

分析性能 react 可以直接使用 react_perf，然后使用 chrome 进行录制分析

避免重复渲染

重写 shouldComponentUpdate 减少重新渲染

PureConponent

继承自 component，它做了一个优化，它重写了 shouleComponentUpdate 方法
这个比较是浅比较，所以 props 如果是对象，会出现无法更新的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
shouldComponentUpdate(nextProps,nextState){
  for(let prop in nextProps){
    if(nextProps[prop]!==this.props[prop]){
      return true;
    }
  }
  for(let state in nextStates){
    if(nextStates[state]!==this.states[state]){
      return true;
    }
  }
  return false;
}

immutable.js

可共享的变化是万恶之源，js 中的对象一般是可变的，因为使用引用赋值，对引用对象的修改会影响的原始对相关，为了避免这种影响，一般采用浅拷贝或者深拷贝的方式，但是如果对象的属性很多，就会造成 CPU 和内存的浪费。

immutable 中的数据一旦被创建，就不能被更改，所有修改和添加删除操作都会返回一个新的 immutable 对象。immutable 的实现原理是 Persistent Data Structure(持久化数据结构)，这个咱之前也接触过，主席树的原理啊，抽空研究一下。

1
2
3
4
5
6
7
let { Map } = require("immutable");
let m1 = Map({ a: 1, b: 2, c: 3 });
console.log(m1.get("a"));
let m2 = m1.set("a", "11");
console.log(m2.get("a"));
console.log(m1.get("a"));
console.log(m1 === m2);

缺陷 体积过大 20k

seamiess-immutable

使用 Object.defineProperty 扩展的 Javascript 的 Array 和 Object 对象来实现，只支持 Array 和 Objcet 两种数据类型

hooks

useState

标准写法，参数就是 state 的初始值，解构得到的第二个变量是设置该 state 的函数

1
const [age, setAge] = useState(42);

useEffect

它跟 class 组件中的 componentDidMount、componentDidUpdate 和 componentWillUnmount 具有相同的用途，只不过被合并成了一个 API。

当你调用 useEffect 时，就是在告诉 React 在完成对 DOM 的更改后运行你的“副作用”函数。由于副作用函数是在组件内声明的，所以它们可以访问到组件的 props 和 state。默认情况下，React 会在每次渲染后调用副作用函数 —— 包括第一次渲染的时候。

副作用函数还可以通过返回一个函数来指定如何“清除”副作用。例如，在下面的组件中使用副作用函数来订阅好友的在线状态，并通过取消订阅来进行清除操作：

使用规则

只能在函数最外层调用 Hook。不要在循环、条件判断或者子函数中调用。

只能在 React 的函数组件中调用 Hook。不要在其他 JavaScript 函数中调用。（还有一个地方可以调用 Hook —— 就是自定义的 Hook 中。）

通过跳过 Effect 进行性能优化

1
2
3
useEffect(() => {
  document.title = `You clicked ${count} times`;
}, [count]); // 仅在 count 更改时更新

createPortal

将组件渲染到组件树之外的地方，可以用来做弹窗

diff 算法处理 key

// TODO
希望操作最小化

第一步，把老数组在新数组中没有的元素移除掉

React Fiber

React render

触发 render 的场景

  • 状态更新时，类组件调用 setState 或者 函数组件的 state 更新
  • 父容器重新渲染，无论子组件的实现如何，都会重新渲染

性能优化

谨慎分配 state，为了避免不必要的 render，可以将状态下放到更低层级的组件

合并状态更新

使用 PureComponent 和 React.memo 避免不必要的 render 调用

避免组件不必要的渲染的方法有：React.memo 包裹的函数式组件，继承自 React.PureComponent 的 class 组件。

浅比较

用 PureComponent 或者 React.memo 修饰的组件，每次更新的时候都对 props 和 state 进行一次浅比较。如果有对象，且对象引用变化，就会触发重渲染。由于函数也是引用类型，如果传递的是箭头函数（匿名函数），组件也会在父组件重新渲染的时候重新渲染。

useMemo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function Example(props) {
  const [count, setCount] = useState(0);
  const [foo] = useState("foo");

  const main = useMemo(
    () => (
      <div>
        <Item key={1} x={1} foo={foo} />
        <Item key={2} x={2} foo={foo} />
        <Item key={3} x={3} foo={foo} />
        <Item key={4} x={4} foo={foo} />
        <Item key={5} x={5} foo={foo} />
      </div>
    ),
    [foo]
  );

  return (
    <div>
      <p>{count}</p>
      <button onClick={() => setCount(count + 1)}>setCount</button>
      {main}
    </div>
  );
}

发表于 更新于 分类于   |   字数统计: 1.8k(字)   |   阅读时长: 8(分)

因为看编译原理的有穷自动机，想到了以前一直不懂的这玩意。既然都叫自动机，就一块研究了吧。

AC 自动机是一种实现多模式匹配的字符串匹配算法。

前置技能 Trie 树（字典树）

字典树是一颗树，能迅速匹配字典中的字符串。
它具有以下基本性质。

  • 根节点不包括字符串，除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同

他的节点结构如下，其中 exist 标记当前节点是否是单词的结尾。

1
2
3
4
5
struct node
{
    node *next[26];
    bool exist;
}

以下是使用指针方式的构建代码,比较易懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

struct trie
{
    struct node
    {
        node *next[26];
        bool exist;
        node()
        {
            memset(next, 0, sizeof(next));
            exist = false;
        }
    };
    node *root;
    trie()
    {
        root = new node();
    };
    void insert(string word)
    {
        node *cur = root;
        for (int i = 0; i < word.length(); ++i)
        {
            int num = word[i] - 'a';
            if (!cur->next[num])
            {
                cur->next[num] = new node();
                cur = cur->next[num];
            }
            else
            {
                cur = cur->next[num];
            }
        }
        cur->exist = true;
    }
    bool find(string word)
    {
        node *cur = root;
        bool ok = true;
        for (int i = 0; i < word.length(); ++i)
        {
            int num = word[i] - 'a';
            if (!cur->next[num])
            {
                ok = false;
                break;
            }
            cur = cur->next[num];
        }
        if (!cur->exist)
        {
            ok = false;
        }
        return ok;
    }
};

main()
{
    trie t;
    t.insert("hello");
    t.insert("world");
    t.insert("i");
    t.insert("am");
    t.insert("a");
    t.insert("lvjie");
    cout << t.find("lvjie") << endl;
    cout << t.find("lvji") << endl;
    cout << t.find("i") << endl;
    cout << t.find("a") << endl;
}

字典树

利用字典树暴力求解多模式匹配

很容易想到，从字符串的每一个字符开始，跑 Trie 的匹配算法，这样的时间复杂度是 O(len(T) * maxD(Trie)) 即字符串长度乘以字典树的深度

KMP 的思想很重要

显然，匹配失败并不需要在下一位置从 Trie 根节点开始匹配，而是应该找当前匹配的最长后缀。

这里引入 fail 指针的概念，表示从该节点取前缀，在字典树中找到该前缀中后缀最长的节点。
以下摘自洛谷日报

  • 共同点-两者同样是在失配的时候用于跳转的指针。
  • 不同点-KMP 要求的是最长相同真前后缀，而 AC 自动机只需要相同后缀即可。
  • 因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。
  • 有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。
  • 也就是说，AC 自动机在对匹配串做逐位匹配时，同一位上可能匹配多个模式串。
  • 因此 fail 指针会在字典树上的结点来回穿梭，而不像 KMP 在线性结构上跳转。

构建基础思想

  • 构建一个节点的 fail 指针，需要找它的父节点的 fail 指针，所以构建过程应该是一个对树 BFS 的过程
  • 使用队列进行 BFS，每次取队首的节点，设为当前节点 cur，（该节点的 fail 指针已经构建），遍历它所有边，现假设有以字符 x 连接的子节点 child
    • 找当前节点 cur 的 fail 指针指向的节点是否也有以字符 x 连接的子节点，如果有，令 child 的 fail 指针指向该子节点
    • 如果没有，则令 cur = cur.fail，循环这个过程，直到 cur 指向 -1

查询思想

构建了 ac 自动机这种结构，它的基础应用就是给你一个字符串，让你统计在这个串中出现了多少统计的单词，而这个求解过程是在 O(N) 的复杂度下完成的

方法很简单，维护两个指针 cur 和 pos，分别指向字典树的节点和字符串遍历位置

对于每个位置 pos

  • 如果当前 cur = -1，说明该字符位置无法匹配任何模式串，则令 cur = 0， pos++
  • 如果当前 cur 位置的 cnt 计数不为 0，则将从该点及从该点可跳转的后缀纳入统计
  • 判断当前节点有否有以字符 str[pos]连接的子节点，如果有 pos++，cur 移动到该子节点的位置
  • 否则，cur 指向 cur 节点的 fail 指针的位置

代码实现

以下为 luogu P3808 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 7;
struct aho
{
    int size;
    struct node
    {
        int next[26];
        int fail, cnt;
        node()
        {
            memset(next, 0, sizeof(next));
            fail = cnt = 0;
        }
    } treeNode[maxn];
    queue<int> q;
    void init()
    {
        while (!q.empty())
        {
            q.pop();
        }
        for (int i = 0; i < maxn; ++i)
        {
            memset(treeNode[i].next, 0, sizeof(treeNode[i].next));
            treeNode[i].fail = treeNode[i].cnt = 0;
        }
        size = 0;
    }
    void insert(string s)
    {
        int cur = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            int num = s[i] - 'a';
            if (!treeNode[cur].next[num])
            {
                treeNode[cur].next[num] = ++size;
            }
            cur = treeNode[cur].next[num];
        }
        treeNode[cur].cnt++;
    }

    void build()
    {
        treeNode[0].fail = -1;
        queue<int> q;
        q.push(0);
        while (!q.empty())
        {
            int top = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                if (treeNode[top].next[i])
                {
                    q.push(treeNode[top].next[i]);
                    if (top == 0)
                    {
                        treeNode[treeNode[top].next[i]].fail = 0;
                    }
                    else
                    {

                        int v = treeNode[top].fail;
                        while (v != -1)
                        {

                            if (treeNode[v].next[i])
                            {
                                treeNode[treeNode[top].next[i]].fail = treeNode[v].next[i];
                                break;
                            }
                            else
                            {
                                v = treeNode[v].fail;
                            }
                        }
                        if (v == -1)
                        {
                            treeNode[treeNode[top].next[i]].fail = 0;
                        }
                    }
                }
            }
        }
    }

    int getNow(int cur)
    {
        int ret = 0;
        while (cur != -1)
        {
            ret += treeNode[cur].cnt;
            treeNode[cur].cnt = 0;
            cur = treeNode[cur].fail;
        }
        return ret;
    }

    int find(string target)
    {
        int res = 0;
        int pos = 0, cur = 0;
        while (pos < target.length())
        {
            if (treeNode[cur].cnt)
            {
                res += getNow(cur);
            }
            int num = target[pos] - 'a';
            if (cur == -1)
            {
                ++pos;
                cur = 0;
            }
            else if (treeNode[cur].next[num])
            {
                ++pos;
                cur = treeNode[cur].next[num];
            }
            else
            {
                cur = treeNode[cur].fail;
            }
        }
        if (treeNode[cur].cnt)
        {
            res += getNow(cur);
        }
        return res;
    }
    // 用来检查构建的字典树和fail指针的指向
    void check()
    {
        int cur = 0;
        struct pair
        {
            int v;
            string word;
            pair(int v, string word) : v(v), word(word){};
        };
        queue<pair> q;
        q.push(pair(0, ""));
        while (!q.empty())
        {
            pair top = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                if (treeNode[top.v].next[i])
                {

                    string word = top.word + char('a' + i);
                    q.push(pair(treeNode[top.v].next[i], word));
                    cout << "开始输出节点信息" << endl;
                    cout << "当前节点为编号" << treeNode[top.v].next[i] << endl;
                    cout << "word=" << word << endl;
                    cout << "cnt=" << treeNode[treeNode[top.v].next[i]].cnt << endl;
                    cout << "fail=" << treeNode[treeNode[top.v].next[i]].fail << endl;
                    cout << "节点信息输出完毕" << endl;
                }
            }
        }
    }
};
int main()
{
    freopen("3808.in", "r", stdin);
    int n;
    cin >> n;
    aho a;
    a.init();
    for (int i = 0; i < n; ++i)
    {
        string t;
        cin >> t;
        a.insert(t);
    }
    a.build();
    // a.check();
    string target;
    cin >> target;
    cout << a.find(target);
}

发表于 更新于 分类于   |   字数统计: 639(字)   |   阅读时长: 2(分)

推荐 B 站一个 UP 的视频，讲的非常容易理解 链接

暴力匹配思路

设模式串为 sp，要匹配的目标字符串为 st

扫一遍 st，每次从 st 当前位置开始匹配 sp，这样做浪费了大量时间，之前匹配过程得到信息没有被有效利用。

KMP 算法

最大公共前后缀

KMP 中为了有效利用之前已获得的信息，使用了最大公共前后缀。
前后缀的概念我们都知道，而公共前后缀是指该位置的前缀与后缀相同的部分。应当注意，前缀是不能包含当前位置的，而后缀不能包含第 1 个位置。
举个例子，ABCDABC 中，C 位置的最大公共前后缀是 ABC。
我们计算 AAAAB 的最大公共前后缀，使用 presuf 数组保存最大公共前后缀的长度
则 presuf = [0,1,2,3,0]

KMP 算法流程

构造最大前后缀数组

首先构造 presuf 数组，构造的流程如下

为了方便算法编写，令 presuf[0] = -1 作为边界，最大公共前后缀从 1 下标开始记录。
令 j 表示当前指针位置，可以理解为后缀指针，t 表示前缀指针位置。

1
2
3
4
5
6
7
8
9
t = presuf[0] = -1
m = sp.length()
while j < m-1
    // 当前位置前后缀匹配，更新 presuf 数组
    if t < 0 || sp[j] == sp[t]
        presuf[++j] = ++ t
    // 当前不匹配，则应该缩小前缀的范围
    else
        t = presuf[t];

构造过程

匹配流程

1
2
3
4
5
6
7
8
9
10
11
i = 0
j = 0
m = st.length()
while j < m
    if i < 0 || sp[i] == st[i]
        ++i,++j
        if i == sp.length()
            // 得到结果
    else
        // 这一步也很好理解，和构造过程是一样
        i = presuf[i]

代码实现

为了便于理解，变量名都是用了更具意义的缩写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int main()
{
    string st = "AAAAAAAAB";
    string sp = "AAAAB";
    int presuf[maxn];
    memset(presuf, 0, sizeof(presuf));
    // 构造过程
    int prep = presuf[0] = -1;
    int sufp = 0;
    while (sufp < sp.size())
    {
        if (prep < 0 || sp[prep] == sp[sufp])
        {
            presuf[++sufp] = ++prep;
        }
        else
        {
            prep = presuf[prep];
        }
    }
    // 匹配过程
    int stp = 0, spp = 0;
    int res = -1;
    while (stp < st.size())
    {
        if (spp < 0 || st[stp] == sp[spp])
        {
            ++spp, ++stp;
            if (spp == sp.length())
            {
                res = stp;
                break;
            }
        }
        else
        {
            spp = presuf[spp];
        }
    }
    cout << res;
}

应用

KMP 算法的应用，判定一棵二叉树是否是另一颗二叉树的子树，如果这棵树的序列化字符串是另一棵树序列化字符串的子串，则可以判定。

发表于 更新于 分类于   |   字数统计: 1.5k(字)   |   阅读时长: 6(分)

（以下内容摘自龙书）

有穷自动机是一般化的状态转换图，它可以是确定的或不确定的，其中不确定的含义是，对于某个输入符号，在同一个状态上存在不止一种转换。

下文以 DFA 指代确定的有穷自动机，NFA 指代不确定的有穷自动机。

DFA 和 NFA 都能且仅能识别正规集，即它们能够识别正规表达式所表示的语言。DFA 导出的识别器比 NFA 导出的识别器快得多，但是 DFA 可能比与之等价的 NFA 大得多。

NFA

NFA 是由以下几个部分组成的数学模型：

  • 一个状态的有穷集合 S
  • 一个输入符合集合$\Sigma$,即输入符号字母表
  • 一个转换函数 move，它把状态和符号组成的二元组映射到状态集合
  • 状态 $s_0$ 是唯一的开始或初始状态
  • 状态集合 F 是接受（或中止）状态集合

NFA 可以用带标记的有向图表示，称为转换图，其节点是状态，有标记的边是转化函数。

NFA

NFA2

DFA

DFA 是 NFA 的特例

  • 没有一个状态具有$\epsilon$转换
  • 对每个状态 s 和输入符号 a，最多只有一条标记为 a 的边离开

确定的有穷自动机在任何状态下，对任一输入符号，最多只有一个转换。如果用转换表表示 DFA 的转换函数，那么表中的每个表项最多只有一个状态。因而，很容易确定 DFA 是否接受某输入字符串，因为从开始状态起，最多只有一条到达接受状态的路径可由这个符号串标记。

NFA 转为 DFA

子集构造算法，在 NFA 的转换表中，每个表项是一个状态集，在 DFA 的转化表中，每个表项只有一个状态。从 NFA 变换到 DFA 的基本思想是让 DFA 的每个状态对应 NFA 的一个状态集。DFA 用它的状态去记住 NFA 在读输入符号后到达的所有状态。

NFA转DFA

定义三种操作

  • $\epsilon-closure(s)$ 从 NFA 状态 s 只经过$\epsilon$转换可以到达的 NFA 状态集
  • $\epsilon-closure(T)$ 从 T 中的状态只经过$\epsilon$转换可以到达的 NFA 状态集
  • move(T,a) 从 T 中的状态 S 经过输入符号 a 上的转换可以到达的 NFA 状态集

子集构造的步骤伪码如下，其中 Dstates 是 D 的状态集合，Dtran 是 D 的转换表

初始时，$\epsilon-closure(s)$是 Dstates 中唯一的状态且未被标记

1
2
3
4
5
6
7
while Dstates 中存在一个未标记的状态T
    标记T
    for 每个输入符号a
        U = epsilon-closure(move(T,a))
        if U 不在 Dstates中
            将U作为一个未标记的状态添加到Dstates中
        Dtran[T,a] = U

开始状态 A = $\epsilon-closure(s)$ = {0，1，2，4，7}，根据算法流程，先标记 A

然后计算 $\epsilon-closure(move(A,a))$，在状态 A 上只有 2 和 7 有 a 上的转换，得到状态 B={1,2,3,4,6,7,8},Dtran[A,a] = B

状态 A 中只有状态 4 对于输入 b 有一个转换，得到状态 C={1,2,4,5,6,7},Dtran[A,b]=C

然后对没被标记的状态 B 和状态 C 继续这个过程

状态 B 的 a 转换 得到的状态仍然是 B， Dtran[B,a] = B

状态 B 中在 8 上的 b 的转换可以得到新的状态 D={1,2,4,5,6,7,9} Dtran[B,b] = D。这里的计算详细解释一下，{1,2,3,4,6,7,8} 经过 b 转换后的集合是 {5,9}，然后再计算 $\epsilon-closure({5,8})$ 得到 {1,2,4,5,6,7,9}

状态 C 的 a 转换可以得到的状态 {1,2,3,4,6,7,8}，即状态 B，Dtran[C,a] = B

状态 C 的 b 转换可以得到的状态 {1,2,4,5,6,7}，即状态 C 自身，Dtran[C,b] = C

之后的过程省略，可以得到的五个状态集合是

A = {0,1,2,4,7}
B = {1,2,3,4,6,7,8}
C = {1,2,4,5,6,7}
D = {1,2,4,5,6,7,9}
E = {1,2,4,5,6,7,10}

状态 a b
A B C
B B D
C B C
D B E
E B C

子集构造法结果

代码实现

接下来用编程语言实现一个简单的 DFA

要实现的DFA

功能要求：输入一个单行无空格的字符串（以“#”号结束），如果该字符串是一个合法的输入，则显示“接受”，否则显示“不接受”。

分析该 DFA 的五元组信息如下

  • 一个状态的有穷集合 S = {0,1,2,3}
  • 一个输入符合集合$\Sigma$ = {a,b}
  • 一个转换函数 move，它把状态和符号组成的二元组映射到状态集合
    • move(0,a) = 1
    • move(0,b) = 0
    • move(1,a) = 1
    • move(1,b) = 2
    • move(2,a) = 1
    • move(2,b) = 3
    • move(3,a) = 1
    • move(3,b) = 0
  • 状态 $s_0$ 是唯一的开始或初始状态 = 0
  • 状态集合 F 是接受（或中止）状态集合 = {3}

根据如下信息就可以开始编码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
string str;
void dfa()
{
    bool ok = true; // 是否合法
    int pos = 0;    // 当前扫描位置
    int state = 0;  // 当前状态
    while (str[pos] != '#')
    {
        char next = str[pos];
        ++pos;
        if (state == 0)
        {
            if (next == 'a')
            {
                state = 1;
            }
            else if (next == 'b')
            {
                state = 0;
            }
            else
            {
                ok = false;
                break;
            }
        }
        else if (state == 1)
        {
            if (next == 'a')
            {
                state = 1;
            }
            else if (next == 'b')
            {
                state = 2;
            }
            else
            {
                ok = false;
                break;
            }
        }
        else if (state == 2)
        {
            if (next == 'a')
            {
                state = 1;
            }
            else if (next == 'b')
            {
                state = 3;
            }
            else
            {
                ok = false;
                break;
            }
        }
        else if (state == 3)
        {
            if (next == 'a')
            {
                state = 1;
            }
            else if (next == 'b')
            {
                state = 0;
            }
            else
            {
                ok = false;
                break;
            }
        }
    }
    if (state != 3)
    {
        ok = false;
    }
    if (ok)
    {
        cout << "接受" << endl;
    }
    else
    {
        cout << "不接受" << endl;
    }
}
int main()
{
    while (cin >> str)
    {
        dfa();
    }
}

输入：
abbab#
abb#
输出：
不接受
接受

发表于 更新于 分类于   |   字数统计: 4.1k(字)   |   阅读时长: 13(分)

思维导图

正常控制流

正常控制流包含两种顺序

  • 按照指令存放的顺序执行，新的 PC 数值为当前指令地址加上指令长度
  • 跳转到由于转移类指令指出的转移目标地址处执行，新的 PC 数值为转移目标地址

进程与进程上下文的切换

进程的概念

进程是资源分配的最小单位，每个应用程序在运行时均有自己的存储空间，用来存储自己的程序代码和数据，包括只读区（代码和只读数据），可读可写数据区（初始化数据和未初始化数据），动态的堆区和栈区

进程的引入为程序提供了以下两方面的抽象。一个独立的逻辑控制流和一个私有的虚拟内存地址。每个进程拥有一个独立的逻辑，使得程序员以为程序似在执行过程中独占处理器。一个私有的虚拟地址空间，使得程序员以为程序在执行过程中独占存储器。

为了实现以上两方面的抽象，操作系统必须提供一整套管理机制，包括处理器调度、进程上下文切换、虚拟存储管理等。

逻辑控制流

一个可执行目标文件被加载并启动执行后，就成为一个进程。他们代码段中的每一条指令都有一个确定的地址，在这些指令的执行过程中，会形成一个指令执行的地址序列，对于确定的输入数据，其指令的地址序列也是确定的。这个确定的指令执行地址序列被称为进程的逻辑控制流。

对于一个具有单核处理器的系统，如果有多个进程运行，这些进程会轮流使用处理器，处理器的物理控制流是由多个逻辑控制流组成。
多个逻辑控制流

图中可以看出有些进程的逻辑控制流在时间上有交错，通常把这种不同进程的逻辑控制流在时间上交错或者重叠称为并发。而并行则是并发执行的一个特例，我们称两个进程是并行的，是指他们并发的运行在不同的处理器或者处理器核中。

连续执行同一个进程的时间段称为时间片，每个时间片结束时，通过进程的上下文切换，换一个新的进程到处理器上执行，开始一个新的时间片，这个过程称为时间片轮转处理器调度。

进程的上下文切换

实现不同进程中指令交替执行的机制称为进程的上下文切换。

进程的物理实体（代码和数据）和支持进程运行的环境合称为进程的上下文，可以细分为

  • 由用户进程的程序块，数据块，运行时的堆和用户栈等组成的用户空间信息被称为用户级上下文。
  • 进程表示信息，进程现场信息，进程控制信息和系统内核堆栈组成的内核空间信息被称为系统级上下文。
  • 处理器中各个寄存器的内存被称为寄存器上下文。

用户级上下文和系统级上下文地址空间一起构成了一个进程的整个存储器映像。进程控制信息包含各种内核数据结构，如有关进程信息的进程表，页表，文件表等。
进程的存储映像

上下文切换发生在操作系统调度一个新进程到处理器上运行，他需要完成以下三件事

  • 将当前进程的寄存器上下文保存到当前进程的系统级上下文的现场信息中
  • 将新进程系统上下文中的现场信息作为新的寄存器上下文恢复到处理器的各个寄存器中
  • 将控制转移到新进程执行

一个重要的上下文信息是 PC，当前进程被打断的断点处的 PC 作为寄存器上下文的一部分被保存在进程现场信息中。

进程的私有地址空间

虚拟地址空间映像

整个虚拟地址空间分为两大部分。内核虚拟存储空间（简称内核空间）和进程虚拟内存空间（简称用户空间）。在采用虚拟存储机制的系统中，每个程序的可执行目标文件在装入时都被映射到同样的虚拟地址空间上，即所有用户进程的虚拟地址空间是一致的，只是在相应的制度区域和可读写数据区域中映射的信息不同而已。

linux 将用户空间对应的进程虚拟存储空间组织成若干“区域”的集合，
内核为每个进程维护了一个进程描述符，记录或者指向内核运行该进程所需要的所有信息，如进程 pid，指向用户栈的指针，可执行目标文件的文件名，程序计数器 PC 等。

程序的加载和运行

当启动一个可以行目标文件执行时，首先会通过某种方式调出常驻内存的一个称为加载器的操作系统程序来处理。在 UNIX/Linux 系统中，可以通过 execve() 函数来启动加载器，其作用是在当前进程的上下文中加载并且运行一个新程序。

异常和中断

除了时间片到，当前进程的执行被新进程打断，还有用户按下 CTRL+C，当前执行执行中发生了不能使指令执行的意外事件，IO 设备完成了系统交给的任务需要进一步处理，这些特殊事件统称为异常或者中断。
当发生异常或者终端，正在执行进程的逻辑控制流被打断，CPU 转到具体的特殊处理事件的内核程序去执行。他与上下文切换有一个明显的不同：上下文切换后 CPU 执行另一个用户进程，但是，中断或异常处理程序执行的代码不是一个进程，而是一个内核控制路径，它代表异常或终端发生时正在运行的当前进程在内核态执行的一个独立的指令序列。作为一个内核控制路径，他比进程更轻，其上下文信息比一个进程的上下文信息少得多。

基本概念

异常是在 CPU 内部执行时发生的，中断是 CPU 外部的 IO 设备向 CPU 发出的请求，通常称异常为内部异常，而称中断为外部中断。

中断处理过程

大致处理流程如下：当 CPU 在执行当前程序或任务的第 i 条指令时检测到一个异常事件，或者在执行第 i 条指令后发现有一个中断请求信息，CPU 会打断当前用户进程，然后转到相应的异常或中断处理程序去执行。如果该处理程序能解决相应问题，则在该处理程序的最后，CPU 通过执行“异常/中断返回指令”回到被打断的用户进程的第 i 条指令或第 i+1 条指令继续执行。若异常或中断处理程序发现是不可恢复的知名错误，则中止用户进程。通常情况下，对于异常和中断事件的具体处理过程全部由操作系统（可能包括驱动程序）软件来完成。

异常的分类

intel 将内部异常分为三类

故障

故障是在引起故障的指令被启动后但未结束执行时 CPU 检测到的一类与指令执行相关的意外事件。这种意外事件有些可以回复，有些不能回复。如指令译码出现的非法操作码；取指令或者取数据时发生页故障，执行触发操作时发现除数为 0.

对于像溢出和非法操作码等这类故障，因为无法通过异常处理程序回复，会调用内核的 abort 例程，以中止发生故障的当前进程。

对于页故障。cpu 在指令执行过程中需要访问存储器，首先进行地址转换，在查页表进行地址转换时，判断相应页表项中的有效位是否是 1，并且确定是否地址越界或访问越权，如果检测到有效位不为 1 或者地址越界或者访问越权，都会产生页故障异常。页故障异常包含多种不同情况：处理程序首先检测是否发生地址越界或访问越权，如果是的话，故障不可恢复，否则是缺陷故障，可通过从磁盘读入页面来恢复。Linux 中不可恢复的访存故障（地址越界和访问越权）都称为段故障。

陷阱

陷阱也成为自陷或者陷入，与故障等其他异常事件不同，是预先安排的一种异常事件，就像预先设定的陷阱一样，当执行到陷阱指令，CPU 就调出特定的程序进行相应的处理，处理结束后返回到陷阱指令的下一条指令执行。

陷阱的重要作之一是在用户程序和内核之间提供一个像过程调用一样的接口，这个接口称为系统调用。操作系统给每个服务编一个号，称为系统调用号，每个服务功能通过一个对应的系统调用服务例程提供。如在 linux 中就提供了创建子线程（fork），读文件（read），加载并且运行新程序（execve）等服务功能。

用于程序调试的断点设置也是一种陷阱指令。

在 IA-32 中，陷阱指令引擎的异常称为编程异常，这些指令包括 INT n，int 3，into（溢出检查），bound（地址越界检查）,通常将 INT n 称为软中断指令，该指令引起的异常通常也称为软中断。在 IA-32/Linux 中可以使用快速系统调用指令 sysenter 或者软中断指令 int $0x80 进行系统调用。

终止

如果在执行指令的过程中发生了严重错误，如控制器出现问题，访问 DRAM 或者 SRAM 时发生校验错误等，则程序无法继续执行，只好终止发生问题的进程。

中断的分类

中断 是由外部 IO 设备请求处理器进行的一种信号。他不是由当前执行的指令引起的，外部 IO 设备通过特定的中断请求信号线向 CPU 提出中断申请。CPU 在执行指令过程中，每执行一条指令就查看中断请求引脚，如果中断请求引脚的信号有效，则进入中断响应周期。在中断响应周期中，CPU 先将当前 PC 值和当前机器状态保存到栈中，并设置成为关中断状态，然后从数据总线读取中断类型号，根据中断类型号跳转到对应的中断服务程序执行。中断响应过程由硬件完成，而中断服务程序执行具体的中断处理工作，中断处理完成后，再回到被打断程序的断点处继续执行。

外部中断的处理过程

可屏蔽中断

是指通过可屏蔽中断请求线INTR 向 CPU 进行请求的中断，主要来自 IO 设备的中断请求。CPU 可以通过在中断控制器中设置相应的屏蔽字来屏蔽他或者不屏蔽他。若一个 IO 设备的中断请求被屏蔽，他的中断请求信号不会被送到 CPU。

不可屏蔽中断

通常是非常紧急的硬件故障，通过专门的不可屏蔽中断请求线NMI 向 CPU 发出中断请求。

异常和中断的响应过程

CPU 从检测到异常或中断事件，到调出响应的异常或中断处理程序开始执行，整个过程称为异常和中断的响应。主要分为以下三个步骤：

  • 保护断点和程序状态
  • 关中断
  • 识别异常和中断事件并转到响应处理程序执行

保护断点和程序状态

对于不同的异常事件，其返回地址不同。如却也故障异常的断点是发生页故障的当前指令的地址。陷阱的断点是陷阱指令后面一条指令的地址。

为了能够支持异常或者中断的嵌套处理，大多数处理器将断点保存到栈中，如 IA-32 处理器的断点被保存到栈中，如果系统不支持桥套处理，则可以将断点保存到特定寄存器中。MIPS 处理器用 EPC 寄存器专门存放断点，其 CPU 用于中断的开销较小。

被中断时源程序状态（如产生的各种标志信息，允许自陷标志等）都必须保存起来。每个正在运行程序的状态信息存放在一个专门的寄存器中，这些专门寄存器统称为程序状态字寄存器（PSWR），存放在 PSWR 中的信息称为程序状态字。

关中断

应有一种机制来禁止在处理异常或中断时再响应新的异常或中断，通常通过设置中断允许位来实现。

识别异常和中断事件并转到响应处理程序执行

在调出异常和中断你处理程序之前，必须知道发生了什么异常或者那个 IO 设备发出了中断请求。一般来说，内部异常事件和外部中断源的识别方式不同，大多数处理器会将二者分开来处理。

内部异常事件的识别很简单，只要 CPU 在执行期间把检测到的事件对应的异常类型或者表示异常类型的信息记录到特定的内部寄存器中即可。

外部中断源的识别比较复杂，只能通过在每条指令执行完成后，取下条指令之前去查询是否有中断请求。通常 CPU 通过采样对应的中断请求引脚来进行查询。但是到底是那个 IO 设备发出的请求，还需要进一步识别。

异常中断的识别可以采用软件识别和硬件识别两种方式。

软件识别是指，CPU 中设置一个原因寄存器，该寄存器中有一些标识异常原因或终端类型的标志信息。操作系统使用一个统一的异常或中断查询程序，按一定的优先级顺序查询原因寄存器，先查询到的先处理。MIPS 采用软件识别方式

硬件识别方式称为向量中断方式，这种方式下，异常或中断处理程序的首地址称为中断向量，所有中断向量存放在一个表中，称为中断向量表。每个异常和中断都被设定一个中断类型号，中断向量存放的位置与对应的中断类型号相关。可以根据类型号快速找到对应的处理程序。IA-32 中的异常和中断识别就采用这种方式。

其他

BIOS（Basic Input/Output System）是基本输入/输出系统的简称

Intel 从奔二处理器开始，引入了指令 sysenter 和 sysexit，sysenter 被称为快速系统调用指令，他提供了从用户态到内核态的快速切换方式。

页的大小是 4kb，当对于页起始地址的发起第一次访问时，会发生缺页异常。

发表于 更新于 分类于   |   字数统计: 1.4k(字)   |   阅读时长: 6(分)

概念

二叉搜索树（Binary Search Tree）是一种可以在 O(logN) 复杂度做查找，插入和删除的操作。

二叉搜索树是一种满足以下特殊性质的二叉树。

  • 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
  • 若右子树不空，则右子树上所有结点的值均小于或等于它的根结点的值
  • 左右子树均为二叉搜索树

二叉搜索树包含三种基本操作。其流程如下。

查找操作

  • 若当前节点为 NULL，返回 false
  • 若查找的值小于当前节点的值，则递归搜索左子树
  • 若查找的值大于当前节点的值，则递归搜索右子树
  • 若查找的值等于当前节点的值，则返回 true

插入操作

  • 若当前节点为 NULL，用插入的值构建新节点插入到当前位置
  • 若插入的值小于当前节点的值，则在左子树上执行插入操作
  • 若插入的值大于当前节点的值，则在右子树上执行插入操作

删除操作

  • 若当前节点为 NULL，返回 false
  • 若删除的值小于当前节点的值，则在左子树上执行删除操作
  • 若删除的值大于当前节点的值，则在右子树上执行删除操作
  • 若删除的值等于当前节点的值，这里又分为多种情况
    • 若当前节点左子树为空，则直接将右子树接上来
    • 若当前节点右子树为空，则直接将左子树接上来
    • 否则，查找左子树中最大的值（或者右子树中最小的值），与当前节点的值进行交换，然后删除被交换的节点，这里想一下就可以明白，左子树最大的数值移动到当前节点的位置，因为它是左子树中最大的数值，所以它一定大于左子树中其他值，同时也一定小于右子树中所有值，这样操作后仍然满足 BST 的性质。

根据二叉搜索树的性质，中序遍历二叉搜索树，得到的一定是一个有序的数列。所以用二叉搜索树进行排序，时间复杂度为 O(NlogN)

用法

以下内容来自洛谷日报

这样一种数据结构，支持找前驱与后继，还可以按排名与按数值查找

找前驱

所谓前驱，就是小于 x 的最大的数，所以前驱一定比 x 小
其实找前驱，就是从根节点开始，递归子树，如果你要找的数小于当前节点，就找他的左子树，反之找他的右子树，直到没有可以找的为止。

按排名找值

再节点维护一个 size 信息，表示当前位置开始的树的节点数量，则找排名为 k 的节点，先看左子树的 size+1 是否大于等于 k，若大于，则在左子树中查找 排名为 k-1 的节点。否则，查询右树中排名为 k-size-1 的节点。

按值找排名

按值找排名时，从根开始，如果该位置的值小于要查询的值，就找他的右子树，同时记住他左子树的大小，如果小于，就查询他的左子树，直到大小相等，他的排名就是该点左子树的大小加上一路上比他小的节点个数再加上 1。

代码

以下是 BST 基础功能的 C++ 实现的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#include <sstream>
using namespace std;
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
template <typename T>
struct node
{
    T val;
    node *lch, *rch;
    node(T val) : val(val), lch(NULL), rch(NULL) {}
};

template <typename T>
struct bst
{
    typedef node<T> node;

private:
    node *root;

public:
    bst() : root(NULL) {}
    // 插入操作
    bool insert(const T &val)
    {
        return _insert(root, val);
    }
    bool _insert(node *&root, const T &val)
    {
        if (root == NULL)
        {
            root = new node(val);
            return true;
        }
        if (val < root->val)
        {
            return _insert(root->lch, val);
        }
        else
        {
            return _insert(root->rch, val);
        }
    }
    // 查找操作
    bool find(T val)
    {
        return _find(root, val);
    }
    bool _find(node *root, const T &val)
    {
        if (root == NULL)
        {
            return NULL;
        }
        else if (val < root->val)
        {
            return _find(root->lch);
        }
        else if (val > root->val)
        {
            return _find(root->rch);
        }
        else
        {
            return root;
        }
    }
    bool remove(T val)
    {
        return _remove(root, val);
    }
    bool _remove(node *&root, T val)
    {
        if (root == NULL)
        {
            return false;
        }
        else if (val < root->val)
        {
            return _remove(root->lch, val);
        }
        else if (val > root->val)
        {
            return _remove(root->rch, val);
        }
        else
        {
            if (root->lch == NULL)
            {
                node *del = root;
                root = root->rch;
                delete del;
                return true;
            }
            else if (root->rch == NULL)
            {
                node *del = root;
                root = root->lch;
                delete del;
                return true;
            }
            else
            {
                // 找右子树中值最小的
                node *rightMin = root->rch->lch;
                while (rightMin)
                {
                    rightMin = rightMin->lch;
                }
                // 交换之后，右子树仍然满足 bst 性质
                swap(root->val, rightMin->val);
                _remove(root->rch, rightMin->val);
                return true;
            }
        }
    }
    void output()
    {
        _output(root);
    }
    void _output(node *root)
    {
        if (root == NULL)
        {
            return;
        }
        _output(root->lch);
        cout << root->val << endl;
        _output(root->rch);
    }
};
int main()
{
    bst<int> b;
    b.insert(1);
    b.insert(3);
    b.insert(2);
    b.insert(10);
    b.insert(8);
    b.remove(2);
    b.insert(4);
    b.remove(3);
    b.output();
}

发表于 更新于 分类于   |   字数统计: 3k(字)   |   阅读时长: 11(分)

chapter3 流，元素与基本尺寸

外在盒子与内在盒子-外在盒子负责元素是可以一行显示,还是只能换行显示;内在盒子负责宽高、内容呈现什么的。内在盒子专业的名称是“容器盒子”。y 属性值是 inline-block 的元素既能和图文一行显示,又能直接设置 width/height。

width:auto 的四种表现

  • 充分利用可用空间，即 fill-available， 4 。比方说,<div>;、 <p>;这些元素的宽度默认是 100% 于父级容器的。
  • 收缩与包裹。典型代表就是浮动、绝对定位、inline-block 元素或 table 元素,
    英文称为 shrink-to-fit,可简单理解为“包裹性”。CSS3 中的 fit-content 指的就是这种宽度表现。
  • 收缩到最小。这个最容易出现在 table-layout 为 auto 的表格中,
  • 超出容器限制。除非有明确的 width 相关设置,否则上面 3 种情况尺寸都不会主动
    超过父级容器宽度的,但是存在一些特殊情况。例如,内容很长的连续的英文和数字,或者内联
    元素被设置了 white-space:nowarp。

唯一的外部尺寸是 div 的宽，外部尺寸是指宽度由外部元素决定

外部尺寸与流体特性

正常流宽度

正常填充满盒子。

格式化宽度

格式化宽度仅出现在“绝对定位模型”中,也就是出现在 position 属性值为 absolute 或 fixed 的元素中。在默认情况下,绝对定位元素的宽度表现是“包裹性”,宽度由于内部尺寸决定。但有一种情况例外。对于非替换元素，,当 left/top 或 top/bottom 对立方位的属性值同时存在的时候,元素的宽度表现为“格式化宽度”,其宽度大小相对于最近的具有定位特性
(position 属性值不是 static)的祖先元素计算。

内部尺寸与流体特性

包裹性

自适应性 元素尺寸是元素尺寸由内部元素决定,但永远小于“包含块”容器的尺寸。因此,对于一个元素,如果其 display 属性值是 inline-block,那么即使其里面内容再多,只要是正常文本,宽度也不会超过容器。

文字少的时候居中显示,文字超过一行的时候居左显示

1
2
3
4
5
6
7
.box {
  text-align: center;
}
.content {
  display: inline-block;
  text-align: left;
}

首选最小宽度 对于东亚文字，最小宽度为每个字的宽度，西方文字的最小宽度是由特定的连续的英文字符单元决定的，利用首选最小宽度可以实现

宽度分离原则

width 属性不与 padding/border 共存，更好的方式是使用 box-sizing:border-box

1
2
3
4
5
6
7
8
.father {
  width: 180px;
}
.son {
  margin: 0 20px;
  padding: 20px;
  border: 1px solid;
}

height:auto

对于 height 属性,如果父元素 height 为 auto,只要子元素在文档流中,其百分比值完全就被忽略了

如果包含块的高度没有显式指定(即高度由内容决定),并且该元素不是绝对定位,则计算值为 auto，auto 无法进行百分比计算

height:100% 的两种计算，绝对定位的宽高百分比计算是相对于 padding box ，,非绝对定位元素则是相对于 content box 计算的。

min-width/max-width

1
2
3
4
img {
  max-width: 100%;
  height: auto !important;
}

height:auto 是必需的,否则,如果原始图片有设定 height, max-width 生效的时候,图片就会被水平压缩。

max-*初始值是 none，min-*初始值是 auto

数值变化无动画，需要设置初始值为 0

1
2
3
4
5
6
7
.box {
  min-height: 0;
  transition: min-height 0.3s;
}
.box:hover {
  min-height: 300px;
}

max-*会覆盖 !important 的 width/height

::selection 选择器匹配被用户选取的选取是部分。即对选中文本的操作。
只能向 ::selection 选择器应用少量 CSS 属性：color、background、cursor 以及 outline。

chapter4 盒尺寸四大家族

content 与替换元素

<img>、<object>、<video>、<iframe>或者表单元素<textarea>和<input>都是典型的替换元素

vertical-align 在替换元素的基线定义为元素的下边缘

<select> 也是替换元素

<input>和<button>按钮的区别在钮默认的 white-space 值不一样,前者是 pre,后者是 normal

透明图片占位的替代方法

1
2
3
4
5
6
img {
  visibility: hidden;
}
img[src] {
  visibility: visible;
}

对于 Firefox 浏览器,src 缺省的\不是替换元素,而是一个普通的内联元素,所以使用的就不是替换元素的尺寸规则,而是类似\的内联元素尺寸规则,宽高会无效。因此可以在 CSS 重置时加上下面一条

1
2
3
img {
  display: inline-block;
}
  • :before,:after 伪元素是非替换元素，其 content 属性若显示图片则显示的是图片的固有尺寸，不会因 width 和 height 更改
  • 基于伪元素的图片内容生成技术 链接
  • ,使用 content 属性,我们还可以让普通标签元素变成替换元素。一般网站的标志使用的是 h1 标签，可以用 content 改变图片
  • 使用 content 属性生成的文本无法选中，无法复制，像设置了 user-select:none 一样
  • :empty 伪元素依然会选取 有 content 属性的元素
  • 动态加载效果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
dot {
  display: inline-block;
  height: 1em;
  line-height: 1;
  text-align: left;
  vertical-align: -0.25em;
  overflow: hidden;
}
dot::before {
  display: block;
  content: "...\A..\A.";
  white-space: pre-wrap;
  animation: dot 3s infinite step-start both;
}
@keyframes dot {
  33% {
    transform: translateY(-2em);
  }
  66% {
    transform: translateY(-1em);
  }
}

padding 属性

  • 内联的元素设置垂直 padding 依然有效果，如果父元素设置 overflow: auto，会显示滚动条。id 锚点元素可以设置为内联元素然后设置 padding-top 使得定位位置偏下
  • 实际上,对于非替换元素的内联元素,不仅 padding 不会加入行盒高度的计算,margin 和 border 也都是如此,都是不计算高度,但实际上在内联盒周围发生了渲染。
  • padding 的百分比数值无论水平竖直都是相对父元素宽度计算的

margin 与元素尺寸以及相关布局

  • 只有元素是“充分利用可用空间”状态的时候,margin 才可以改变元素的可视尺寸。因为只要宽度设定,margin 就无法改变元素尺寸。对于水平排列的列表，采用 float 方案，可以在 ul 设置负的 margin 数值，来增加可用宽度。
  • 由于 Firefox 和 Chrome 浏览器对于子元素触发滚动条的方式不一样，滚动容器底部留白使用 padding 是不推荐的，可以接触 margin 的外部尺寸特性来实现底部留白
  • 两栏等高
1
2
3
4
5
6
7
8
.column-box {
  overflow: hidden;
}
.column-left,
.column-right {
  margin-bottom: -9999px;
  padding-bottom: 9999px;
}

视觉层多了 9999px 高度可以使用的背景色，当任一栏的高度增加时，父元素总的高度增加

  • margin 的百分比数值无论水平竖直都是相对父元素宽度计算的
  • margin 合并的 3 种场景
    • 相邻兄弟元素 margin 合并
    • 父级和第一个/最后一个子元素
    • 空块级元素的 margin 合并
  • margin 合并的计算规则 “正正取大值”
    “正负值相加”
    “负负最负值”
  • 由于 css 中 margin 初始值是 0，实现块级元素右对齐可以使用 margin-left:auto
  • 实现块级元素垂直居中 绝对定位元素的格式化高度即使父元素 height:auto 也是支持的,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.father {
  width: 300px;
  height: 150px;
  background-color: #f0f3f9;
  position: relative;
}
.son {
  position: absolute;
  top: 0;
  right: 0;
  bottom: 0;
  left: 0;
  width: 200px;
  height: 100px;
  background-color: #cd0000;
  margin: auto;
}
  • margin 无效
    • display 计算值 inline 的非替换元素的垂直 margin 是无效的
    • 表格中的和元素或者设置 display 计算值是 table-cell 或 table-row 的 margin 是无效的
    • margin 合并的时候,更改 margin 值可能是没有效果的
    • 绝对定位元素非定位方位的 margin 值“无效”
    • 定高容器的子元素的 margin-bottom 或者宽度定死的子元素的 margin-right 的失效

border 属性

  • border-width 不支持半分比
  • 透明边框技巧 使用透明 border 增加点击区域
  • 图形构建 三角形效果
  • 登高布局技术 http://demo.cssworld.cn/4/4-4.php

charpter5 内联元素与流

ex 单位 对应 x-height，可用于图标与文字的对齐

line-height 的默认值是 normal,还支持数值、百分比值以及长度值。

无论内联元素 line-height 如何设置,最终父级元素的高度都是由数值大的
那个 line-height 决定的,我称之为“内联元素 line-height 的大值特性”

table-cell 元素设置 vertical-align 垂直对齐的是子元素,但是其作用的并不是子元素,而是 table-cell 元素自身

消除 strut 的影响 图片块状化 设置 lineheight 为 0 fontsize 足够小 图片设置 vertical-align

text-align:justify 文字向两侧对齐，对最后一行无效。

一个 inline-block 元素,如果里面没有内联元素,或者 overflow 不是 visible,
则该元素的基线就是其 margin 底边缘;否则其基线就是元素里面最后一行内联元素的基线。

vertical-align 的百分比数值是按照行高计算的

改造“幽灵空白节点”的基线位置可以使用 font-size：0

基于 vertical-align 属性的水平垂直居中弹框 链接

charpter6 流的破坏与保护

float

  • float 导致的。float 都有哪些有意思的特性呢?具体如下:
    • 包裹性;
    • 块状化并格式化上下文;
    • 破坏文档流;
    • 没有任何 margin 合并;
  • 设定了 float 的 inline-table 计算为 table，其他都为 block
  • clearfix
1
2
3
4
5
.father:after {
  content: "";
  display: table;
  clear: both;
}

bfc

  • 那什么时候会触发 BFC 呢?常见的情况如下:
    • <html>根元素;
    • float 的值不为 none;
    • overflow 的值为 auto、scroll 或 hidden;
    • display 的值为 table-cell、table-caption 和 inline-block 中的任何一个
    • position 的值不为 relative 和 static。
  • 尽量避免滚动容器设置 padding-bottom 值
  • 永远不可能实现一个方向溢出剪裁或滚动,另一方向内容溢出显示的效果

overflow

  • 则当子元素内容超出容器宽度高度限制的时候, 剪裁的边界是 border box 的内边缘,而非 padding,box 的内边缘
1
2
3
4
5
.ell {
  text-overflow: ellipsis;
  white-space: nowrap;
  overflow: hidden;
}

scrollbar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
我们平时开发中只用下面 3 个属性:
::-webkit-scrollbar {
  /* 血槽宽度 */
  width: 8px;
  height: 8px;
}
::-webkit-scrollbar-thumb {
  /* 拖动条 */
  background-color: rgba(0, 0, 0, 0.3);
  border-radius: 6px;
}
::-webkit-scrollbar-track {
  /* 背景槽 */
  background-color: #ddd;
  border-radius: 6px;
}

chapter7 css 层叠规则

!!!z-index 仅可以在定位元素上生效

  • background/border 是装饰属性，浮动和块用作布局，而内联元素作为内容，自然在上面显示

层叠顺序

层叠上下文 background/border
负 z-index
block 块状水平盒子
float 浮动盒子
inline/inline-block 水平盒子
z-index:auto/z-index:0
正 index

层叠上下文

创建

  • 页面根元素称为根层叠上下文
  • z-index 为数值的定位元素是传统层叠上下文

  • css3 属性

    • flex 的布局元素同时 z-index 不为 auto
    • opacity 不为 1
    • mix-blend-mode 不是 normal

  • 定位元素会层叠在普通元素的上面的原因是元素一旦成为定位元素， 其 z-index 就会自动生效，此时其 z-index 就是默认的 auto，也就是 0 级别。

  • opacity 动画问题，当 opacity 不为 1 的时候，其具有层叠上下文 z-index:auto，导致其显示于文字之上，解决方法是设置文字的 z-index 为正数值

负 index 应用

  • 可访问性隐藏，可以隐藏元素，只需要层叠上下文内某一个父元素加背景色