By

文章目錄
  1. 1. 前言
  2. 2. 欲善其事必先利其器
  3. 3. 数学知识
    1. 3.1. 指数
    2. 3.2. 对数
    3. 3.3. 级数
    4. 3.4. 模运算
    5. 3.5. 证明方法
    6. 3.6. 递归简论
  4. 4. 数据结构
    1. 4.1. 链表
    2. 4.2. 栈
  5. 5. 算法
    1. 5.1. 算法与程序
    2. 5.2. 算法复杂性
      1. 5.2.1. 时间复杂度
      2. 5.2.2. 空间复杂度
    3. 5.3. 程序算法思想
      1. 5.3.1. 递归
      2. 5.3.2. 分治
      3. 5.3.3. 动态规划
      4. 5.3.4. 贪心算法
      5. 5.3.5. 回溯法算法
      6. 5.3.6. 分支限界法
  6. 6. STL
    1. 6.1. STL
    2. 6.2. STL组件
      1. 6.2.1. 容器(Containers)
        1. 6.2.1.1. 容器内的类型和成员
      2. 6.2.2. 迭代器(Iterators)
      3. 6.2.3. 算法(Algorithms)
    3. 6.3. STL内部的错误处理和异常处理
      1. 6.3.1. 错误处理
      2. 6.3.2. 异常处理
    4. 6.4. 扩展STL

前言

写这一篇文章的目的是出于自己一直以来基础都比较弱，特别是数据结构和算法，但数据结构和算法确实程序里很核心的部分，只有了解各种数据结构和算法的基本思想，才能针对实际问题做出最好的选择，写出最优的程序。工作两年多了，但感觉自己再这方面还是依然原地踏步，了解的一知半解。为了避免多年以后还来学习这些本应该在学校学好的知识，从而有了这一次学习计划。

在看了这位博主的我的算法学习之路之后，深深的感受到了数据结构和算法的魅力和重要性。虽然不知道自己还能为游戏梦想坚持多久，但当下，制定一个完整的数据结构和算法的学习计划是当务之急。

现在有点理解别人说过的”编程语言只是工具，编程思想，数据结构和算法才是核心。”

以下学习主要是对于数据结构和算法的回顾和进阶学习计划。准备用C++来写。

参考书籍：
编程语言：
《C++ Primer》Fifth Edition — Stanley B.Lippman Josee Lajoie Barbara E.Moo
《Effective C++》Third Edition — Scott Meyers
最初学习C++是看的《Thinking in C++》和《Professional C++》，但后来看了部分《C++ Primer》之后觉得，这本书在细节方面讲解的更细致到位。而《Effective C++》是从我们平时容易忽略或错误理解的点，以一条条规则的形式，讲述背后的道理，可以作为C++编程指南。

数据结构和算法：
《数据结构与算法 - C语言描述》 — Mark Allen Weiss
数据结构与算法 - C语言描述课后习题在线答案参考
《算法设计与分析》 Third Edition — 王晓东
《Introduction To Algorithm》(算法导论) Third Edition— Thomas H.Cormen & ……
Introduction To Algorithm MIT课程视频

前两者是我在大学时候学习的关于数据结构和算法的书籍，作为基础知识回顾来学习。
第三个在网络上的评价褒贬不一，但作为国外的优秀教材来使用，可以看出是很有分量的，作为进阶学习书籍。最后一个是麻省理工对于算法导论教材的上课视频可以作为学习《Introduction To Algorithm》的学习资料。

编程艺术和思考：
《The Progmatic Programmer》(程序员修炼之道) — Andrew Hunt & David Thomas
此书并非将编程技巧而是讲程序员应该如何去思考，如何高效的开发。

STL深入学习：
《C++标准程序库》
此书虽然比较老，但貌似是C++标准库学习的经典书籍，里面对STL进行基本的讲解学习。
《STL源码剖析》
此书乃侯捷所著，对于STL进行了深入的讲解学习，属于对STL的深入学习的一本参考书籍。

欲善其事必先利其器

单纯学习数据结构和算法是比较枯燥的，算法可视化的神奇网站，这个网站可以让我们在学习数据结构和算法的时候可视化的看到每一步的变化，更加形象生动。

数学知识

指数

Power(X,A) X Power(X,B) = Power(X,A+B)
Power(X,A) / Power(X,B) = Power(X,A-B)

对数

LogA(B) = LogC(B) / LogC(A); C > 0
Log(AB) = Log(A) + Log(B)
Log(A/B) = Log(A) - Log(B)
Log(Power(A,B)) = B X Log(A)
Log(X) < X(X > 0)

级数

1
2
3
4
5
6
 N
 ∑  (Power(2, i)) =  Power(2, N+1) - 1;
i=0
 N
 ∑ (Power(A, i)) = (Power(2, N+1) - 1) / (A - 1)
i=0

模运算

如果N整除A-B,那么A与B模N同余，记为A≡B(mod N)

证明方法

  1. 归纳法
    第一步证明基准情形(对于某些小的值的正确性，比如1)
    第二步，假设直到k也成立
    最后，证明k+1的时候也成立即可
  2. 反证法
    首先假设定力不成立
    然后证明该假设导致的某个已知的性质不成立，从而证明原假设是错误的。

递归简论

基本法则：

  1. 基准情形
    必须要有某些基准的情形，它们不用递归就能求解
  2. 不断推进
    对于那些递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进
  3. 设计法则
    假设所有的递归调用都能运行
  4. 合成效益法则
    在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作

数据结构

抽象数据类型(Abstract data type, ADT)是一些操作的集合。

链表

链表是由一系列不必在内存中向连的结构组成。每一个结构均含有表元素和指向包含该元素后继元的结构的指针。最后一个单元的后继元指向NULL。

链表分类：

  1. 单向链表
    只能从前往后访问节点
    以下实现了简单的单向链表，允许头插入Node，删除第一个满足条件的Node，打印所有成员，判断是否为空，得到Node节点数等。

    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
    #include "stdafx.h"

    template<typename T>
    struct SingleLinkNode
    {
    	T mElement;
    	SingleLinkNode* Next;
    };

    template<typename T>
    class SingleLinkList
    {
    public:
    	SingleLinkList()
    	{
    		mHeadNode = NULL;

    		mLength = 0;
    	}

    	~SingleLinkList()
    	{
    		SingleLinkNode<T> *tempnode;
    		while (mHeadNode != NULL)
    		{
    			tempnode = mHeadNode->Next;
    			delete mHeadNode;
    			mLength--;
    			mHeadNode = tempnode;
    		}
    	}

    	//ADT
    	void FrontInsert(T v)
    	{
    		SingleLinkNode<T> *tempnode = new SingleLinkNode<T>();

    		tempnode->mElement = v;

    		tempnode->Next = mHeadNode;

    		mHeadNode = tempnode;

    		mLength++;
    	}

    	bool IsEmpty()
    	{
    		return mLength;
    	}

    	
    	void Delete(T v)
    	{
    		if (mHeadNode == NULL)
    		{
    			return;
    		}

    		SingleLinkNode<T> *tempnode = mHeadNode;

    		SingleLinkNode<T> *prenode = NULL;

    		bool find = false;

    		while (tempnode != NULL)
    		{
    			//remove first v element
    			if (tempnode->mElement == v)
    			{
    				//when remove first node, move forward mHeadNode
    				if (tempnode == mHeadNode)
    				{
    					mHeadNode = tempnode->Next;
    				}
    				else
    				{
    					prenode->Next = tempnode->Next;
    				}
    				delete tempnode;
    				mLength--;
    				find = true;
    				break;
    			}
    			//Record pre node for later operation
    			prenode = tempnode;
    			tempnode = tempnode->Next;
    		}

    		if (find)
    		{
    			cout << "Delete " << v << " successfully!" << endl;
    		}
    		else
    		{
    			cout << "Delete " << v << " failed! Not find it in list!" << endl;
    		}
    	}

    	int Find(T v)
    	{
    		int position = 0;
    		SingleLinkNode<T> *tempnode = mHeadNode;
    		while (tempnode != NULL)
    		{
    			position++;
    			if (tempnode->mElement == v)
    			{
    				return position;
    			}
    			else
    			{
    				tempnode = tempnode->Next;
    			}
    		}
    		return -1;
    	}

    	SingleLinkNode<T>* GetNodeAt(int position)
    	{
    		if (position < 1 || position > mLength)
    		{
    			cout << position << " Out of range of link list!" << endl;
    			cout << "Current length of link list = " << mLength << endl;
    			cout << "Insert failed!" << endl;
    			return NULL;
    		}
    		else
    		{
    			//链表是非连续的存储方式，所以需要通过循环访问到特定位置
    			SingleLinkNode<T> *tempnode = mHeadNode;

    			if (position == 1)
    			{
    				return mHeadNode;
    			}
    			else
    			{
    				for (int i = 1; i < position; i++)
    				{
    					tempnode = tempnode->Next;
    				}
    				return tempnode;
    			}
    		}
    	}

    	void TraversAll()
    	{
    		SingleLinkNode<T> *tempnode = mHeadNode;
    		while (tempnode != NULL)
    		{
    			cout << tempnode->mElement << endl;
    			tempnode = tempnode->Next;
    		}
    	}

    	int Length()
    	{
    		return mLength;
    	}
    private:
    	SingleLinkNode<T> *mHeadNode;

    	int mLength;
    };

    测试程序：

    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
    #include "stdafx.h"
    #include <vld.h>

    #include "SingleLinkList.h"

    int _tmain(int argc, _TCHAR* argv[])
    {
    	//Single Link List part
    	SingleLinkList<int> *singlelinklist = new SingleLinkList<int>();

    	singlelinklist->FrontInsert(3);
    	singlelinklist->FrontInsert(1);
    	singlelinklist->FrontInsert(4);
    	singlelinklist->FrontInsert(2);

    	singlelinklist->TraversAll();

    	singlelinklist->Delete(1);
    	singlelinklist->Delete(5);

    	singlelinklist->TraversAll();

    	delete singlelinklist;

    	system("pause");
    	return 0;
    }

    可以看到链表的节点是通过SingleLinkNode抽象出来。
    SingleLinkList

  2. 双向链表
    可以从前往后也可以从后往前访问节点
    为了从后往前访问，我们需要改写SingleLinkNode支持从当前Node访问前一Node

    1
    2
    3
    4
    5
    6
    7
    8
    9
    template<typename T>
    struct DoubleLinkNode
    {
    	T mElement;
    	
    	DoubleLinkNode *Pre;

    	DoubleLinkNode *Next;
    };

    同时为了快速从尾部访问，SingleLinkList需要增加mTailNode去指向链表尾部Node，同时支持从尾部插入

    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
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    #include "stdafx.h"

    //DoubleLinkNode definition
    //.....

    template<typename T>
    class DoubleLinkList
    {
    public:
    	DoubleLinkList()
    	{
    		mHeadNode = NULL;

    		mTailNode = NULL;

    		mLength = 0;
    	}

    	~DoubleLinkList()
    	{
    		DoubleLinkNode<T> *tempnode;
    		while (mHeadNode != NULL)
    		{
    			tempnode = mHeadNode->Next;
    			delete mHeadNode;
    			mLength--;
    			mHeadNode = tempnode;
    		}
    	}

    	//ADT
    	void FrontInsert(T v)
    	{
    		DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

    		tempnode->mElement = v;

    		//when insert first element, tail node equals to head node
    		if (mLength == 0)
    		{
    			tempnode->Pre = NULL;
    			tempnode->Next = NULL;
    			mHeadNode = tempnode;
    			mTailNode = mHeadNode;
    		}
    		else
    		{
    			mHeadNode->Pre = tempnode;
    			tempnode->Next = mHeadNode;
    			mHeadNode = tempnode;
    		}

    		mLength++;
    	}

    	void InsertAtPosition(int position, T v)
    	{
    		if (position < 1 || position > mLength + 1)
    		{
    			cout << position << " Out of range of link list!" << endl;
    			cout << "Current length of link list = " << mLength << endl;
    			cout << "Insert failed!" << endl;
    		}
    		//when insert element as first element.
    		else if (position == 1)
    		{
    			FrontInsert(v);
    		}
    		//when insert at final position
    		//when position is larger than length of link list,
    		//we insert it at the end of the link list
    		else if (position == mLength + 1)
    		{
    			TailInsert(v);
    		}
    		//insert element between head and last element
    		else
    		{
    			DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

    			tempnode->mElement = v;

    			DoubleLinkNode<T> *prenode = GetNodeAt(position - 1);

    			if (prenode != NULL)
    			{
    				tempnode->Pre = prenode;

    				tempnode->Next = prenode->Next;

    				prenode->Next->Pre = tempnode;

    				prenode->Next = tempnode;

    				mLength++;
    			}
    		}
    	}

    	void TailInsert(T v)
    	{
    		DoubleLinkNode<T> *tempnode = new DoubleLinkNode<T>();

    		tempnode->mElement = v;

    		//when insert first element, tail node equals to head node
    		if (mLength == 0)
    		{
    			tempnode->Pre = NULL;

    			tempnode->Next = NULL;

    			mHeadNode = tempnode;

    			mTailNode = mHeadNode;
    		}
    		else
    		{
    			tempnode->Pre = mTailNode;

    			tempnode->Next = NULL;

    			mTailNode->Next = tempnode;

    			mTailNode = tempnode;
    		}

    		mLength++;
    	}

    	DoubleLinkNode<T>* GetNodeAt(int position)
    	{
    		if (position < 1 || position > mLength)
    		{
    			cout << position << " Out of range of link list!" << endl;
    			cout << "Current length of link list = " << mLength << endl;
    			cout << "Insert failed!" << endl;
    			return NULL;
    		}
    		else
    		{
    			//链表是非连续的存储方式，所以需要通过循环访问到特定位置
    			DoubleLinkNode<T> *tempnode = mHeadNode;

    			if (position == 1)
    			{
    				return mHeadNode;
    			}
    			else if (position == mLength)
    			{
    				return mTailNode;
    			}
    			else
    			{
    				for (int i = 1; i < position; i++)
    				{
    					tempnode = tempnode->Next;
    				}
    				return tempnode;
    			}
    		}
    	}

    	bool IsEmpty()
    	{
    		return mLength;
    	}

    	void Delete(T v)
    	{
    		if (mHeadNode == NULL)
    		{
    			return;
    		}

    		DoubleLinkNode<T> *tempnode = mHeadNode;

    		DoubleLinkNode<T> *prenode = NULL;

    		bool find = false;

    		while (tempnode != NULL)
    		{
    			//remove first v element
    			if (tempnode->mElement == v)
    			{
    				//when remove first node, move forward mHeadNode
    				if (tempnode == mHeadNode)
    				{
    					if (mLength <= 1)
    					{
    						mHeadNode = NULL;
    						mTailNode = NULL;
    					}
    					else
    					{
    						mHeadNode = tempnode->Next;
    						mHeadNode->Pre = NULL;
    					}
    				}
    				else if (tempnode == mTailNode)
    				{
    					if (mLength <= 1)
    					{
    						mHeadNode = NULL;
    						mTailNode = NULL;
    					}
    					else
    					{
    						mTailNode = prenode;
    						mTailNode->Next = NULL;
    					}
    				}
    				else
    				{
    					prenode->Next = tempnode->Next;
    					tempnode->Next->Pre = prenode;
    				}
    				delete tempnode;
    				mLength--;
    				find = true;
    				break;
    			}
    			//Record pre node for later operation
    			prenode = tempnode;
    			tempnode = tempnode->Next;
    		}

    		if (find)
    		{
    			cout << "Delete " << v << " successfully!" << endl;
    		}
    		else
    		{
    			cout << "Delete " << v << " failed! Not find it in list!" << endl;
    		}
    	}

    	int Find(T v)
    	{
    		int position = 0;
    		DoubleLinkNode<T> *tempnode = mHeadNode;
    		while (tempnode != NULL)
    		{
    			position++;
    			if (tempnode->mElement == v)
    			{
    				return position;
    			}
    			else
    			{
    				tempnode = tempnode->Next;
    			}
    		}
    		return -1;
    	}

    	void TraversAll()
    	{
    		DoubleLinkNode<T> *tempnode = mHeadNode;
    		while (tempnode != NULL)
    		{
    			cout << tempnode->mElement << endl;
    			tempnode = tempnode->Next;
    		}
    	}

    	int Length()
    	{
    		return mLength;
    	}
    private:
    	DoubleLinkNode<T> *mHeadNode;

    	DoubleLinkNode<T> *mTailNode;

    	int mLength;
    };

    测试程序

    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
    #include "stdafx.h"
    #include <vld.h>

    #include "SingleLinkList.h"

    int _tmain(int argc, _TCHAR* argv[])
    {
    	//Double link list part
    	DoubleLinkList<int> *doublelinklist = new DoubleLinkList<int>();

    	doublelinklist->TailInsert(2);
    	doublelinklist->FrontInsert(3);
    	doublelinklist->TailInsert(4);
    	doublelinklist->TailInsert(1);

    	doublelinklist->TraversAll();

    	doublelinklist->Delete(4);

    	cout << "Complete doublelinklist->Delete(4);" << endl;

    	doublelinklist->TraversAll();

    	doublelinklist->InsertAtPosition(3, 6);

    	cout << "Complete doublelinklist->InsertAtPosition(3, 6);" << endl;

    	doublelinklist->TraversAll();

    	doublelinklist->InsertAtPosition(5, 7);

    	cout << "Complete doublelinklist->InsertAtPosition(5, 7);" << endl;

    	doublelinklist->TraversAll();

    	doublelinklist->InsertAtPosition(9, 10);

    	cout << "Complete doublelinklist->InsertAtPosition(9, 10);" << endl;

    	doublelinklist->TraversAll();

    	delete doublelinklist;

    	system("pause");
    	return 0;
    }

    测试结果：
    DoubleLinkList

  3. 循环链表
    双向链表的基础上，可以从头直接访问尾也可以从尾直接访问头
    出于测试目的，为了验证是否至此从尾访问到头部，在TraversAll的方法里，我从第二个节点开始访问进行打印数据直到回到头节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void TraversAll()
    {
    	CircleLinkNode<T> *tempnode = mHeadNode;
    	tempnode = tempnode->Next;
    	cout << mHeadNode->mElement << endl;
    	while (tempnode != mHeadNode)
    	{
    		cout << tempnode->mElement << endl;
    		tempnode = tempnode->Next;
    	}
    }

    因为Head节点的Pre指向Tail节点，Tail节点的Next指向Head，所以这里在析构释放内存的时候需要注意判断条件：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    ~CircleLinkList()
    {
    	CircleLinkNode<T> *	tempnode = mHeadNode;
    	while (mLength != 0)
    	{
    		mHeadNode = mHeadNode->Next;
    		delete tempnode;
    		tempnode = mHeadNode;
    		mLength--;
    	}
    }

    其他情况主要注意在Head和Tail的极端顶点时的判断处理：

    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
    //ADT
    void FrontInsert(T v)
    {
    	CircleLinkNode<T> *tempnode = new CircleLinkNode<T>();

    	tempnode->mElement = v;

    	//when insert first element, tail node equals to head node
    	if (mLength == 0)
    	{
    		tempnode->Pre = tempnode;
    		tempnode->Next = tempnode;
    		mHeadNode = tempnode;
    		mTailNode = mHeadNode;
    	}
    	else
    	{
    		mHeadNode->Pre = tempnode;
    		tempnode->Pre = mTailNode;
    		tempnode->Next = mHeadNode->Next;
    		mHeadNode = tempnode;
    		mTailNode->Next = mHeadNode;
    	}

    	mLength++;
    }

    //......

    测试结果：
    CircleLinkList

栈

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。
栈的ADT：
Push(进栈)
Pop(出栈)

栈是LIFO(后进先出)

栈的实现：
栈是一个表，因此任何实现表的方法都能实现栈(比如数组，链表)。
下面以前面实现的链表为例来实现栈：
因为栈只允许顶端Push，Pop以及Top查看顶端元素并返回值，所以这里采用单向链表即可。

待续……

算法

算法与程序

算法是由若干条指令组成的又有穷序列，且满足下述4条性质：

  1. 输入：有零个或多个由外部提供的量作为算法的输入。
  2. 输出：算法产生至少一个量作为输出。
  3. 确定性：组成算法的每条指令是清晰的，无歧义的。
  4. 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

区分程序和算法：
程序与算法不同。程序是算法用某种程序设计语言的具体实现。

算法复杂性

算法复杂性体现在运行该算法所需的计算机资源(时间和空间)的多少上。

所以算法复杂性主要是体现的时间复杂度和空间复杂度上。
C表示复杂度，N表示问题的规模，I表示算法的输入，A表示算法本身。
C = F(N,I,A)
T表示时间复杂度，S表示空间复杂度。
T = F(N,I,A)
S = F(N,I,A)

时间复杂度

时间复杂度 — 指执行算法所需要的计算工作量
时间复杂度分为下列三种：

  1. 平均时间复杂度 — 理论上一般情况的时间复杂度
  2. 最坏时间复杂度 — 特殊情况下（导致时间耗费最多的数据输入）
  3. 最优时间复杂度 — 特殊情况下（导致时间耗费最少的数据输入）

空间复杂度

空间复杂度 — 指执行算法所需要的内存空间

程序算法思想

递归

定义：
直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。

基本思想：
每个递归函数都必须有非递归定义的初始值，否则，递归函数就无法计算。
递归式的第二式用较小自变量的函数值来表示较大自变量的函数值的方式来定义。

事例：
无穷数列1,1,2,3,5,8,13，,2,34,55……，称为Fibonacci数列。

1
2
3
       {  1                         n = 0
F(n) = {  1                         n = 1
       {  F(n - 1) + F(n - 2)       n > 1

代码实现：

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
// AlgorithmStudy.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int Fibonacci(int n)
{
	if( n <= 2)
	{
		return 1;
	}
	else
	{
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int n;
	cout<<"Please Enter the Fibonacci's n:"<<endl;
	cin>>n;
	cout<<"Fibonacci("<<n<<") = "<<Fibonacci(n)<<endl;

	system("pause");
	return 0;
}

FabonacciRecursion

还有一个典型的问题，汉诺塔问题。
问题描述：
a，b，c三个塔座。塔座a上共n个圆盘，圆盘至下而上从大到小的叠放在一起，圆盘编号从小到大为1,2,3……n。要求将塔座a上的这一叠圆盘移动到塔座b上，并按同样顺序叠放。移动规则如下：

  1. 每次只能移动一个圆盘
  2. 任何时时刻都不允许将较大的圆盘压在较小的圆盘会上
  3. 在满足移动规则1和2的前提下，将圆盘至a，b，c中任意塔座上。

解题思想：
若是奇数次移动，则将最小的圆盘移到顺时针方向的下一座塔上。若是偶数次移动，则保持最小的圆盘不动，而在其他两个塔座之间，将较小的圆盘移动到另一个塔座上。

那么如何用递归来实现这个解题思想了。
当n = 1时，将编号1的圆盘从塔座a移动到塔座b即可。
当n > 1时，需要利用塔座c作为辅助塔座。此时要设法将n - 1个较小的圆盘依照移动规则从塔座a移至塔座c上，然后，将剩下的最大圆盘从塔座a移至塔座b上，最后，再设法将n - 1个较小的圆盘你依照移动规则从塔座c移至塔座b上。(由此可见，n个圆盘的移动问题分解成为了两次n - 1个圆盘的移动问题，这就可以通过递归的方式解决)

1
2
3
4
5
6
7
8
9
void Hanoi(int n, int a, int b, int c)
{
	if(n > 0)
	{
        Hanoi(n - 1, a, c, b); // 将n - 1个圆盘按移动规则从a移动到c
        move(a,b);             // 将圆盘n从a移动到b
        Hanoi(n -1, c,  b, a); // 将n - 1个圆盘按移动规则从c移动到b
    }
}

递归算法好处：
结构清晰，可读性强，且容易用数学归纳法证明算法的正确性，方便调试。

递归算法坏处：
运行效率低，时间复杂度和空间复杂度都很大。

针对Fabonacci方法，我们可以写一个非递归的方法，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int FibonacciNoRecursion(int n)
{
	int temp[2];
	temp[0] = 1;
	temp[1] = 1;
	if(n <= 2)
	{
		return 1;
	}
	else
	{
		for(int i = 2; i < n; i++)
		{
			int tp = temp[0] + temp[1];
			temp[1]= temp[0];
			temp[0] = tp;
		}
	}
	return temp[0];
}

这样一来，递归调用导致的调用栈深度问题就没有了，而是通过临时变量把数据存储了起来。

分治

基本思想：
将一个规模为n的问题分解为k个(一般划分成n/2 — 二分细分)规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解。

在排序算法学习中，快速排序(Quick Sort)和归并排序(Merge Sort)就用到了分治的思想。

动态规划

基本思想：
动态规划与分治思想类似，但动态规划里经分解得到的子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，会这样就可以避免大量的重复计算，从而得到多项式时间算法。

动态规划适用于解最优化问题。一般有4个步骤设计：

  1. 找出最优解的性质，并刻画其结构特征。
  2. 递归地定义最优值。
  3. 以自底向上的方式计算出最优值。
  4. 根据计算最优值时得到的信息，构造最优解。

动态规划的基本要素：

  1. 最优子结构
    当问题的最优解包含其子问题的最优解时，称该问题具有最优子结构性质
  2. 重叠子问题
    在递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复运算。
  3. 备忘录方法
    备忘录方法是动态规划的变形，唯一不同的是递归方式是至顶向下。

接下来以求解最长公共子序列来分析动态规划算法。
问题描述：
X = {x1, x2, x3,…..xn}
Z = {z1, z2, z3,…..zn}
存在一个递增序列，即Z是X的子序列。

X = {x1, x2, x3,….. xm}
Y = {y1, y2, y3,….. yn}
求解X和Y的最长公共子序列Z：
Z = {z1, z2, z3,…zk}

分析最优子结构性质：
若X(m) = Y(n)，则Z(k) = X(m) = Y(n)，且Z(k-1)是X(m-1)和Y(n-1)的最长公共子序列
若X(m) != Y(n)且Z(k) != X(m)，则Z是X(m-1)和Y的最长公共子序列
若X(m) != Y(n)且Z(k) != Y(n)，则Z是X和Y(n-1)的最长公共子序列

c[i][j]记录序列X(i)和Y(j)的最长公共子序列的长度
从上面的最优子结构性质我们可以得出下列结论：

1
2
3
          {         0                       i = 0, j = 0
c[i][j] = {    c[i-1][j-1] + 1              i,j > 0; X(i) = Y(j)
          { Max(c[i][j-1], c[i-1][j])       i,j > 0; X(i) != Y(j)

从上面而已看出，在递归求的时候，很多子问题是重叠的。

b[i][j]用于记录c[i][j]的值是由哪一个子问题的解得到的。b最后会用于构建最优解。
我们把上面的情况分别分为1,2,3。在递归求解的时候存储的b[i][j]里。

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
#include "stdafx.h"
#include <iostream>
using namespace std;

template<typename T>
int GetArrayLength(T &array)
{
	return sizeof(array) / sizeof(array[0]);
}

void LCSLength(int m, int n, char *x, char *y, int **c, int **b)
{
	int i,j;
	// i = 0, j = 0的情况
	c[0][0] = 0;

	for(i = 1; i <= m; i++)
	{
		c[i][0] = 0;
	}
	
	for(i = 1; i <= n; i++)
	{
		c[0][i] = 0;
	}
	//自底向上的填充最优解
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
		{
			// X(i) == Y(j)的情况
			if(x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = 1;
			}
			// X(i) != Y(j) 且 Max{}取c[i][j-1]
			else if(c[i-1][j] >= c[i][j - 1])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = 2;
			}
			// X(i) != Y(j) 且 Max{}取c[i-1][j]
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = 3;
			}
		}
	}
}

void LCS(int i, int j, char *x, int **b)
{
	if(i == 0 || j == 0)
	{
		return ;
	}
	//根据前面LCSLength的分解情况，自底向上的递归构建最长公共子序列
	if(b[i][j] == 1)
	{
		LCS(i-1, j-1, x, b);
		cout<<x[i]<<endl;
	}
	else if(b[i][j] == 2)
	{
		LCS(i-1, j, x, b);
	}
	else
	{
		LCS(i, j-1, x, b);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	//LCS,因为LCSLength里面都是以1作为索引来访问x和y的第一个字母，
	//所以这里增加一个额外的" "便于1作为第一个字母的索引
	char x[] = {' ', 'A', 'B', 'D', 'B', 'C', 'A', 'E', 'F'};
	char y[] = {' ', 'A', 'C', 'B', 'A', 'F'};
	int **c = new int*[GetArrayLength(x)];
	int **b = new int*[GetArrayLength(x)];
	for(int i = 0; i < GetArrayLength(x); i++)
	{
		c[i] = new int[GetArrayLength(y)];
		b[i] = new int[GetArrayLength(y)];
	}
	//因为前面我们额外增加了一个" "，所以这里要减少一个长度计算
	LCSLength(GetArrayLength(x) - 1, GetArrayLength(y) - 1, x, y, c, b);
	LCS(GetArrayLength(x) - 1, GetArrayLength(y) - 1, x, b);
	
	system("pause");
	return 0;
}

LCSLength

算法时间复杂度分析：
计算最长公共序列的LCSLength耗时O(m x n);
构建最长公共序列的LCS递归调用自身使i和j - 1,时间复杂度为O(m + n)

算法改进：
c[i][j]可以由c[i-1][j-1],c[i-1][j]和c[i][j-1]推断出来，所以可以节省数组b的空间，但数组c仍需要m x n的空间，所以空间复杂度仍然是O(m x n)

另一个很典型的动态规划事例是0-1背包问题：
问题描述：
给定n种物品和一背包。物品i的重量是w(i)，其价值为v(i)，背包容量为c。应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

形式化描述：
给定c > 0,w(i) > 0, v(i) > 0, i <= i <=n,要求找出一个n元0-1向量(x1,x2,x3…..,xn), x(i) ∈ {0, 1}, 1 <= i <= n,使得∑(i= 1 - n)(w(i) x x(i)) <= c，而且∑(i= 1 - n)(v(i) x x(i))达到最大。
转换成式子如下：
max(∑( 1 <= i <= n)(v(i) x x(i)))
{ ∑(i= 1 - n)(w(i) x x(i)) <= c
{ x(i) ∈ {0, 1}, 1 <= i <= n

分析：
最优子结构性质：
设(y1,y2……yn)是所给0-1背包问题的一个最优解，则(y2,y3…..yn)是下面相应子问题的一个最优解：
max(∑(2 <= i <= n)(v(i) x x(i)))
{ ∑(2 <= i <= n)(w(i) x x(i)) <= c - w(1) x y(1)
{ x(i) ∈ {0, 1}, 2 <= i <= n

递归关系：
0-1背包问题的子问题：
max(∑(i <= k <= n)(v(k) x x(k)))
{ ∑(i <= k <= n)(w(k) x x(k)) <= j
{ x(k) ∈ {0, 1}, i <= k <= n
m(i,j)是背包容量为j，可选物品为i,i+1…..n时0-1背包问题的最优解。
x(i)表示背包i的选择∈ {0, 1}
根据最优子结构性质，可以建立就按m(i,j)的递归式如下：
{ max{m((i+1,j), m(i+1, j - w(i)) + v(i))} j >= w(i)
m(i,j) = {
{ m(i+1,j) 0 <= j <= w(i)

{  v(n)   j >= w(n)

m(n,j) = {
{ 0 0 <= j < w(n)

计算出所有m[i][j]后，我们可以通过判断m[i][c]和m[i+1]c是否相同来判断x(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
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
#include "stdafx.h"
#include <vld.h>
#include <iostream>
#include <math.h>
using namespace std;

template<typename T>
int GetArrayLength(T &array)
{
	int length = sizeof(array) / sizeof(array[0]);
	return length;
}

void Knapsack(float *v, int *w, int c, int n, float **m)
{
	int jmax = fmin(w[n] - 1,c);
	//根据最优子结构性质，m[n - 1][j]的最优解是m[n][j]最优解的子集，
	//我们先构建出m[n][j]时的数据,然后利用m[n][j]的数据去构建m[i][c]  1 <= i < n
	for (int j = 0; j <= jmax; j++)
	{
		m[n][j] = 0;
	}

	for (int j = w[n]; j <= c; j++)
	{
		m[n][j] = v[n];
	}

	//利用m[n][j]去构建m[i][j]   1 <= i < n
	for (int i = n - 1; i > 1; i--)
	{
		jmax = fmin(w[i] - 1, c);
		for (int j = 0; j <= jmax; j++)
		{
			m[i][j] = m[i + 1][j];
		}

		for (int j = w[i]; j <= c; j++)
		{
			m[i][j] = fmax(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
		}
	}

	//Finally, we can get m[1][c] from c[2][c]
	m[1][c] = m[2][c];
	if (c >= w[1])
	{
		m[1][c] = fmax(m[2][c], m[2][c - w[1]] + v[1]);
	}
}

void Traceback(float **m, int *w, int c, int n, int *x)
{
	for (int i = 1; i < n; i++)
	{
		if (m[i][c] == m[i + 1][c])
		{
			x[i] = 0;
		}
		else
		{
			x[i] = 1;
			c -= w[i];
			cout << "Put " << i << " into the bag!" << endl;
		}
	}
	//check for last one
	x[n] = m[n][c] ? 1 : 0;
	if (x[n] == 1)
	{
		cout << "Put " << n << " into the bag!" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	//0-1背包问题
	//因为我们从v[1]开始访问当做第一个背包的价值，
	//所以这里加一个0在最前面方便从1开始索引
	float v[] = { 0, 1, 5, 2, 3, 6, 8, 3 };
	int w[] = { 0, 4, 3, 6, 7, 2, 3, 1 };
	int c = 20;
	//减掉我们额外增加的第一个
	int n = GetArrayLength(v) - 1;
	float **m = new float*[GetArrayLength(v)];
	//为了从1开始索引
	int *x = new int[n + 1];
	for (int i = 0; i < GetArrayLength(v); i++)
	{
		//m[i][j]    1 <= j <= n用于表示背包容量为j，可选物品为i,i+1....n是0-1背包问题的最优解
		//为了m[i][c]来访问背包重量为c的时候的最优解，这里需要额外增加数组长度1
		m[i] = new float[c + 1];
	}
	Knapsack(v, w, c, n, m);
	Traceback(m, w, c, n, x);
	
	for (int i = 0; i < GetArrayLength(v); i++)
	{
		delete m[i];
	}

	delete x;

	system("pause");
	return 0;
}

01Knapsack

算法复杂度分析：
计算m[i][j]的递归式可以看出，算法Knapsack需要O(nc)计算时间，Traceback需要O(n)计算时间

算法缺点：

  1. w[i]要求是整数
  2. 当c很大的时候，算法Knapsack时间复杂度很大

算法改进：
详情参考计算机算法设计与分析(第3版)

贪心算法

基本思想：
贪心算法通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。

基本要素：

  1. 贪心选择性质
    贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。(贪心算法以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题)
  2. 最优子结构性质
    最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

下面结合背包问题来区分动态规划和贪心算法在实际应用中的区别：
问题描述：
背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。

最优子结构性质分析：
若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量w，剩余的将是n-1个原重量物品1,2,…,j-1,j+1,…,n及重为w(j)-w的物品j中可装入容量为c-w的背包且具有最大价值的物品。

贪心选择性质分析：
按单位价值为依据(局部最优)进行选择(贪心选择)，可使最终装满背包时，价值最大。

贪心算法解背包问题的基本步骤：

  1. 计算每种物品单位重量的价值v(i)/w(i)
  2. 依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
  3. 若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多的装入背包。
  4. 依次策略，直到背包装满为止。

贪心选择对于0-1背包问题就不能得到最优解，因为它无法保证最终背包能装满，部分闲置的背包空间使每千克背包空间的价值降低了。所以在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后做出最好选择，而不是按最优单位价值(局部最优)来选。

回溯法算法

回溯法的算法框架：

  1. 问题的解空间
    解空间包含所有可能的答案
  2. 回溯法的基本思想
    在问题的解空间树种，按深度优先策略，从根节点触发搜索解空间树。算法搜索到任一节点时，先判断该节点是否包含问题的解，如果不包含，则以该节点为根节点以深度优先搜索。直到搜索到叶节点也没找到问题解时，回溯到最近一个非叶节点继续搜索，知道所有节点都搜索完成为止。

接下来以0-1背包问题为例来学习理解回溯法：
假设0-1背包n = 3，w = [16, 15, 15] v = [45, 25, 25] c= 30
解空间为：
{(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1)}
Backtracking
因为是以深度优先搜索，所以是延A -> B -> D -> H -> D -> I -> D -> B -> E -> J -> K的顺序来搜索，直到回溯完所有的解空间节点或找到答案为止。

问题:
上述回溯法把所有的解空间都搜索了一遍，时间和空间复杂度大。

优化：
回溯法通常采用两种策略避免无效搜索，提高回溯法的搜索效率：

  1. 用约束函数在扩展结点处剪去不满足约束条件的子树。
  2. 用限界函数剪去得不到最优解的子树。(两个函数统称为剪枝函数)

在0-1背包里左子树表示装载当前背包，右子树表示不装载当前背包。
所以在针对剪枝函数的优化上，我们可以在判断只有在右子树中有可能包含最优解时才进入。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp + r <= bestp时，可剪去右子树。

正确的选取r是优化的关键之一：
我们可以通过按背包问题里贪心算法的方式计算出当前剩余物品的最优值(算出当前剩余物品最多还能增加的价值)作为上界剪枝。

代码实现:
Utilites.h

1
2
3
4
5
6
7
8
#include "stdafx.h"

template<typename T>
static int GetArrayLength(T &array)
{
	int length = sizeof(array) / sizeof(array[0]);
	return length;
}

Knap.h

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
#include "stdafx.h"

class Knap
{
public:
	Knap(float *v, int *w, int c, int n);

	~Knap();

	void Backtrack(int i);

	float GetBestp();

private:
	float Bound(int i);

	//把物品按单位价值降序排列
	void Sort();

	int mC; //背包容量

	int mN; //物品数量

	int *mW; //物品重量

	float *mV; //物品价值

	int mCW; //当前重量

	float mCV; //当前价值

	float mBestp; //当前最优价值
};

Knap.cpp

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
#include "stdafx.h"
#include "Knap.h"
#include "Utilties.h"

Knap::Knap(float *v, int *w, int c, int n)
{
	assert(c > 0);
	assert(n > 0);
	mC = c;
	mN = n;
	mW = w;
	mV = v;
	mCW = 0;
	mCV = 0; 
	mBestp = 0;
	Sort();
}

void Knap::Backtrack(int i)
{
	//到达叶节点
	if (i > mN)
	{
		//到了叶节点后记录最优值
		mBestp = mCV;
		return;
	}

	//进入左子树
	if (mCW + mW[i] <= mC)
	{
		mCW += mW[i];
		mCV += mV[i];
		//深度优先扩张
		Backtrack(i + 1);
		//回溯到i时，我们需要在判断是否进入右子树之前把mCW和mCV的值回复到正确的值。
		mCW -= mW[i];
		mCV -= mV[i];
	}

	//进入右子树
	if (Bound(i + 1) > mBestp)
	{
		//继续深度优先扩张
		Backtrack(i + 1);
	}
}

float Knap::GetBestp()
{
	return mBestp;
}

//计算cp + r <= bestp中r的值
//通过把剩余物品按贪心算法的背包问题来计算出最优值上界
float Knap::Bound(int i)
{
	int cleft = mC - mCW; //剩余容量

	float b = mCV; //当前价值

	//以物品单位重量价值递减序装入物品
	while (i <= mN && mW[i] <= cleft)
	{
		cleft -= mW[i];
		b += mV[i];
		i++;
	}

	//装满背包
	if (i <= mN)
	{
		b += mV[i] * cleft / mW[i];
	}

	return b;
}

void Knap::Sort()
{
	assert(mN > 0);
	float *pervalue = new float[mN];
	pervalue[0] = 0;
	for (int i = 1; i <= mN; i++)
	{
		pervalue[i] = mV[i] / mW[i];
	}

	//双重循环都跟数据大小有关
	//所以冒泡排序平均时间复杂度是O(square(n))
	for (int i = 1; i <= mN; i++)
	{
		for (int j = i + 1; j <= mN; j++)
		{
			if (pervalue[i] < pervalue[j])
			{
				swap(mV[i], mV[j]);
				swap(mW[i], mW[j]);
				swap(pervalue[i], pervalue[j]);
			}
		}
	}
}

Knap::~Knap()
{

}

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int _tmain(int argc, _TCHAR* argv[])
{	
	//0-1背包回溯算法
	//因为我们从v[1]开始访问当做第一个背包的价值，
	//所以这里加一个0在最前面方便从1开始索引
	float v[] = { 0, 1, 5, 2, 3, 6, 8, 3 };
	int w[] = { 0, 4, 3, 6, 7, 2, 3, 1 };
	int c = 20;
	//减掉我们额外增加的第一个
	int n = GetArrayLength(v) - 1;
	Knap *knap = new Knap(v, w, c, n);

	knap->Backtrack(1);

	cout << "knap->GetBestp() = " << knap->GetBestp() << endl;

	delete knap;

	system("pause");
	return 0;
}

BacktrackingResult

时间复杂度分析：
Knap::Sort()排序采用冒泡排序，时间复杂度为：
平均时间复杂度：O(square(n))
最坏时间复杂度：O(square(n)) （每一次比较都需要交换）
最优时间复杂度：O(n) （第一次循环就完成所有排序而无需进行后面的，需要判断结束条件）

Knap::Bound()计算上界剪枝需要O(n)
最坏情况下有O(Pow(2,n))个右节点，所以回溯算法的最坏时间复杂度为O(n x Pow(2,n))
跟动态规划解0-1背包的O(nc)时间复杂度相比，回溯算法的时间复杂度大得多。

Note:
剪枝函数(约束函数和上界函数)的选取是回溯法性能的关键。

分支限界法

待续…..

STL

C++里将数据结构和算法运用的比较好的就不得不提STL了。

STL

STL(标准模板库)是C++标准程序库的核心，是一个泛型程序库，利用先进，高效的算法来管理数据。

STL组件

  1. 容器(Containers)
    用来管理某类对象的集合。
  2. 迭代器(Iterators)
    用来在一个对象群集(Collection of objects)的元素上进行遍历动作
  3. 算法(Algorithoms)
    用来处理群集内的元素。(比如搜寻，排序，修改，使用等)

“STL的基本观念就是将数据和操作分离。数据由容器类加以管理，操作则由可定制的算法定义。迭代器在两者之间充当粘合剂是的任何算法都可以和任何容器运作。”
STLComponentsRelationship

STL将数据和算法分开对待，这和面向对象设计(OOP)的思想是矛盾的。
但这么做的好处是：
可以将各容器与各算法结合起来。

STL的特性一：
泛型，可以针对任意类型运作

Note:
“STL甚至提供更泛型化的组件。通过特定的适配器(adapters)和仿函数(functors)，你可以补充，约束或定制算法，以满足特别需求。”

容器(Containers)

容器可分为两类：

  1. Sequence Containers
    “可序(ordered)群集，每个元素均有固定位置—取决于插入时机和地点，和元素值无关。”
    vector，deque，list
    Vectors特点(Vector将其元素置于一个dynamic array)：
    1. 允许随机存储。
    2. 非尾部插入会比较费时(要保持原本的相对次序，导致元素移动)
    3. 动态扩容
      Deques特点(double-ended queue是一个dynamic array，可以向两端发展)：
    4. 允许随机存储
    5. 头部和尾部插入迅速
    6. 中间部分插入费时(导致元素移动)
    7. 动态扩容
      Lists特点(doubly linked list，分散存储内存):
    8. 不提供随机存取(因为是分散存储的)
    9. 访问元素费时(沿着链表节点访问)
    10. 插入和删除快速(因为只需要改变链接点即可)
    11. 动态扩容
  2. Associative Containers
    “已序(sorted)群集，元素位置取决于特定的排序准则。”
    set，multiset，map，multimap
    Sets特点:
    1. 依据值自动排序
    2. 每个元素值只允许出现一次
    3. 动态扩容
      Multisets特点：
    4. 依据值自动排序
    5. 允许重复元素
    6. 动态扩容
      Maps特点：
    7. 采用键值对存储，根据键值排序
    8. 键值不允许重复
    9. 动态扩容
      Multimaps特点：
    10. 采用键值对存储，根据键值排序
    11. 允许键值重复
    12. 动态扩容

除了上述容器，C++标准成宿还提供了一些特别的Container Adapters。
Container Adapaters：

  1. Stacks
    LIFO(后进先出)
  2. Queues
    FIFO(先进先出)
  3. Priority Queues
    元素按优先级排序

Note:
“通常关联式容器由二叉树(binary tree)实现。”

容器的共同能力：

  1. 所有容器提供的都是“Value语意”而非“Reference语意”
    Value语意 VS Reference语意
    “STL只支持value语意，不支持reference语意”
    好处：
    1. 元素拷贝简单
    2. 使用references时容易导致错误
      缺点：
    3. “拷贝元素”可能导致不好的性能
    4. 无法在数个不同的容器中管理同一份对象
  2. 所有元素形成一个次序(返回iterator的接口用于访问所有元素)
  3. 各项操作并非绝对安全。调用者必须确保传给操作函数的参数符合需求。

Note:
实现Reference语意需要通过智能指针(e.g. share_ptr)

容器的共同操作：

  1. 初始化
  2. 大小相关操作函数(size(),empty(),max_size())
  3. 比较(==,!=,<,<=,>,>=)

Value语意也就引出了容器元素的条件：

  1. 必须可透过copy构造函数进行复制
  2. 必须可以透过assignment操作符完成赋值动作
  3. 必须可以透过析构函数完成销毁动作

如何选择合适的Container？
根据以下规则：

  1. 缺省情况下使用vector，vector内部结构简单，支持随机存储
  2. 如果经常要在头部和尾部安插和移除元素，采用deque
  3. 如果需要经常在容器的中段执行元素的插入，移除和移动，可以考虑使用list
  4. 如果经常需要根据某个准则来搜寻元素，那么应当使用“以该排序准则对元素进行排序”的set或multiset(hash table比二叉树更快，对于无需排序的元素，推荐用hash table)
  5. 如果想处理key/value pair，采用map或multimap
  6. 如果需要关联式数组，应用map
  7. 如果需要字典结构，应用multimap

STL Container能力详情参见：
STLContainerCapabilities

容器内的类型和成员

容器内的类型：
container::value_type — 元素类型
container::reference —元素的引用类型
container::const_reference — 常数元素的引用类型
container::iterator — 迭代器类型
container::const_iterator — 常数迭代器的类型
container::const_reverse_iteator — 常数反向迭代器的类型
container::size_type — 无符号整数类型，用以定义容器大小
container::difference_type — 正整数类型，用以定义距离
container::key_type — 用以定义关联式容器的元素内的key类型
container::mapped_type — 用以定义关联式容器的元素内的value类型
container::key_compare — 关联式容器内的“比较准则”的类型
container::value_compare — 整个元素”比较准则”的类型
container::allocator_type — 配置器类型

生成，复制，销毁,非变动性操作,赋值,元素存储,返回迭代器操作,元素insert和remove:
……
……

迭代器(Iterators)

什么是迭代器(Iteratos)？
“迭代器是一个“可遍历STL容器内全部或部分元素”的对象。”

Note:
“迭代器奉行一个村抽象概念：任何东西，只要行为类似迭代器，就是一种迭代器。不同的迭代器具有不同的“能力”(指行进和存储能力)”

迭代器分类：
STLIteratorClassification

迭代器的能力取决于容器的内部结构，所以根据能力来分类的话：

  1. 双向迭代器(Bidirectional iterator)
    支持双向行进(++ —)(list, set, multiset, map, multimap)
  2. 随机存取迭代器(Random access iterator)
    支持双向行进同时具备随机访问(< >等)(vector, deque)

“为了编写与容器类型无关的泛型程序编码，最好不要使用随机存取迭代器。(因为不是所有的容器都支持随机迭代器)”

比如如下代码：

1
2
3
4
for(pos = coll.begin(); pos < col.end(); ++pos)
{
	.......
}

上面使用的<就是随机存储迭代器才支持的。

Note:
是否支持特定迭代器跟迭代器的能力和容器的内部结构挂钩(比如List因为是链接形式所以肯定不支持Random access iterator的随机访问的)。

迭代器操作：

  1. Operator *
    返回当前元素值
  2. Operator ++
    访问下一个元素
  3. Operators ==
    判断迭代器是否指向同一位置
  4. Operators ！=
    判断迭代器是否指向同一位置
  5. Operator =
    为迭代器赋值

“迭代器是个所谓的smart pointers，具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此，每一种容器类型都必须提供自己的迭代器。”

容器类提供的迭代器访问相关函数：

  1. begin()
    返回一个迭代器，指向容器的起始点
  2. end()
    返回一个迭代器，指向容器结束点(最后一个元素之后)

读写方式区分：

  1. iterator
    支持读/写模式
  2. const_iterator
    只读模式

这里通过简单的使用Set container为例，对iterator和自定义比较函数做个了解：

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
// STLStudy.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

template<typename T>
bool Greater(const T& p1, const T& p2)
{
	return p1 > p2;
}

int _tmain(int argc, _TCHAR* argv[])
{
	//Associative Container
	bool(*fn_pt)(const int&,const int&) = Greater<int>;
	set<int, bool(*)(const int&,const int&)> s(fn_pt);

	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(6);
	s.insert(5);
	s.insert(1);

	set<int>::const_iterator set_const_iterator;
	for (set_const_iterator = s.begin(); set_const_iterator != s.end(); ++set_const_iterator)
	{
		cout << *set_const_iterator<<endl;
	}

	system("pause");

	return 0;
}

SetIteratorAndCompareFunction
从上面可以看到set有自己对应的iterator去访问set container里的元素，同时我们也可以传递一个自定义的比较函数作为set container排序的依据。

迭代器相关辅助函数：

  1. advance() — 可令迭代器前进
  2. distance() — 计算两个迭代器之间的距离
  3. iter_swap() — 交换两个迭代器所指内容

Iterator Adapter：

  1. Insert iterators
    使算法以安插(insert)方式而非覆写(overwrite)方式运作
    1. Back inserters(安插于容器最尾端)
    2. Front inserters(安插于容器最前端)
    3. General inserters(安插到指定位置)
  2. Stream iterators
    用于读写stream的迭代器。
  3. Reverse iterators
    以逆方向进行所有操作(++相当于— —相当于++)
    通过容器的rbegin()，rend()可以获得Reverse iterators

迭代器特性(Iterator Traits):
“迭代器可以区分为不同类型，每个类型都具有特定的迭代器功能。如果能根据不同的迭代器类型，将操作行为重载，将会很有用，甚至很必要。透过迭代器标记(tags)和特性(traits)可以实现这样的重载。”

首先来看看迭代器标志的定义：
STLIteratorTags

接下来是迭代器特性(包含迭代器相关的所有信息)的定义：
STLIteratorTraits
“有了上面这个template，T表示迭代器类型，我们就可以撰写任何运用“迭代器类型或其元素类型”等特征的泛型程序代码”

iterator_traits结构描述了迭代器相关的类型信息。
针对特定的迭代器(一般指针作为迭代器时)需要特化版本：

1
2
3
4
5
6
7
8
9
10
11
12
namespace std{
	template <class T>
	struct iterator_traits<T*>{
		typedef T                            value_type;
		typedef ptrdiff_t                    difference_type;
		typedef random_access_iterator_tag   iterator_category
		typedef T*                           pointer;
		typedef T&                           reference;
	}
}

}

比如元素环形移动：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class Forwarditerator>
void shift_left(Forwarditerator beg, Forwarditerator end)
{
	//temporary variable for first element
	typedef typename std::iterator_traits<Forwarditerator>::value_type value_type;

	if(beg != end)
	{
		//save value of first element
		value_type temp(*beg);

		//shift following values
		......
	}
}

通过把迭代器类型作为模板参数通过iterator_traits访问该迭代器类型的value_type。

iterator_traits里的iterator_category可以帮助我们写出针对不同迭代器类型的函数。
接下来结合distance()的实现来学习理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class iterator>
typename std::iterator_traits<iterator>::difference_type distance(iterator pos1, iterator pos2)
{
	return distance(pos1, pos2, std::iterator_traits<iterator>::iterator_category());
}

template<class Raiterator>
typename std::iterator_traits<Raiterator>::difference_type foo(Raiterator pos1, Raiterator pos2, std::random_access_iterator_tag)
{
	return pos2 - pos1;
}

template<class Initerator>
typename std::iterator_traits<Initerator>::difference_type foo(Initerator pos1, Initerator pos2, std::input_iterator_tag)
{
	typename std::iterator_traits<Initerator>::difference_type d;
	for(d = 0; pos1 != pos2; ++pos1, ++d)
	{
		;
	}

	return d;
}

根据传递迭代器类型iterator_category()作为第三个参数，我们可以写出针对不同迭代器类型的distance方法实现。根据迭代器是否支持随机访问，我们写出了不同的distance计算实现。
Note：
difference_type代表迭代器距离类型。同时std::tag对于子类同时有效。

如何自定义迭代器？
可以看出迭代器必须具有iterator_traits结构所描述的类型定义，用于描述迭代器相关类型信息。

  1. 提供必要的五种类型定义(iterator_traits里定义的)
  2. 提供一个特化版本(用于一般指针迭代器)的iterator_traits结构
    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
    #include "stdafx.h"

    template<typename Container>
    class MyInsertIterator : public std::iterator<std::output_iterator_tag, void, void, void, void>
    {
    protected:
    	Container& container;

    public:
    	explicit MyInsertIterator(Container& c) : container(c)
    	{

    	}

    	MyInsertIterator<Container>& operator= (const typename Container::value_type& value)
    	{
    		container.insert(value);
    		return *this;
    	}

    	MyInsertIterator<Container>& operator* ()
    	{
    		return *this;
    	}

    	MyInsertIterator<Container>& operator++ ()
    	{
    		return *this;
    	}

    	MyInsertIterator<Container>& operator++ (int)
    	{
    		return *this;
    	}
    };

    //convenience function to create the MyInsertIterator
    template<class Container>
    inline MyInsertIterator<Container> MyInsert(Container& c)
    {
    	return MyInsertIterator<Container>(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
#include "stdafx.h"
#include "MyInsertIterator.h"

int _tmain(int argc, _TCHAR* argv[])
{
	//My own Iterator part
	set<int> coll;

	//create MyInsertIterator for coll
	MyInsertIterator<set<int>> iter(coll);
	*iter = 1;
	iter++;
	*iter = 2;
	iter++;
	*iter = 3;

	PrintAll(coll);

	MyInsert(coll) = 44;
	MyInsert(coll) = 55;

	PrintAll(coll);

	system("pause");

	return 0;
}

STLOwnIterator
把iterator作为父类，通过设定模板参数设置iterator_traits里需要设定的类型相关信息。
通过重载各个运算符实现我们自己的迭代器支持的操作。

Note：
“Iterator traits是掌握STL编程技术的关键。”

算法(Algorithms)

“算法并非容器类的成员函数，而是一种搭配迭代器使用的全局函数。”

这样做的好处：
“不必为每一种容器量身定制算法，所有算法只需一份。”

先来看看实战使用：

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
#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
	//cout << MyClass::mID << endl;

	//Sequence container
	vector<int> v;

	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	reverse(v.begin(), v.end());

	vector<int>::const_iterator vector_const_iterator;
	for (vector_const_iterator = v.begin(); vector_const_iterator != v.end(); ++vector_const_iterator)
	{
		cout << *vector_const_iterator << endl;
	}

	system("pause");

	return 0;
}

STLAlgorithems
从上面reverse的调用可以看出，用户需要负责传入两个iterator作为访问区间。
但这样做的话接口虽然灵活，但是确需要用户去保证传入的两个iterator的有效性。

算法分类：

  1. Manipulating Algorithms
    是指会“删除或重排或修改元素”的算法
    remmove,resort,modify……
    下面以remove算法为例：
    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
    #include "stdafx.h"


    template<typename T>
    void PrintAll(T container)
    {
    	typename T::const_iterator const_iterator;
    	for (const_iterator = container.begin(); const_iterator != container.end(); ++const_iterator)
    	{
    		cout << *const_iterator << endl;
    	}

    	cout << "-------------------------------------" << endl;
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    	//cout << MyClass::mID << endl;

    	//Sequence container
    	vector<int> v;
    	vector<int> v2;

    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}

    	reverse(v.begin(), v.end());

    	//PrintAll<vector<int>::const_iterator>(v.begin(), v.end());

    	copy(v.begin(), v.end(), inserter(v2, v2.begin()));
    	
    	//PrintAll<vector<int>::const_iterator>(v2.begin(), v2.end());

    	//注意remove不会改变container数量，只是用后面的覆盖符合规则的元素
    	//同时返回新的最尾端元素iterator
    	vector<int>::iterator v2end = remove(v2.begin(), v2.end(), 3);

    	PrintAll<vector<int>>(v2);

    	PrintAll<vector<int>>(v2);

    	//要想删除container里的元素，需要使用容器的erase
    	v2.erase(v2end, v2.end());

    	PrintAll<vector<int>>(v2);

    	system("pause");

    	return 0;
    }

STLRemove
从上面看到，我们无法通过迭代器本身去删除容器的元素而需要通过容器本身去删除。
为什么会这样了？
“STL将数据结构和算法分离开来。然而，迭代器只不过是“容器中某一位置”的抽象概念而已。一般来说，迭代器对自己所属容器一无所知。任何“以迭代器访问容器元素”的算法，都不得透过迭代器条用容器类提供的任何成员方法。”
但正因为这样的设计，算法只需要操作与迭代器上而不需要了解容器细节。
那么这里有一个问题，Manipulating Algorithms会修改或移除或重排容器元素，那么他们可以作用于Associative Containers(按特定规则对元素进行了排序)上吗？
答案是不能，为了保证Associative Containers已序的特性，Associative Containers只提供了const_iterator的迭代器，从而防止了Manipulating Algorithms的使用。
算法 VS 容器成员函数？
算法只是做一些通用的工作，本不能完美针对各个容器使用最优的方式。
比如针对list，如果采用算法remove，会导致删除第一个元素后，后面所有的元素都分别设给前一个元素，这就违背了list的通过修改链接而非实值来安插，移动，移除元素的优点。在这种情况下，使用list自身的成员函数更优于通用算法。

自定义泛型函数：
参见前面我们自定义的PrintAll泛型模板函数，把container作为参数传递，从而打印出所有元素。

以函数作为算法的参数：
一些算法可以接受用户定义的辅助性函数，由此提高其灵活性和能力。这些函数将在算法内部被调用。
下面以for_each为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include "stdafx.h"

template<typename T>
void Print(T elem)
{
	cout << elem << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    ......

	cout << "foreach-------------------------" << endl;
	for_each(v2.begin(), v2.end(), Print<int>);
	
	system("pause");

	return 0;
}

STLForEach
“运用这些辅助函数，我们可以指定搜寻准则，排序准则或定义某种操作等。”
Predicates：
“Predicates是一种特殊的辅助函数。返回bool的函数，通常被用来指定排序准则和搜寻准则。(STL要求，面对相同的值，predicates必须得出相同的结果)”
下面以find_if为例：

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
#include "stdafx.h"

template<typename T>
bool IsEven(T number)
{
	number = abs(number);

	if (number % 2 == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
    ......

	for_each(v2.begin(), v2.end(), Print<int>);

	vector<int>::iterator pos = find_if(v2.begin(), v2.end(), IsEven<int>);

	if (pos != v2.end())
	{
		cout << *pos << " is first even number in v2!" << endl;
	}
	else
	{
		cout << "No even number found!" << endl;
	}

	system("pause");

	return 0;
}

STLPredicates
更多的predicates参考STL Algorithms的使用。

  1. Nonmodifying Algorithms
    是指不会变动元素值，也不会改变元素次序的算法。
    e.g. count, min_element, max_element, find……

仿函数(Functors):
什么是Functors？
“Functors是泛型编程强大为例和纯粹抽象概念的又一个例证。你可以说，任何东西，只要其行为像函数，它就是函数。因此，如果你定义了一个对象，行为像函数，它就可以被当做函数来用。”

那么什么才算是具备函数行为了？
“是指可以“使用小括号传递参数，籍以调用某个东西”。”
e.g.
function(arg1,arg2);

如何实现？
通过自定义operator()即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "stdafx.h"

//functors
template<typename T>
class FunctorClass
{
public:
	void operator()(T elem) const{
		cout << elem << endl;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	......

	FunctorClass<int> func;

	for_each(v2.begin(), v2.end(), func);
	
	system("pause");

	return 0;
}

STLFunctors
让我们看看for_each源码：

1
2
3
4
5
6
7
8
9
template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function fn)
{
  while (first!=last) {
    fn (*first);
    ++first;
  }
  return fn;      // or, since C++11: return move(fn);
}

可以看出我们传递的FunctorClass实例对象通过fn(*first)的方式调用了我们定义的operator()函数

Functor好处：

  1. smart functions(智能型函数)
    ““行为类似指针”的对象。拥有成员函数和成员变量，意味着functor拥有状态。”
  2. 每个functor都有自己的类型
  3. functor通常比一般函数速度快
    “就template概念而言，由于更多细节在编译器就已确定，所以通常可能进行更好的最佳化。”

预定义的Functor：
C++标准库里包含了一些预先定义的仿函数：
less<>,negate<>……

什么是Function Adaptors？
所谓的Function Adaptors是指能够将仿函数和另一个仿函数(或某个值，或某个一般函数)结合起来的仿函数。
比如：
bind2nd(greater(),42) — 检查某个int值大于42.bind2nd把二元仿函数转换为一元仿函数。
“通过Function Adaptors，我们可以把多个仿函数结合起来，形成强大的表达式，这种编程方式称为functional composition。”

那么成员函数能当做Function Adaptors使用吗？
答案是可以。C++里提供了将成员函数转换成Function Adaptors的方法(mem_fun_ref()和mem_fun())
Note:
mem_fun_ref和mem_fun调用的成员函数必须是const。

那么非成员函数是否能当做Function Adaptors了？
答案是可以的。C++里提供了ptr_fun将非成员函数转换为Functor Object。
详细内容参见《C++标准程序库》第8章

接下来让我们看看如何使自定义的Functor也可以使用Function Adaptors。
要想使自定义Functor使用Function Adaptors需要满足下列条件：

  1. 必须提供一些类型成员来反映其参数和返回值的类型。
    C++标准程序库提供了一些结构如下：
    STLFunctionAdaptorsStructor
    如果自定义Functor想要支持Functor Adaptors，我们只需要定义struct继承至unary_function或binary_function，同时定义operator()的Functor行为即可。

更多一元，二元组合函数配接器参见《C++标准程序库》第8章

Note：
算法参数传递的区间是半开区间[begin, end)(包含begin，不包含end)

STL内部的错误处理和异常处理

错误处理

“STL的设计原则是效率优先，安全次之。错误检查相当花时间，所以几乎没有。”
原因：

  1. 错误检验会降低效率，而速度始终是程序的总体目标。
  2. 不加入的话，用户可以通过封装自己写错误检查的版本，但反过来却不行。

使用STL需要注意的点：

  1. 迭代器务必合法而有效
  2. 一个迭代器如果只想”end”位置，它并不指向任何对象，因而不能对它调用operator*或operator->
  3. 区间必须是合法的
  4. 如果涉及的区间不止一个，第二区间及后继各区间必须拥有“至少和第一区间一样多”的元素
  5. 覆盖动作中的“目标区间”必须拥有足够的元素，否则就必须采用insert iterators

Note:
含错误处理版本的STL，STLport

异常处理

……

扩展STL

“STL被涉及成一个框架，可以向任何方向扩展。你可以提供自己的容器，迭代器，算法，Functor…..，只要你满足条件即可。”

待续……

文章目錄
  1. 1. 前言
  2. 2. 欲善其事必先利其器
  3. 3. 数学知识
    1. 3.1. 指数
    2. 3.2. 对数
    3. 3.3. 级数
    4. 3.4. 模运算
    5. 3.5. 证明方法
    6. 3.6. 递归简论
  4. 4. 数据结构
    1. 4.1. 链表
    2. 4.2. 栈
  5. 5. 算法
    1. 5.1. 算法与程序
    2. 5.2. 算法复杂性
      1. 5.2.1. 时间复杂度
      2. 5.2.2. 空间复杂度
    3. 5.3. 程序算法思想
      1. 5.3.1. 递归
      2. 5.3.2. 分治
      3. 5.3.3. 动态规划
      4. 5.3.4. 贪心算法
      5. 5.3.5. 回溯法算法
      6. 5.3.6. 分支限界法
  6. 6. STL
    1. 6.1. STL
    2. 6.2. STL组件
      1. 6.2.1. 容器(Containers)
        1. 6.2.1.1. 容器内的类型和成员
      2. 6.2.2. 迭代器(Iterators)
      3. 6.2.3. 算法(Algorithms)
    3. 6.3. STL内部的错误处理和异常处理
      1. 6.3.1. 错误处理
      2. 6.3.2. 异常处理
    4. 6.4. 扩展STL