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]