发表于 |

异常处理

Python中使用try...except...finally...来处理异常。简单的栗子：

1
2
3
4
5
6
try:
    print('try...')
except ZeroDivisionError as e:
    print('except:', e)
finally:
    print('finally...')

如果某段代码出现错误，可以使用try来包含这段代码，如果执行出错，则后续代码则不会被执行，而是直接跳转到错误处理代码，即except语句块。如果有finally语句块，则执行finally语句块。

在异常处理的流程当中，try语句中如果没有错误，则except一定不会被执行，如果有finally语句块（也可以没有），一定会会执行finally语句块。

可以有多个except语句，来处理不同类型的错误，如下面int()函数可能会抛出ValueError错误，所以使用except捕获ValueError。如果没有错误发生，可以再except语句块后面添加一个else，当没有错误发生时，自动执行else语句：

1
2
3
4
5
6
7
8
9
10
11
try:
    r = 10 / int('2')
except ValueError as e:
    print('ValueError:', e)
except ZeroDivisionError as e:
    print('ZeroDivisionError:', e)
else:
    print('no error!')
finally:
    print('finally...')
print('END')

Python的错误类型都继承自BaseException，它不仅仅能捕获该类型错误，还能将其子类也捕获。比如：

1
2
3
4
5
6
try:
    foo()
except ValueError as e:
    print('ValueError')
except UnicodeError as e:
    print('UnicodeError')

第二个except永远也不会执行，因为UnicodeError是ValueError的子类。该错误只能被第一个except捕获。官方文档描述了有关错误类型的继承关系。

try...except...可以跨多层调用，比如下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
def foo(s):
    return 10 / int(s)

def bar(s):
    return foo(s) * 2

def main():
    try:
        bar('0')
    except Exception as e:
        print('Error:', e)
    finally:
        print('finally...')

不需要再每个地方都捕获错误，只要在合适的层次去捕获错误就可以了。

如果没有捕获错误，它就会一直上抛，最后被Python解释器捕获，打印一个错误信息，然后程序退出。

Python内置的logging模块可以非常容易的记录错误信息，同时，让程序继续执行下去。程序打印完错误信息后会继续执行，并正常退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import logging

def foo(s):
    return 10 / int(s)

def bar(s):
    return foo(s) * 2

def main():
    try:
        bar('0')
    except Exception as e:
        logging.exception(e)

main()
print('END')

log:

1
2
3
4
5
6
7
8
9
10
11
$ python3 err_logging.py
ERROR:root:division by zero
Traceback (most recent call last):
  File "err_logging.py", line 13, in main
    bar('0')
  File "err_logging.py", line 9, in bar
    return foo(s) * 2
  File "err_logging.py", line 6, in foo
    return 10 / int(s)
ZeroDivisionError: division by zero
END

抛出错误：Python内置函数会抛出很多错误，也可以自己编写函数抛出错误。可以定义一个错误的class，选择继承关系，使用raise语句抛出一个错误的实例：

1
2
3
4
5
6
7
8
9
10
class FooError(ValueError):
    pass

def foo(s):
    n = int(s)
    if n==0:
        raise FooError('invalid value: %s' % s)
    return 10 / n

foo('0')

另外一种处理错误的方式：在捕获错误的时候，打印ValueError!后，又将错误抛出。这是由于这个函数不知道怎么处理这个错误，所以，最恰当的方式是继续上抛，让顶层调用者去处理。raise语句如果不带参数，就会把当前的错误按照原样抛出。此外还可以将except中的raise一个Error，将一种错误转换成另外一种类型：raise ValueError('input error!')。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def foo(s):
    n = int(s)
    if n==0:
        raise ValueError('invalid value: %s' % s)
    return 10 / n

def bar():
    try:
        foo('0')
    except ValueError as e:
        print('ValueError!')
        raise

bar()

发表于 |

函数

匿名函数

匿名函数就是不需要指定函数的名字，比如lambda x: x * x。相当与：

1
2
3
4
5
6
# ':'前的x为函数参数，后面的为返回值
def f(x):
	return x * x
# 同样可以将匿名函数作为返回值返回
def b(x, y):
	return lambda: x * x + y * y

函数参数

可变参数：可以接受所有参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def calc(*numbers):
    sum = 0
    for n in numbers:
        sum = sum + n * n
    return sum

>>> calc(1, 2, 3)
14


# 参数如果是list、tuple、可以直接在前面加 *
>>> nums = [1, 2, 3]
>>> calc(*nums)
14

关键字参数：使用**来定义，允许传入0个或者任意个含参数名的参数，在内部自动组装成dict

1
2
3
4
5
def person(name, age, **kw):
    print('name:', name, 'age:', age, 'other:', kw)

>>> person('Jim', 18, city='Beijing')
name: Jim age: 18 other: {'city': 'Beijing'}

命名关键字参数：可以限制关键字参数的名字，比如只接受某个参数名为关键字参数。命名关键字参数需要用*进行分隔开，*后面的参数被视为关键字参数。

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
# 只接收city和job作为关键字参数。
def person(name, age, *, city, job):
    print(name, age, city, job)
    
>>> person('Jack', 24, city='Beijing', job='Engineer')
Jack 24 Beijing Engineer

# 如果函数定义中已经有了一个可变参数，后面跟着的命名关键字参数就不再需要一个特殊分隔符'*'了：
def person(name, age, *args, city, job):
    print(name, age, args, city, job)
    
命名关键字参数必须传入参数名，这和位置参数不同。如果没有传入参数名，调用将报错：

>>> person('Jack', 24, 'Beijing', 'Engineer')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: person() takes 2 positional arguments but 4 were given


# 命名关键字参数可以有缺省值，从而简化调用：
def person(name, age, *, city='Beijing', job):
    print(name, age, city, job)

# 由于命名关键字参数city具有默认值，调用时，可不传入city参数：
>>> person('Jack', 24, job='Engineer')
Jack 24 Beijing Engineer


# 使用命名关键字参数时，要特别注意，如果没有可变参数，就必须加一个'*'作为特殊分隔符。如果缺少*，Python解释器将无法识别位置参数和命名关键字参数：
def person(name, age, city, job):
    # 缺少 *，city和job被视为位置参数
    pass

递归函数：

在函数内部，可以调用其他函数，如果一个函数在内部调用自身，那么就称作递归函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)
    
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

递归函数的优点：逻辑清晰，但是使用尾递归要注意防止栈溢出。（函数是通过栈这种数据结构来实现的。所以递归调用的次数越多，会导致栈溢出） 解决这个办法是通过尾递归优化。

尾递归优化：当函数返回的时候，调用自身本身，并且return语句不能包含表达式。这样编译器或者就是去就可以把尾递归做优化，使得尾递归不论本身调用多少次，都只占用了一个栈。不会出现栈溢出的情况。上面的例子return n * fact(n - 1)不是一个尾递归。

一个尾递归的例子：

1
2
3
4
5
6
7
8
# 这个函数是一个递归调用，所以并不会导致栈溢出。但是由于Python解释器并没有做尾递归优化，所以仍然会导致栈溢出。
def fact(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

列表生成式：

如果想要生成一个list，可以使用list(range(1, 11))，也可使用for循环，然而使用列表生成式可以很方便的生成list：把要生成的元素x * x放到前面，后面跟着for循环，就可以把list创建出来

1
[x * x for x in range(1, 11)]

后面还可以跟if语句，求偶数的平方：

1
2
>>> [x * x for x in range(1, 11) if x % 2 == 0]
[4, 16, 36, 64, 100]

使用两层循环，使用两个变量来生成list：

1
2
3
4
5
6
>>> [m + n for m in 'ABC' for n in 'XYZ']
['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']

>>> d = {'x': 'A', 'y': 'B', 'z': 'C' }
>>> [k + '=' + v for k, v in d.items()]
['y=B', 'x=A', 'z=C']

生成器与迭代器

生成器:

Python中，一边循环一边计算的机制，称为生成器（generator），只要把一个列表生成式的[]改成()，就创建了generator。

有两种方式创建生成器：

1
2
3
4
5
6
7
8
9
# 列表生成式
[x * x for x in range(10)]
# generator
g =（x * x for x in range(10)）

# 每次调用 next(g)，就可以计算出g的下一个元素的值，直到最后抛出 StopIteration 错误。由于generator是可迭代对象。所以可以用for循环来遍历。
g = (x * x for x in range(10))
for n in g:
    print(n)

第二种方法创建生成器，如果函数定义中包含yield关键字，那么这个函数就是一个生成器。在generator当中，每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行，举个简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def odd():
    print('step 1')
    yield 1
    print('step 2')
    yield(3)
    print('step 3')
    yield(5)
    
>>> o = odd()
>>> next(o)
step 1
1
>>> next(o)
step 2
3
>>> next(o)
step 3
5
>>> next(o)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

在使用for循环调用generator时，如果想要拿到返回值，必须捕获错误，返回值包含在StopIteration的value中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
>>> g = fib(6)
>>> while True:
...     try:
...         x = next(g)
...         print('g:', x)
...     except StopIteration as e:
...         print('Generator return value:', e.value)
...         break
...
g: 1
g: 1
g: 2
g: 3
g: 5
g: 8
Generator return value: done

###迭代器：

Python 中可以直接作用于for循环的对象统称为可迭代对象：Iterable。使用 isinstance() 判断一个对象是否是可迭代对象Iterable

1
2
3
4
from collections import Iterable
isinstance([], Iterable)    
isinstance({}, Iterable)
isinstance(100, Iterable) // False

生成器不但可以作用于 for 循环，而且可以被 next() 函数不断调用返回下一个值，直到最后抛出StopIteration错误，这样可以被next()函数不断返回下一个值得对象称为迭代器：Iterator。

生成器都是Iterator对象，但是list、dict、str是可迭代对象（Iterable），但是不是迭代器Iterator。需要把以上类型变成可迭代对象可以使用 iter() 函数。

1
2
isinstance(iter([]), Iterator)
// True

list、dict、str 等数据不是Iterator的原因是：Python 中的Iterator对象表示的是一个数据流，Iterator对象可以被next()函数不断调用返回下一个数据，直到没有数据时抛出StopIterator错误。可以把这个数据流看做是一个有序的序列，但我们却不能提前直到这个序列的长度，只能不断的调用next()函数事项按需计算下一个数据，所以Iterator的计算是惰性的，只有在需要返回下一个数据的时候才会计算，Iterator甚至可以表示出一个无限大的数据流，例如全体自然数，而使用list是完全不可能存储全体自然数的。

总结：
凡是可以作用于 for 循环的对象都是 Iterable类型。
凡是可以作用于 next()函数的对象都是 Iterator类型，表示一种惰性计算。
集合数据类型如：list、dict、str 等是Iterable但不是Iterator，不过可以通过iter()函数获取Iterator对象。

发表于 |

getInitialState()

组件在安装之前，会调用 getInitialState 来初始化组件的状态，返回值被用作 this.state 的初始值来使用。

注意：在 ES6 中，使用下面方式设置初始化值：

1
2
3
4
5
6
7
class Counter extends React.Component {
  constructor(props) {
    super(props);
    this.state = {count: props.initialCount};
  }
  // ...
}

getDefaultProps()

在创建类的时候调用并缓存，如果该组件没有从父组件获得到 props，可以通过这个方法设置默认值。这个组件创建的值不能够跨实例共享，不会被赋值。

注意：在 ES6 中，可以使用下面的方式设置默认值：

1
2
3
4
5
6
7
class Greeting extends React.Component {
  // ...
}

Greeting.defaultProps = {
  name: 'Mary'
};

propTypes

该 propTypes 对象能够验证传递给组件的 props 的类型：

1
2
3
4
5
6
7
8
9
10
11
12
propTypes: {
  // You can declare that a prop is a specific JS primitive. By default, these
  // are all optional.
  optionalArray: React.PropTypes.array,
  optionalBool: React.PropTypes.bool,
  optionalFunc: React.PropTypes.func,
  optionalNumber: React.PropTypes.number,
  optionalObject: React.PropTypes.object,
  optionalString: React.PropTypes.string,
  optionalSymbol: React.PropTypes.symbol,
  // more ...
}

更多详细信息可参考这里

componentWillMount()

函数原型：

1
void componentWillMount()

这个方法是在组件创建并初始化之后，在第一次 render() 之前调用，可以做一些业务初始化操作，也可以设置㢟状态。这个函数在整个生命周期中只被调用一次。

componentDidMount()

函数原型：

1
void componentDidMount()

组件第一次 render() 之后，只会调用一次。可以再这个函数中操作子组件。需要注意的是，React Native 是先调用子组件的 componentDidMount() ，然后在调用父组件的函数。可以在这个组件当中设置计时器或者网络请求等。调用这个函数完毕后，就等待触发其他事件。

componentWillReceiveProps()

函数原型：

1
2
3
void componentWillReceiveProps(
  object nextProps
)

当组件收到新的 props，就会调用该函数。举个例子：

1
2
3
4
5
6
7
// nextProps 是即将被设置的新的属性，旧的属性还可以通过 this.props 来获取。
// 根据属性的变化，通过 this.setState() 来更新组件状态、这里面更新状态是安全的，并不会触发额外的 render()
componentWillReceiveProps(nextProps) {  
  this.setState({
    likesIncreasing: nextProps.likeCount > this.props.likeCount
  });
}

shouldComponentUpdate()

函数原型：

1
2
3
boolean shouldComponentUpdate(  
  object nextProps, object nextState
)

当组件接收到新的 props 和 state 改变的话，会触发调用该方法。参数 nextProps 和 componentWillReceiveProps 函数一样。参数 nextState 表示组件即将更新的状态值。返回参数决定是否需要更新组件，如果 true 表示更新，继续向下执行。否则表示不更新，直接进入等待状态。

默认情况下，该函数永远返回 true 来保证数据变化的时候 UI 能同步更新，也可以通过检查属性变化前后来决定 UI 是否更新来提高应用性能。

componentWillUpdate()

函数原型：

1
2
3
void componentWillUpdate(
  object nextProps, object nextState
)

shouldComponentUpdate 函数返回 true，并且 nextProps 或者 nextState 发生改变时，就会开始更新组件。

注意：这个方法里面不能调用 this.setState() 来修改状态，这个函数调用之后，就会把 nextProps 和 nextState 分别设置到 this.props 和 this.state 中。紧接着这个函数，就会调用 render() 来更新界面了。

componentDidUpdate()

函数原型：

1
2
3
void componentDidUpdate(  
  object prevProps, object prevState
)

这里已经完成 props 和 state 状态的更新，此函数的输入参数就变成了 prevProps 和 prevState。

componentWillUnmount()

函数原型：

1
void componentWillUnmount()

组件销毁的时候调用，可以做一些组件相关的清理工作，例如取消计时器等。

参考：
https://race604.com/react-native-component-lifecycle/

发表于 |

JS中的函数也是一种对象，但是并不是所有的对象都是函数。函数中拥有 call、apply、bind三个原型方法。call()、apply()可以看作为某个对象的方法，通过调用方法的形式来间接调用函数。

如果函数挂载在一个对象上，作为对象的一个属性，就称它为对象的方法。当通过这个对象来调用函数时，该对象就是此次调用的上下文， 也就是该函数的this的值。

每一个函数都包含一个prototype属性，这个属性是指向一个对象的引用，这个对象称作“原型对象”。 每一个函数都包含不同的原型对象。当将函数用作构造函数的时候，新创建的对象会从原型对象上继承属性。

bind

将函数绑定到某个对象，将返回一个新的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
this.x = 9;
var module = {
  x: 81,
  getX: function() { return this.x; }
};

// 此时 this 的指向是 module
module.getX(); // 返回 81

// 在这种情况下，"this"指向全局作用域
var retrieveX = module.getX;
retrieveX(); // 返回 9,

// 创建一个新函数，将"this"绑定到module对象
// 新手可能会被全局的x变量和module里的属性x所迷惑
var boundGetX = retrieveX.bind(module);
boundGetX(); // 返回 81

再来看一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
var Foo = {
  count: 1,

  getCount: function() {
    return this.count;
  }
};

console.log(Foo.getCount()); // 1

// 此时 func 指向全局变量
var func = Foo.getCount;
console.log(func()); // undefined

那么进行多次 bind() 呢？

1
2
3
4
5
6
7
8
9
10
11
var bar = function() {
  console.log(this.x);
}
var foo = { x:3 }
var sed = { x:4 }
var fiv = { x:5 }

var func = bar.bind(foo).bind(sed);
func(); //?
var func = bar.bind(foo).bind(sed).bind(fiv);
func(); //?

以上输出什么？答案是，两次都仍将输出 3 ，而非期待中的 4 和 5 。原因是，在Javascript中，多次 bind() 是无效的。更深层次的原因， bind() 的实现，相当于使用函数在内部包了一个 call / apply ，第二次 bind() 相当于再包住第一次 bind() ,故第二次以后的 bind 是无法生效的。

其实真的没什么大不了的，看看 bind 的实现就明白了：

1
2
3
4
5
6
Function.prototype.bind = Function.prototype.bind || function(context){
  var self = this;
  return function(){
    return self.apply(context, arguments);
  };
}

call 与 apply

在 JavaScript 中 call、apply 都是为了改变函数运行时的上下文而存在的，也就是说为了改变函数体内部 this 的指向。其语法：fun.call(thisArg[, arg1[, arg2[, ...]]])。可以让 call() 中的对象调用当前对象所拥有的function，可以用这种方法来实现继承：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Foo() {}
Foo.prototype = {
  color: 'red',
  say: function() {
    console.log('this color is: ' + this.color);
  }
}

var foo = new Foo;
foo.say();

// 此方法也想调用 say()，又不想从新定义 say 方法。可以 通过 call、apply 来实现。
bar = {
  color: 'cyan',
}

// 可以看出，call、apply 是为了动态改变 this 而出现的。
foo.say.call(bar);
foo.say.apply(bar);

call 与 apply 的功能是一样的，唯一的不同是接收参数方式不一样：

1
2
3
var func = function() {};
func.call(this, arg1, arg2);
func.apply(this, [arg1, arg2]);

在func函数运行时指定 this。该 this 并不是真正的 this 值，在严格模式下为全局对象(在浏览器中为window)。非严格模式下为 undefined。

三者区别

apply、call、bind比较：

1
2
3
4
5
6
7
8
9
10
11
var obj = { x: 10 };

var foo = {
  getX: function() {
    return this.x;
  }
}

console.log(foo.getX.bind(obj)()); // 10
console.log(foo.getX.call(obj));   // 10
console.log(foo.getX.apply(obj));  // 10

三个输出的都是10，但是注意看使用 bind() 方法的，他后面多了对括号。

也就是说，区别是，当你希望改变上下文环境之后并非立即执行，而是回调执行的时候，使用 bind() 方法。而 apply/call 则会立即执行函数。

再总结一下：

apply 、 call 、bind 三者都是用来改变函数的this对象的指向的；
apply 、 call 、bind 三者第一个参数都是this要指向的对象，也就是想指定的上下文；
apply 、 call 、bind 三者都可以利用后续参数传参；
bind 是返回对应函数，便于稍后调用；apply 、call 则是立即调用 。

参考

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Function/call
https://segmentfault.com/a/1190000000375138?page=1
http://web.jobbole.com/83642/
http://yanhaijing.com/basejs/index.html#sect_var_scope_closures

发表于 |

Class

文件：objc.h

Class 是一个 objc_class 类型的结构体指针，也就是类。id 是 objc_object 类型的指针。如下：

1
2
3
4
5
6
7
8
9
10
11
12
#if !OBJC_TYPES_DEFINED
/// An opaque type that represents an Objective-C class.
typedef struct objc_class *Class;

/// Represents an instance of a class.
struct objc_object {
    Class isa  OBJC_ISA_AVAILABILITY;
};

/// A pointer to an instance of a class.
typedef struct objc_object *id;
#endif

objc_class 定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct objc_class {
    Class isa                                 OBJC_ISA_AVAILABILITY;  // 元类    

#if !__OBJC2__
    Class super_class                         OBJC2_UNAVAILABLE;  // 指向父类，如果该类是 NSObject 或者是 NSProxy，那么 super_class 为 nil。
    const char *name                          OBJC2_UNAVAILABLE;  // 类名
    long version                              OBJC2_UNAVAILABLE;  // 类的版本信息（默认为0，可通过 class_setVersion、class_getVersion）进行修改、读取
    long info                                 OBJC2_UNAVAILABLE;  // 类信息（运行时期使用的一些位标识，如CLS_CLASS (0x1L) 表示该类为普通 class，其中包含实例方法和变量;CLS_META (0x2L) 表示该类为 metaclass，其中包含类方法）
    long instance_size                        OBJC2_UNAVAILABLE;  // 该类的实例变量大小（包括从父类继承下来的实例变量）
    struct objc_ivar_list *ivars              OBJC2_UNAVAILABLE;  // 该类成员变量地址
    struct objc_method_list **methodLists     OBJC2_UNAVAILABLE;  // 方法地址列表，与 info 的一些标志位有关。（如CLS_CLASS (0x1L)，则存储实例方法，如CLS_META (0x2L)，则存储类方法;）
    struct objc_cache *cache                  OBJC2_UNAVAILABLE;  // 缓存方法表，用来提高方法表的查找速度
    struct objc_protocol_list *protocols      OBJC2_UNAVAILABLE;  // 该类声明遵守的协议的列表
#endif

} OBJC2_UNAVAILABLE;

由此可见，类也是一个对象。也就是说类和对象都是对象，分别被称为 类对象、实例对象。

isa：objc_object（实例对象）中的 isa 指针指向类的结构体称为 class（也就是该对象所属的类）。其中存放着普通成员变量与动态方法实例方法(“-“开头)。objc_class 中的 isa 指针指向类结构体称之为 metaclass，其中存放着 static 类型的成员变量与 static 类型的方法(“+” 开头的方法)。

一图胜千言：

所有实例对象的 isa 指针都指向它所属的类，所属的类的 isa 指针指向其 metaclass。所有的 metaclass 都指向其之神。root metaclass是通过继承根类产生的，与根 class 结构体成员一致，不同的是root metaclass 的 isa 指针指向自身。

Objective-C 中的元素

SEL

SEL 是 selector 在 Objective-C 中的表示类型。selector 可以理解为区别方法的 ID。

1
typedef struct objc_selector *SEL;

其定义如下：

1
2
3
4
struct objc_selector {
    char *name;                       OBJC2_UNAVAILABLE;  // 名称
    char *types;                      OBJC2_UNAVAILABLE;  // 类型
};

IMP

IMP 是编译器生成的函数指针。该类型决定调用具体函数的实现。

其定义如下：

1
2
3
4
5
6
/// A pointer to the function of a method implementation.
#if !OBJC_OLD_DISPATCH_PROTOTYPES
typedef void (*IMP)(void /* id, SEL, ... */ );
#else
typedef id (*IMP)(id, SEL, ...);
#endif

Method

Method 代表类中的某个方法的类型。

1
typedef struct objc_method *Method;

其定义如下：

1
2
3
4
5
struct objc_method {
    SEL method_name                   OBJC2_UNAVAILABLE; // 方法名
    char *method_types                OBJC2_UNAVAILABLE; // 方法类型
    IMP method_imp                    OBJC2_UNAVAILABLE; // 方法实现
}

Ivar

Ivar 代表类中实例变量的类型。

1
typedef struct objc_ivar *Ivar;

其定义如下：

1
2
3
4
5
6
7
8
struct objc_ivar {
    char *ivar_name                   OBJC2_UNAVAILABLE; // 变量名
    char *ivar_type                   OBJC2_UNAVAILABLE; // 变量类型
    int ivar_offset                   OBJC2_UNAVAILABLE; // 基地址偏移字节
#ifdef __LP64__
    int space                         OBJC2_UNAVAILABLE; // 占用空间
#endif
}

objc_property_t

objc_property_t 是内置类型属性，其定义如下：

1
typedef struct objc_property *objc_property_t;

还有一个关联属性 objc_property_attribute_t 类型，它是属性的 attribute，包含属性名称、属性编码类型、原子类型/非原子类型等。其定义如下：

1
2
3
4
typedef struct {
    const char *name;   // 名称
    const char *value;  // 值
} objc_property_attribute_t;

Cache

Cache：缓存方法表

1
typedef struct objc_cache *Cache

其定义如下：

1
2
3
4
5
struct objc_cache {
    unsigned int mask                   OBJC2_UNAVAILABLE;  // 指定分配的 cache buckets，在方法查找中，Runtime使用这个字段确定数组的索引位置。
    unsigned int occupied               OBJC2_UNAVAILABLE;  // 实际占用cache buckets的总数。（bucket 等于 NULL，表示缓存没有被占用，被占用的 bucket 可能是不连续的额，这个数组可能会随着时间而增长）
    Method buckets[1]                   OBJC2_UNAVAILABLE;  // objc_msgSend 发送消息的函数。
};

Catagory

Catagory：可以动态为已经存在的类添加新的方法。

1
typedef struct objc_category *Category;

其定义如下：

1
2
3
4
5
6
7
struct objc_category {
    char *category_name                           OBJC2_UNAVAILABLE; // 类别名称
    char *class_name                              OBJC2_UNAVAILABLE; // 类名
    struct objc_method_list *instance_methods     OBJC2_UNAVAILABLE; // 实例方法列表
    struct objc_method_list *class_methods        OBJC2_UNAVAILABLE; // 类方法列表
    struct objc_protocol_list *protocols          OBJC2_UNAVAILABLE; // 协议列表
}

消息传递

在 Objective-C 中，调用某个方法，相当于发送一条消息。会调用 runtime 模块中的 objc_msgSend 函数调用，比如 [self someMethod]; 方法，会转换成 objc_msgSend(self, someMethod)。

消息调用类型还包括以下几种：

  • objc_msgSend_stret：如果带发送的消息返回结构体，可交由此函数处理。
  • objc_msgSend_fpret：消息返回浮点数，
  • objc_msgSend_Super：给父类发送消息，如 [super message:parameter]

更多解释可以查看这里

消息转发

第一步：通过 resolveInstanceMethod: 方法决定是否能在本类中动态添加方法，返回 YES 可以通过 class_addMethod 来动态添加方法，消息得到处理。如果返回 NO，则会启动将消息转发给其他对象。
第二步：通过 forwardingTargetForSelector:，当前接收者有第二次机会处理这个未知的消息，runtime 会询问能否将消息转给其他的接收者来处理。如果返回某个对象则会调用对象的方法，然后结束。反之返回 nil，则进入第三步。
第三步：通过 methodSignatureForSelector:方法签名，如果返回 nil，则消息无法处理。如果返回 methodSignature 则进入下一步。
第四步：通过 forwardInvocation:方法，可以通过 NSInvocation 对象做很多处理，比如修改方法的实现，修改响应对象等。如果方法调用成功，则结束。如果失败，则调用 doesNotRecognizeSelector 方法，如果没有实现这个方法，则程序会崩溃。

完整流程图：

地方

发表于 |

Runtime Versions and Platforms
Interacting with the Runtime
Messaging
Dynamic Method Resolution
Message Forwarding
Type Encodings
Declared Properties

版本

  • iPhone 程序和 Mac OS X v10.5 及以后的系统中的 64 位程序使用的都是 Objective-C 运行时系统的现行版本。
  • Mac OS X 32位系统中使用的是早期版本。

发表于 |

栈的本质是一个线性表，线性表中存在两种存储形式，分为栈的线性存储结构和链式存储结构。

线性存储结构

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
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct {
  ElementType *base;
  ElementType *top;
  int stackSize;
} sqStack;


void initStack(sqStack *s)
{
  s->base = (ElementType *)malloc(STACK_INIT_SIZE * sizeof(ElementType));
  if (!s->base)
  {
    exit(0);
  }

  s->top = s->base; // 最开始，栈顶指向栈底
  s->stackSize = STACK_INIT_SIZE; // 栈的操作
}

// 入栈
void Push(sqStack *s, ElementType e)
{
  // 如果栈満，添加空间
  if (s->top - s->base >= s->stackSize) {
    s->base = (ElementType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElementType));
    if (!s->base) {
      exit(0);
    }

    s->top = s->base + s->stackSize; // 设置栈顶
    s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
  }

  *(s->top) = e;
  s->top++;
}

void Pop(sqStack *s, ElementType *e)
{
  // 空栈
  if (s->top == s->base) return;
  // 栈容量 -1
  *e = *--(s->top);
}

// 清空栈，就是将栈中的元素全部作废，但是栈本身的物理空间并不发生改变
void ClearStack(sqStack *s)
{
  s->top = s->base;
}

void DestoryStack(sqStack *s)
{
  int i, len;
  len = s->stackSize;
  for (i = 0; i < len; i++)
  {
    free(s->base);
    s->base ++;
  }

  s->base = s->top = NULL;
  s->stackSize = 0;
}

// 计算栈的当前容量，也就是计算栈中元素的个数
long StackLen(sqStack s)
{
  return(s.top - s.base);
}

链式存储结构

1
2


发表于 |

线性表

线性表可以用数学方式来定义 (a1, ... ai-1, ai, ai+1, ... an)，其中 ai+1 是 ai 的前驱，ai-1 是 ai 的后缀。当 n=0 的时候，称为空表。

线性结构：顺序存储，比如数组。
链表结构：乱序存储，里面有一个指针指向下一项元素地址，分为数据域（如data1）和指针域（next 指针）如下图：

链表存储结构

线性表的优缺点：

优点：

  • 快速存取表中任意位置的元素。
  • 无需为表示表中元素之间的关系而增加额外的存储空间。

缺点：

  • 插入和删除操作需要移动大量的元素。
  • 当线性表变化比较大的时候，难以确定存储空间的容量。
  • 容易造成存储空间碎片。

链表

数据域存储数据，指针域指向下一个储存节点的地址：

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
typedef struct Node {
  ElemeType data;      // 数据域
  struct Node * next;  // 指针域
} Node, *LinkList;

// 初始化链表
void InitList(LinkList *L)
{
  // 初始化头结点，也就是上图中的 head
  *L = (LinkList)malloc(sizeof(struct Node));
  // 构造空的线性表
  if(!*L)
    exit(OVERFLOW);
  (*L)->next = NULL; // 置空指针域
}

// 销毁链表
void DestroyList(LinkList *L)
{
  LinkList q;
  while(*L)
  {
    q = (*L)->next;
    free(*L);
    *L = q;
  }
}

// 初始条件：线性表L已存在。操作结果：将L重置为空表
void ClearList(LinkList L)
{
  LinkList p,q;
  p = L->next; // p指向第一个结点，然后循环删除
  while(p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL; // 头结点指针域为空
}

// 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
Status IsListEmpty(LinkList L)
{
  return L->next == NULL;
}

// 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int ListLength(LinkList L)
{
  int i=0;
  LinkList p = L->next; // p指向第一个结点
  while(p)
  {
    i++;
    p = p->next;
  }
  return i;
}

// 顺序线性表 L 已存在，1 <= i <= ListLength(L)
// 操作结果，用 e 返回 L 中第 i 个元素的值
Status GetElem(LinkList L, int i, ElemType *e)
{
  int j = 1;
  LinkList p = L->next;
  while(p&&j < i) // 顺指针向后查找，直到p指向第i个元素或p为空
  {
    p = p->next;
    j++;
  }
  if(!p || j>i) // 第i个元素不存在
    return ERROR;
  *e = p->data; // 取第i个元素
  return OK;
}

// 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
// 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
//          若这样的数据元素不存在，则返回值为0
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType,ElemType))
{
  int i = 0;
  LinkList p = L->next;
  while(p)
  {
    i++;
    if(compare(p->data,e)) // 找到这样的数据元素
      return i;
    p=p->next;
  }
  return 0;
}

// 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
//           返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{
  LinkList q, p = L->next;
  while(p->next) // p所指结点有后继
  {
    q = p->next; // q为p的后继
    if(q->data == cur_e)
    {
      *pre_e = p->data;
      return OK;
    }
    p=q; // p向后移
  }
  return INFEASIBLE;
}

// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
//         返回OK;否则操作失败，next_e无定义，返回INFEASIBLE
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
{
  LinkList p = L->next;
  while(p -> next) // p 所指结点有后继
  {
    if(p->data == cur_e)
    {
      *next_e = p->next->data;
      return OK;
    }
    p = p->next;
  }
  return INFEASIBLE;
}

// 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e
Status ListInsert(LinkList L, int i, ElemType e)
{
  int j = 0;
  LinkList p = L, s;
  while(p&&j < i-1) // 寻找第 i-1 个结点
  {
    p = p->next;
    j++;
  }
  if(!p || j > i-1) // i 小于1或者大于表长
    return ERROR;

  s = (LinkList)malloc(sizeof(struct Node)); // 生成新结点
  s->data = e; // 插入 L 中
  s->next = p->next;
  p->next = s;
  return OK;
}

// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
Status ListDelete(LinkList L, int i, ElemType *e)
{
  int j = 0;
  LinkList p = L, q;
  while(p->next && j < i-1) // 寻找第i个结点，并令p指向其前驱
  {
    p = p->next;
    j++;
  }
  if(!p->next || j > i-1) // 删除位置错误
    return ERROR;
  q = p->next; // 删除并释放结点
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
}

// 初始条件：线性表 L 已存在。操作结果：依次对 L 的每个数据元素调用函数 vi()
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
  LinkList p = L->next;
  while(p)
  {
    vi(p->data);
    p = p->next;
  }
  printf("\n");
}

时间复杂度

在操作单链表的过程中，由于算法的时间复杂度取决于 i 的值，因此最坏情况下的时间复杂度为 O(n)，最好的情况下为 O(1)。对于插入或者删除数据越频繁的操作，单链表的效率优势就越明显，因为其操作的是指针。

单链表结构与顺序存储结构时间性能对比：

单链表 顺序结构
查找 O(n) O(1)
删除 O(1) O(n)
插入 O(1) O(n)

空间性能

  • 顺序结构需要分配连续的存储空间，空间分大了造成浪费，分小了会造成溢出。
  • 单链表不需要分配存储空间，元素个数也不受限制。

选取单链表还是顺序结构？

  • 若线性表需要频繁查找，很少进行插入和删除操作，采用顺序存储结构。
  • 若需要频繁的插入和删除时，采用单链表结构。

单链表应用

快速找到未知长度单链表的中间节点。

可以通过遍历单链表的方式来获取其中间节点。其时间复杂度为 O(3L/2)思路如下：

  • 先遍历一遍链表，获取其长度 L。
  • 再次循环到 L/2 处，获取其中间节点。

还有一种更巧妙的方式来解决这个问题，其时间复杂度为O()，利用快慢指针的原理，思路如下：

  • 设置两个指针 *search、*mid，都指向单链表的头结点。
  • 其 *search 的移动速度是 *mid 的两倍。这样当 *search 移动到末尾结点的时候，*mid 指针刚好就在中间了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status GetMidNode(LinkList L, ElemType *e)
{
  LinkList mid, search;
  mid = search = L;
  while (search -> next != NULL)
  {
    if (search -> next -> next != NULL)
    {
      search = search -> next -> next;
      mid = mid -> next;
    }
    else
    {
      search = search -> next;
    }
  }

  *e = mid -> data;

  return OK;
}

发表于 |

静态链表可以给没有指针的编程语言设计一种实现单链表功能的方法。思想非常巧妙。其每个数组中的元素结构是由数据域data和游标cur组成，数据域就是需要存放的数据，游标相当于单链表中的 next 指针。cur中存放该元素的后继在数组中的下标。这种数组描述的链表叫做静态链表。

静态链表必须满足下面两个规则：

  • 数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标。
  • 数组的最后一个元素的 cur 则存放第一个有数值的元素的下标，相当于单链表的头节点作用，当整个链表为空时，则为0，表示无指向。

如下图，cur 代表存放后继元素在数组中的下标。第 0 个下标的元素的 cur 存放备用链表的第一个节点的下标。最后一个元素的 cur 存放第一个有数值元素的下标。这样就构成一个链式存储结构。

现在在已、丁之间插入丙元素。需要将已的 cur 改为 7，丙的 cur 改为 3。这时候，链表中的头的 cur 就应该改为 8。如下图：

如果现在需要删除甲，那么甲处于的位置为空，如果有新的元素待插入，那么此位置将会优先考虑。所以删除的位置称为第一个优先空位。即首元素 cur 为1，末尾元素 cur 为 2。而游标为 2 的位置（参考上图）则指向下一个备用链表下标，即为 8。修改后的链表如下图所示。

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
#include<iostream>
using namespace std;

#define MAXSIZE 100

typedef int ElemType;
/* 线性表的静态链表存储结构 */
typedef struct Node
{
    ElemType data;
    int cur; //为0时表示无指向
} StaticLinkList[MAXSIZE];

/* 将一维数组array中各分量链成一个备用链表，array[0].cur为头指针，"0"表示空指针 */
bool InitList(StaticLinkList array)
{
    cout << "InitList..." << endl;
    for (int i = 0; i < MAXSIZE - 2; i++)
    {
        array[i].cur = i + 1;
    }
    array[MAXSIZE - 2].cur = 0;  /* 最后一个元素也是不可用的，倒数第二个元素的cur为0 */
    array[MAXSIZE - 1].cur = 0;   /* 目前静态链表为空，最后一个元素的cur为0 */

    return true;
}
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SLL(StaticLinkList array)
{
    int k = array[0].cur;
    if (k)
        array[0].cur = array[k].cur;/* 下一个分量用来做备用 */

    return k;
}
/*  将下标为pos的空闲结点回收到备用链表 */
void Free_SLL(StaticLinkList array, int pos)
{
    array[pos].cur = array[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */
    array[0].cur = pos; /* 把要删除的分量下标赋值给第一个元素的cur */
}

int ListLength(StaticLinkList array)
{
    int i = array[MAXSIZE - 1].cur;
    int j = 0;
    while(i)
    {
        i = array[i].cur;
        ++j;
    }
    return j;
}
/*  在array中第pos个元素之前插入新的数据元素Elem  */
bool ListInsert(StaticLinkList array, int pos, ElemType Elem)
{
    cout << "Insert List from pos: " << pos << " Item " << Elem << endl;
    if (pos < 1 || pos > ListLength(array) + 1)
        return false;

    int k = MAXSIZE - 1;
    int i = Malloc_SLL(array); /* 获得空闲分量的下标 */

    if (i)
    {
        array[i].data = Elem;

        for (int l = 1; l <= pos - 1; l++)
            k = array[k].cur;

        array[i].cur = array[k].cur;/* 把第pos个元素之前的cur赋值给新元素的cur */
        array[k].cur = i;/* 把新元素的下标赋值给第pos个元素之前元素的cur */
        return true;
    }

    return false;
}
/*  删除在array中第pos个数据元素   */
bool ListDelete(StaticLinkList array, int pos)
{
    cout << "Delete List from pos: " << pos << endl;
    if (pos < 1 || pos > ListLength(array))
        return false;

    int k = MAXSIZE - 1;

    for (int l = 1; l <= pos - 1; l++)
        k = array[k].cur;

    int j = array[k].cur;
    array[j].cur = array[pos].cur;

    Free_SLL(array, j);

    return true;
}

bool ListTraverse(StaticLinkList array)
{
    cout << "List Traverse : " << endl;
    int k = MAXSIZE - 1;
    while (array[k].cur != 0)
    {
        k = array[k].cur;
        cout << array[k].data << ' ';
    }

    cout << endl;
    return true;
}


int main(void)
{
    StaticLinkList SSL;
    InitList(SSL);
    for (int i = 1; i < 5; i++)
        ListInsert(SSL, i, i);
    ListTraverse(SSL);

    ListDelete(SSL, 3);
    ListTraverse(SSL);
    cout << "List Length : " << ListLength(SSL) << endl;

    return 0;
}

静态链表的优缺点：

优点：

  • 在插入和删除操作时，只移动游标，不需要移动元素。改变了在顺序存储结构中的插入和删除需要移动大量元素的缺点。
    缺点：
  • 失去了顺序存储结构随机存取的特性。
  • 没有解决连续存储分配（数组）带来的表长难以确定的问题。

参考

《大话数据结构》