043-C++之STL理论基础
本帖最后由 moc 于 2018-9-19 19:25 编辑1、基本概念
STL(Standard Template Library):是惠普实验室开发的一系列的软件的统称,现在主要出现在C++中,但被引入C++之前该技术就已经存在很长时间。
STL从广义可以分为三类: algorithm(算法)、container(容器)、iterator(迭代器)。
容器和算法通过迭代器可以进行无缝连接,其中所有的代码都采用了类模板和模板函数的方式,这比传统的由函数和类组成的库提供了更好的代码重用。
C++标准中,STL被组织为13个头文件:
<algorithm>、<deque>、<functional>、<iterator>、<vector> 、<list>、<memory>、<map>、<numeric>、<queue>、<set>、<stack>、<utility>。
STL六大组件:-容器(Container) -算法(Algorithm)
-迭代器(Iterator) -仿函数(Function object)
-适配器(Adaptor) -空间适配器(allocator)
使用STL的好处:
① STL为C++的一部分,因此不需要安装什么,他已被内嵌于编译器之内。
② STL的重要的特点:将算法和数据结构分离,这样使得STL变得非常通用。
如:vector容器中可以放基础类型数据,也可以结构体、类、指针等。
STL的sort()函数可以用来操作vector、list等容器。
③ STL已优化和封装得很好,程序员只需熟练使用STL,不需考虑其具体实现过程。
④ STL具有高可重用性<模板技术>、高性能<如map采用红黑数的变体实现>、高移植性、跨平台<可用于Windows、macOS等>系统等优点。
⑤ STL已是C++荣耀的一部分,STL是C++程序的一项不可或缺的基本技能,掌握它对提升C++编程大有裨益,只有熟练使用STL的程序员才是好的C++程序员,需要深入理解在什么情况下使用哪个容器和算法。
2、容器
在实际的开发中,数据结构本身的重要性不亚于数据结构算法的重要性。当程序存在着对时间要求很高的部分时,数据结构的选择尤为重要。STL容器对常用的数据结构提供了支持,这些模板参数允许我们指定容器中的数据类型,可将我们许多重复而乏味的工作得到简化。
1. 容器的概念
用来管理一组元素.
2. 容器的分类
序列式容器(Sequence container):每个元素都有固定的位置—取决于插入的时机和地点和元素值无关。有:vector、deque、list...
关联式容器(Associated container):元素的位置取决于特定的排序准则和插入顺序无关。有:set、multiset、map、multimap...
数据结构|描述|实现头文件
向量(vector)|连续存储的元素|<vector>
列表(list)|由结点组成双向链表,每个结点包含一个元素|<list>
双端队列(deque)|连续存储的指向不同元素的指针所组成的数组|<deque>
集合(set)|由结点组成的红黑树,每个结点包含一个元素|<set>
多重集合(multiset)|允许存在两个次序相等的元素集合|<set>
栈(stack)|先进后出的值的排序|<stack>
队列(queue)|先进先出的值的排序|<queue>
优先队列(priority_queue)|元素次序由所存储的值对上某种谓词决定的队列|<queue>
映射(map)|由键值对组成的集合|<map>
多重映射(multimap)|允许存在相等次序的映射|<map>
3、迭代器
迭代器是一种检查容器内元素并遍历元素的数据类型。C++更趋向于使用迭代器而不是下标操作,因为标准库为每一种标准容器(如vector)定义了一种迭代器类型,而只用少数容器(如vector)支持下标操作访问容器元素。
在STL中,迭代器主要分为5类。各自是:输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机訪问迭代器。
输入迭代器:仅仅读。支持++、==、!=;
输出迭代器:仅仅写,支持++;
前向迭代器:读写,支持++、==、!=。
双向迭代器:读写,支持++、--。 C++的全部标准库容器都至少在双向迭代器的层次上。
随机訪问迭代器:读写,支持++、--、、-n、<、<=、>、>=。
用迭代器访问容器中的数据:
vector<int>v(1,2,3,4,5);
for(auto iter = v.begin(); i != v.end(); i++) {
cout << *iter << endl;
}
4、算法
STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。
① 非可变序列算法:指不直接修改其所操作的容器内容的算法。
② 可变序列算法:指可以修改它们所操作的容器内容的算法。
③ 排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
④ 数值算法:对容器内容进行数值计算。
5、C++标准库
官方文档:传送门
博文参见:传送门
页:
[1]