043-C++之STL理论基础

moc

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]、-n、<、<=、>、>=。
用迭代器访问容器中的数据：

1. vector<int>v(1,2,3,4,5);
   
2. for(auto iter = v.begin(); i != v.end(); i++) {
   
3.   cout << *iter << endl;
   
4. }

复制代码

4、算法
STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。
       ① 非可变序列算法：指不直接修改其所操作的容器内容的算法。
       ② 可变序列算法：指可以修改它们所操作的容器内容的算法。
       ③ 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
       ④ 数值算法：对容器内容进行数值计算。
5、C++标准库
官方文档：传送门
博文参见：传送门