SGI STL-algorithms 介绍分析 11

算法分析和复杂度表示O()

算法复杂度分析:时间和空间。
Big-Oh表示法,如果有任何常数c和N0,使得当N>=N0时,T(N)<=cF(N),那么可将T(N)的复杂度表示为O(F(N))
Big-Oh被普遍运用,但不适合标记数据量小的情况。

算法总览 质变算法 非质变算法

质变算法会改变操作对象的值。
非质变算法不改变操作对象的值。

STL算法的一般形式

所有泛型算法前两个参数都是一对迭代器(iterator),通常称为first和last,用以标识算法的操作区间。STL习惯采用前闭后开区间表示法[first, last),表示first到last(不含last)之间的所有元素。
[first, last)必须可以支持operator++,从first到last。
迭代器分为五类,每个STL算法的申明都表现出其所需要的最低程度的迭代器类型。
许多STL算法不只支持一个版本,其中某个版本采用缺省运算行为,另一个版本提供额外参数,允许外界传入仿函数(functor),以便采用其它策略。
所有数值算法实现于SGI<stl_numeric.h>,用户使用必须包含<numeric> ,其它STL算法实现于SGI的<stl_algo.h><stl_algobase.h>,用户使用需要包含<algorithm>

STL算法泛化过程

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
//该算法暴露令容器过多实现细节,太过依附特定容器。
int *find(int *arrayHead, int arraySize, int value)
{
for(int i=0; i<arraySize; ++i)
{
if(arrayHead[i] == value)
{
break;
}
}
return &(attayHead[i]);
}
//该算法只能针对int*数组
int *find(int *begin, int *end, int value)
{
while(begin!=end && *begin!=value)
{
++begin;
}
return begin;
}
//该算法将传值改为传引用,使用operator!= operator* operator++,但只能对指针类型使用,可改造使普通对象重载操作符也可使用该算法。
template<typename T>
T *find(T *begin, T *end, const T& value)
{
while(begin!=end && *begin!=value)
{
++begin;
}
return begin;
}
//最终形式
template<typename Iterator, typename T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
while(begin!=end && *begin!=value)
{
++begin;
}
return begin;
}