网站建设详细需求文档,昆山网站建设 熊掌号,网站建设新闻发布注意事项,电子商务网站开发背景文章目录#x1f4ac; 一.前言二.STL基本概念和组成①容器②算法③迭代器④空间配置器⑤适配器⑥仿函数 三.STL工作机制 一.前言
长久以来#xff0c;软件界一直希望建立一种可重复利用的东西#xff0c;以及一种得以制造出“可重复运用的东西”的方法,让程序员的心血不止于… 文章目录 一.前言二.STL基本概念和组成①容器②算法③迭代器④空间配置器⑤适配器⑥仿函数 三.STL工作机制 一.前言
长久以来软件界一直希望建立一种可重复利用的东西以及一种得以制造出“可重复运用的东西”的方法,让程序员的心血不止于随时间的迁移人事异动而烟消云散从函数(functions)类别(classes),函数库(function libraries),类别库(class libraries)、各种组件从模块化设计到面向对象(object oriented )到模式(pattern)的归纳整理为的就是复用性的提升。
复用性必须建立在某种标准之上。但是在许多环境下就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作竟然是为了完成前人已经完成而自己手上并未拥有的程序代码这不仅是人力资源的浪费也是挫折与痛苦的来源。
为了建立数据结构和算法的一套标准并且降低他们之间的耦合关系以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。
二.STL基本概念和组成
STL是惠普实验室开发的一系列标准化组件的统称。它是由Alexander Stepanov、M eng Lee和David R.M usser在惠普实验室工作时开发出来的。在1994年STL被纳入C标准成为C库的重要组成部分。STL主要由六个部分组成
空间配置器Allocator适配器Adapters容器Containers迭代器Iterator仿函数Functors)算法Algorithm STL的一个基本理念就是将数据和操作分离数据由容器加以管理操作则由可定制的算法完成迭代器在两者之间充当“黏合剂”。 STL的组件结构图如下图所示
①容器
容器置物之所也。容器是存储其他对象的对象它存储的对象可以是自定义数据类型的对象也可以是内置数据类型的对象。这些被存储的对象必须是同一种数据类型它们归容器所有称为容器的元素。当容器失效时容器中的元素也会失效。容器本身包含了处理这些数据的方法。 从实现角度来看STL容器是一种class template类模板。 STL容器是将运用最广泛的一些数据结构实现出来。数组(array),链表(list),tree(树)栈(stack),队列(queue),集合(set),映射表(map),根据数据在容器中的排列特性这些数据分为序列式容器和关联式容器两种。 序列式容器就是容器元素在容器中的位置是由元素进入容器的时间和地点来决定。Vector容器、Deque容器、List容器、Stack容器、Queue容器。关联式容器是指容器已经有了一定的规则容器元素在容器中的位置由我的规则来决定。Set/multiset容器 Map/multimap容器
STL中的容器共有13种
②算法
算法问题之解法也。以有限的步骤解决逻辑或数学上的问题这一门学科我们叫做算法(Algorithms). STL收录的算法经过了数学上的效能分析与证明是极具复用价值的包括sort、find、copy、for_each等。 从实现角度看算法是STL定义的一系列函数模板是STL非常重要的一部分内容。算法可以对容器中的元素施加特定操作。STL算法不依赖于容器的实现细节只要容器的迭代器符合算法要求算法就可以通过迭代器处理容器中的元素。 算法分为:质变算法和非质变算法。
质变算法是指运算过程中会更改区间内的元素的内容。例如拷贝替换删除等。非质变算法是指运算过程中不会更改区间内的元素内容例如查找、计数、遍历、寻找极值等等
③迭代器 迭代器是一个广义指针。事实上它可以是指针也可以是一个可对其执行类似指针的操作的类模板共有五种类型从实现角度来看迭代器是一种将operator* , operator- , operator,operator–等指针相关操作予以重载的class template. 。通过将指针广义化为迭代器让STL能够为各种不同的容器类包括那些简单指针无法处理的类提供统一的接口。所有STL容器都附带有自己专属的迭代器只有容器的设计者才知道如何借助迭代器使之能够依序寻访某个容器所含的各个元素而又无需暴露该容器的内部表示方式。该迭代器的类型是一个名为iterator的typedef其作用域为整个类。 总结 迭代器是STL提供的用于操作容器中元素的类模板其行为类似于指针STL算法利用迭代器遍历容器中的元素迭代器本身也提供了操作容器元素的方法使容器元素访问更便捷。迭代器将容器与算法联系起来起到了“黏合剂”的作用STL提供的算法几乎都通过迭代器实现元素访问。 STL提供了输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器五种类型的迭代器使用迭代器访问容器元素更简单、易用且代码更加紧凑、简洁。
种类功能输入迭代器提供对数据的只读访问只读支持、、输出迭代器提供对数据的只写访问只写支持前向迭代器提供读写操作并能向前推进迭代器读写支持、、双向迭代器提供读写操作并能向前和向后操作读写支持、- -随机访问迭代器提供读写操作并能在数据中随机移动读写支持、- -、[n]、-n、、、、
④空间配置器
C标准库采用了空间配置器实现对象内存空间的分配和归还空间配置器是特殊的内存模型。例如使用vector容器存储数据的空间由空间配置器完成内存的分配和资源回收。空间配置器本质上是对new和delete运算符再次封装而成的类模板对外提供可用的接口实现内存资源的自动化管理。
⑤适配器
适配器主要指容器适配器。容器适配器也是一类容器它除了能存储普通数据还可以存储list、vector、deque等容器。容器适配器采用特定的数据管理策略能够使容器在操作数据时表现出另一种行为。例如使用容器适配器stack封装一个vector容器使vector容器在处理数据时表现出栈这种数据结构的特点先进后出。 STL提供了三个容器适配器
stack栈queue队列priority_queue优先队列。
适配器体现了STL设计的通用性极大提高了编程效率。
⑥仿函数
仿函数通过重载函数调用符号()运算符实现使类具有函数一样的行为。仿函数也称为函数对象是STL很重要的组成部分它使STL的应用更加灵活方便增强了算法的通用性。大多数STL算法可以使用一个仿函数作为参数以达到某种数据操作的目的。例如在排序算法中可以使用仿函数less或greater作为参数以实现数据从大到小或从小到大的排序。
三.STL工作机制
通过自己书写一个数组容器来了解算法和容器是怎样分离的并且了解迭代器是怎样充当粘合剂。
#include iostream
using namespace std;
//数组容器
templateclass T
class MyArray
{
public://保护原生指针给原生指针取别名这个别名就是迭代器。typedef T* iterator;//迭代器类型MyArray(){mCapacity 10;mSize 10;p new T[mCapacity];for (int i 0; i mCapacity; i){p[i] i 1;}}//提供迭代器开始位置的迭代器T* begin(){return p;}//返回结束位置的迭代器T* end(){return p mSize;}
public:T* p;int mCapacity;//数组容量int mSize;//数组当前元素个数
};
//算法
//要遍历整个容器只需获得容器首尾迭代器即可这样就把容器和算法分离
//如果没有迭代器就需要将算法写在容器内只要用到算法就要先创建容器很麻烦。
templateclass T
void printArray(T begin,T end)
{for (; begin ! end; begin){cout *begin ;}
}
void test()
{MyArrayint arr;//获取容器提供的开始位置迭代器MyArrayint::iterator beginarr.begin();//获取容器提供的结束位置迭代器MyArrayint::iterator end arr.end();printArray(begin, end);
}
