您的位置: 首页  >  文章  >  C++ 标准模板库STL

C++ 标准模板库STL

分类: 文章 • 2024-10-15 18:48:28

STL（Standard Template Library）即标准模板库，是一系列软件的统称。STL作为C++的一部分，目的是标准化组件，减少重复开发，可以使用现成的组件。它的底层利用了C++类模板和函数模板的机制，STL有六大组件，但主要包含容器、迭代器和算法三个部分。

  • 容器（Containers）：用来管理某类对象的集合。每一种容器都有其优点和缺点，所以，为了应付程序中的不同需求，STL 准备了七种基本容器类型。
  • 迭代器（Iterators）：用来在一个对象集合的元素上进行遍历动作。这个对象集合或许是个容器，或许是容器的一部分。每一种容器都提供了自己的迭代器，而这些迭代器了解该种容器的内部结构。
  • 算法（Algorithms）：用来处理对象集合中的元素，比如 Sort,Search,Copy,Erase 那些元素。通过迭代器的协助，我们只需撰写一次算法，就可以将它应用于任意容器之上，这是因为所有容器的迭代器都提供一致的接口。

STL容器简介

容器用来管理某类对象。为了应付程序中的不同需求，STL 准备了七种基本容器类型：向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）

总的来说，容器可分为序列式容器和关联式容器

STL提供了三个序列式容器：向量（vector）、双端队列（deque）、列表（list），其中每个元素均有固定位置——取决于插入时机和地点，和元素值无关

C++ 标准模板库STL

 STL提供了四个序列式容器：集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap），元素位置取决于特定的排序准则以及元素值，和插入次序无关

通常关联式容器由二叉树（binary tree）实现。在二叉树中，每个元素（节 点）都有一个父节点和两个子节点；左子树的所有元素都比自己小，右子树的所有元素都比自己大。

关联式容器的差别主要在于元素的类型以及处理重复元素时的方式。

1、set

概述

set（集合）由红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复。（红黑树是平衡二叉树的一种）

特点

  • set中的元素都是排好序的。
  • set集合中没有重复的元素。
  • map和set的插入删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。

优缺点和适用场景

优点：使用平衡二叉树实现，便于元素查找，且保持了元素的唯一性，以及能自动排序。
缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。
适用场景：适用于经常查找一个元素是否在某群集中且需要排序的场景。

2、multiset

概述

multiset和set相同，只不过它允许重复元素，也就是说multiset可包括多个数值相同的元素。这里不再做过多介绍。

3、map

概述

map由红黑树实现，其元素都是“键值/实值”所形成的一个对组（key/value pairs)。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。

Map主要用于资料一对一映射(one-to-one)的情况，map内部自建一颗红黑树(平衡二叉树中的一种)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。比如一个班级中，每个学生的学号跟他的姓名就存在着一对一映射的关系。

特点

  • 自动建立Key - value的对应。key 和 value可以是任意你需要的类型。
  • 根据key值快速查找记录，查找的复杂度基本是O(logN)，如果有1000个记录，二分查找最多查找10次(1024)，1,000,000个记录，二分查找最多查找20次。
  • 增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。
  • 对于迭代器来说，可以修改实值，而不能修改key。

优缺点和适用场景

优点：使用平衡二叉树实现，便于元素查找，且能把一个值映射成另一个值，可以创建字典。
缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。
适用场景：适用于需要存储一个数据字典，并要求方便地根据key找value的场景。

参考链接：https://www.cnblogs.com/linuxAndMcu/p/10254542.html

迭代器简介

迭代器是一种检查容器内元素并遍历容器的数据类型

迭代器共分为五种，其各自功能如下：

C++ 标准模板库STL

迭代器类型主要支持两类，随机访问和双向访问。其中vector和deque支持随机访问，list,set,map等支持双向访问。 

STL适配器简介

适配器是用来修改其它组件接口的STL组件，是带有一个参数的类模板。它是一个接口类为已有的类提供新的接口。适配器修改或调整其它类的接口，目的是简化、约束、使之安全、隐藏或改变被修改类提供的服务集合。当使用某个类的唯一目的就是改变其它类的接口形式时，它就是一个适配器。

STL定义了三个形式的适配器:容器适配器、迭代器适配器、函数适配器

容器适配器

STL的容器queue和stack，是在容器deque的基础进行了一些特定的约束，因而本质上并不属于容器，而是容器的适配器

 

STL算法简介

STL提供了大量实现算法的模板函数，以便减少开发人员的工作量，提高开发效率。

STL中算法大致分为四类：

  •         1、非可变序列算法：此类算法在对容器进行操作时不会改变容器的内容
  •         2、可变序列算法：此类算法一般会改变它所操作的容器的内容
  •         3、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
  •         4、数值算法：对容器内容进行数值计算

在STL通用算法中，很多算法还包括一种以函数对象作为输入参数的调用方式。

如最常用的排序算法sort就包含两种调用形式：

第一种形式：void sort(RandomAccessIterator first,RandomAccessIterator last);

该形式采用默认操作符operator进行排序，最终按照升序排列；

第二种形式：void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);

该形式按照函数对象comp规定的标准进行排序，既可以是升序，也可以是降序，或者是其它特性的规则。这样就可以通过设计相应的函数对象来达到特殊的排序要求，程序的灵活性更高。

一、不可变序列算法

不可变序列算法包括查找元素的算法、执行相等检查的算法以及对序列元素进行计数的算法。

查找元素的算法的目的主要有3个基本目的：

  • 在某种类型的集合或容器中查找某个元素的位置并返回查找结果；
  • 在某种类型的集合或容器中查找某个元素并返回该元素的值；
  • 在某种类型的集合或容器中查找某个元素并返回该元素是否在其中；

二、可变序列算法

可变序列对序列容器的操作包括复制（copy）、生成（generate）、删除（remove）、替换（resplace）、倒叙（reverse）......

三、函数对象

函数对象是STL提供的第四个主要组件，它使得STL更加的灵活方便，从而增加算法的通用性。所谓函数对象就是一个行为类似函数的对象，它不需要任何的参数，也可以带有若干参数，其功能是获得一个值，或者改变操作状态。在C++程序设计中，任何普通的函数和重载了调用运算符operator的类的对象都满足函数对象的特征，因此都可以作为函数对象传递给算法作为参数使用

 

 

 

相关推荐