现在的位置: 首页 > 综合 > 正文

【STL】算法细节

2018年04月23日 ⁄ 综合 ⁄ 共 739字 ⁄ 字号 评论关闭

一、概论

1、质变算法--会改变操作对象的值

2、非质变算法-不改变操作对象的值

3、所有泛型算法的前两个参数都是一对迭代器

 

二、算法的泛化过程

1、将一个叙述完整的算法转化为程序代码,是任何训练有素的程序员胜任愉快的工作。

2、泛化是一个渐进过程,从具体到抽象的过程。

3、迭代器是一个行为类似指针的对象,在泛化过程中承担重要的角色。

4、STL算法在效率上的考虑甚为周详,基本上可以算是效率最佳算法,通过特定的数据结构来实现特定的算法,做算法分析时

可以看到其在时间复杂度和空间复杂度上表现很好。

 

三、算法的一些细节

1、STL的所有关系型容器都拥有自动排序功能,所以不需要用到sort算法,至于序列式容器中的stack、queue、priority queue

都有特定的出入口,不允许用户对元素排序,剩下的vector、deque,迭代器属于random access iterator,适合使用

sort算法,而list的迭代器是双向的,不适合使用sort算法。

2、sort一定要求random access iterator,sort算法在数据量大时采用Quick sort,分段递归排序,一旦分段后的数据量小于

某个门槛,就改用insertion sort,如果递归层次过深,还会改用heap sort

3、copy是一个常常被调用的函数,SGI STL的copy用尽各种办法,包括函数重载、型别特性、偏特化等,无所不用其极的加强效率。

 

四、总结

1、再好的编程技巧,也无法让一个笨拙的算法起死回生,选择了错误的算法,便注定了失败的命运。

2、特定的算法往往搭配特定的数据结构,所以掌握数据结构也是学好算法的关键。

3、算法是程序的灵魂,一个好的算法能够帮助快速有效的解决问题,并且提供一些新的思路来进行项目开发。

抱歉!评论已关闭.