鑫赢智投【可乐教育】STL概述

1. STL概述鑫赢智投

STL起源：

为的就是复用性的提升，减少人力资源的浪费，建立了数据结构与算法的一套标准。

STL所实现的、是依据泛型思维架设起来的一个概念结构。这个以抽象概念〔 abstract concepts）为主体而非以实际类(classes）为主体的结构，形成了一个严谨的接口标准。在此接口之下，任何组件都有最大的独立性，并以所谓迭代器〈 iterator）胶合起来，或以所谓配接器(adapter）互相配接，或以所谓仿函数( functor）动态选择某种策略（ policy或strategy) 。

STL六大组件

STL提供六大组件，彼此可以组合套用

容器（containers）：各种数据结构，如vector, list, deque, set, map用来存放数据，从实现角度是一种class template，提供一个模板类。算法（algorithms）：各种算法如sort,search, copy, erase…，从实现的角度来看，STL算法是一种function template。迭代器（iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有五种类型。从实现角度来看，迭代器是一种将operator*, operator->, operator++, operator–等指针相关操作给以重载的class template。所有STL容器都附带有自己专属的迭代器。仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现角度来看，仿函数是一种重载了operator()的class 或 class template。一般函数指针可视为狭义的仿函数。配接器（adapters）：一种用来修饰容器（containers）或仿函数（functors）或迭代器（iterators）接口的东西。例如，STL提供的queue和stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借助deque、所有操作都由底层的deque供应。改变 functor接口者，称为function adapter;改变container接口者,称为container adapter;改变iterator接口者，称为iterator adapter。配接器的实现技术很难一言以蔽之。配置器（allocators）：负责空间配置与管理，从实现了动态空间配置、空间管理、空间释放的class template。

展开剩余72%

2. 空间适配器（allocator）

以STL 的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作，默默付出。但若以 STL 的实现角度而言，第一个需要介绍的就是空间配置器，因为整个STL 的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料。不先掌握空间配置器的原理，难免在阅读其它STL组件的实现时处处遇到挡路石。

为什么不说allocator是内存配置器雨说它是空间配置器呢?因为空间不一定是内存，空间也可以是磁盘或其它辅助存储介质。是的鑫赢智投，你可以写—个allocator,直接向硬盘取空间。

总而言之，空间适配器分为第一级配置器（大内存）和第二级配置器（小内存），通过合理使用和回收内存来达到高效的空间使用。

3.迭代器（iterators）

不论是泛型思维或STL的实际运用，迭代器（iterators）都扮演着重要的角色。STL的中心思想在于:将数据容器（ containers）和算法（ algurithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。容器和算法的泛型化，从技术角度来看并不困难，C++的class templates和 function templates可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。

迭代器是一种smart pointer

迭代器是一种行为类似指针的对象,而指针的各种行为中最常见也最重要的便是内容提领(dereference）和成员访问( member access),因此，迭代器最重要的编程工作就是对operator* 和operator->进行重载（ overloading）工作。关于这一点，C++标准程序库有一个 auto_ptr可供我们参考。

设计适当的相应型别( associated types），是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍力自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员…)。至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以送代器为对外接口就行。

traits编程技法大量运用于STL实现品中。它利用“内嵌型别”的编程技巧与编译器的remplate参数推导功能，增强C++未能提供的关于型别认证方面的能力，妳补C++不为强型别( strong typed）语言的遗憾。了解traits 编程技法，就像获得“芝麻开r门1”的口诀-样，从此得以一窥STL源代码堂奥、

4. 序列式容器

容器：置物之所也

根据数据在容器中的排列特性分类：序列式容器和关联式容器。

这里所谓的衍生，并非派生（inheritance）关系，而是内含（containment〉关系。例如heap内含一个vector，priority-queue内含一个heap、stack 和 queue都含一个deque，set/map/multisetmultimap都内含一个RB-tree，hast_x都内含一个hashtable.

序列式容器，其中的元素都可序，但未必有序。C++本身提供了array，STL另外提供了vector, list, deque, stack, queue, priority-queue等等序列容器，其中stack和queue是将deque改投换面，技术上归结为一种配接器(adapter)。

vector

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变，要换个大（或小)一点的房子，一切琐细得由客户端自己来：首先配置–块新空间，然后将元素从旧址——搬往新址，再把原来的空间释还给系统。vector是动态

空间，随着元素的加人，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必因为害怕空间不足而一开始就要求一个大块头 array了，我们可以安心使用vector，吃多少用多少。

vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector 1旧有空间满载，如果客户端每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓扩充空间（不论多大），一如稍早所说，是“配置新空间，数据移动，释还旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑﹑稍后我们便可看到SG vector的空间配置策略。

vector维护的是一个连续线性空间,所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator* , operator->, 0perator++, operator–, operator+ , operator-,operator+=, operator-=，普通指针天生就具备。vector支持随机存取，而普通指针正有着这样的能力。所以，vector提供的是Random Access lterators。

vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。

为了降低空间配置时的速度成本，vector ‘实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（( capacity）的观念。换句话说，–个vector的容量永远大于或等于其大小。一旦容量等于大小，便是满载，下次再有新增元素，整个vector 就得另觅居所，见图4-2。

运用start, finish,end_of_storage 三个迭代器鑫赢智投，便可轻易地提供首尾标示、大小、容量、空容器判断、注标（[ ]）运算子、最前端元素值、最后端元素值…等机能;

发布于：四川省

瑞银网配资提示：文章来自网络，不代表本站观点。