STL六大组件

xiaoxiao2021-02-28  9

一、什么是STL 1、STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。 2、包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性

3、从逻辑层次来看,在STL中体现了泛型化程序设计的思想(generic programming)

在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的方式处理各种不同情形。

4、从实现层次看,整个STL是以一种类型参数化(type parameterized)的方式实现的 基于模板(template)

二、STL组件 STL提供六大组件,彼此可以组合套用:

1、 Container(容器) :各种数据结构。用来存放数据。从实现的角度来看,STL容器是一种class template。

容器类是容纳、包含一组元素或元素集合的对象。

<1>顺序容器: (1)向量(vector):一维动态数组,一次开辟2倍,默认构造无内存。 分配:1,2,4,8….,为了减小初始内存分配频率,可以调用reserve,reserve只开辟内存。 reserve(100)和resize(100)的区别:reserve(100)只开辟空间,resize(100)不仅开辟内存,还增加了元素个数。

add: push_back(val)//O(1), insert(it,val)//O(n) delete: erase(it) / erase(first,last)//O(n) , pop_back()//O(1) query:find(first,last,value)//O(n) modify: 先find返回一个迭代器,再*it=修改的值. O(n) 随机访问[I] //O[1] (2)双端队列(deque):二维动态数组,一维增长2倍,二维4096/sizeof(int),默认构造是空的。

add: push_back(val)//O(1), push_front(val)//O(1),insert(it,val)//O(n) delete: erase(it) / erase(first,last)//O(n) , pop_front()/pop_back()//O(1) query:find(first,last,value)//O(n) modify: 先find返回一个迭代器,再*it=修改的值. O(n) (3)双向链表(list):默认只生成头结点

add: push_back(val)//O(1), push_front(val)//O(1),insert(it,val)//O(1) delete: erase(it) / erase(first,last)//O(n) , pop_front()/pop_back()//O(1) query:find(first,last,value)//O(n) modify: 先find返回一个迭代器,再*it=修改的值. O(n)

<2>关联容器: add,delete,query: (1)集合(set):所有元素都会根据元素的键值自动被排序,因为set/map两者的所有各种操作,都只是转而调用RB-tree的操作行为,不过,值得注意的是,两者都不允许两个元素有相同的键值。set的键值就是实值,实值就是键值。 (2)多重集合(multiset):和set特性及用法完全相同,唯一的差别就在于它允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。 (3)映射(map):和set一样,map第一个元素为键值,第二个元素为实值。 (4)多重映射(multimap):和map特性及用法完全相同,唯一的差别就在于它允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

需要频繁在序列中间位置上进行插入和/或删除操作且不需要过多地在序列内部进行长距离跳转,应该选择list

vector头部与中间插入删除效率较低,在尾部插入与删除效率高。

deque是在头部与尾部插入与删除效率较高

2、 Algorithm(算法) : (1)算法Algorithms,用来处理群集内的元素。它们可以出于不同的目的而搜寻、排序、修改、使用那些元素。通过迭代器的协助,我们可以只需编写一次算法,就可以将它应用于任意容器,这是因为所有的容器迭代器都提供一致的接口。 (2)各种常用算法,如:sort、search、copy、erase。从实现的角度来看,STL算法是一种 function template。 3、 Iterator(迭代器): (1)容器与算法之间的胶合剂,是所谓的“泛型指针”。共有五种类型,以及其他衍生变化。从实现的角度来看,迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。 (2)迭代器Iterators,用来在一个对象群集(collection of objects)的元素上进行遍历。这个对象群集或许是个容器,或许是容器的一部分。迭代器的主要好处是,为所有容器提供了一组很小的公共接口。迭代器以++进行累进,以*进行提领,因而它类似于指针,我们可以把它视为一种smart pointer (3)所有STL容器都有自己专属的迭代器,只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。 4、 Function object(函数对象) : (1)、函数对象(function object)也称为仿函数(functor) (2)、一个行为类似函数的对象,它可以没有参数,也可以带有若干参数。 (3)、任何重载了调用运算符operator()的类的对象都满足函数对象的特征 (4)、函数对象可以把它称之为smart function。 (5)、STL中也定义了一些标准的函数对象,如果以功能划分,可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象,需要包含头文件。 5、Adapter(适配器) : 一种用来修饰容器、仿函数、迭代器接口的东西。 (1)、适配器是一种接口类 为已有的类提供新的接口 目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合

(2)、三种类型的适配器: 容器适配器:用来扩展7种基本容器,它们和顺序容器相结合构成栈、队列和优先队列容器 迭代器适配器(反向迭代器、插入迭代器、IO流迭代器) 函数适配器(函数对象适配器、成员函数适配器、普通函数适配器)

例如:STL提供的queue 和 stack,虽然看似容器,但其实只能算是一种容器配接器,因为它们的底部完全借助deque,所有操作都由底层的deque供应。改变 functors接口者,称为function adapter;改变 container 接口者,称为container adapter;改变iterator接口者,称为iterator adapter。 6、Allocator(分配器): 负责空间配置与管理。从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

这六大组件的交互关系: 容器通过分配器取得数据储存空间; 算法通过迭代器存取容器内容; 函数对象可以协助算法完成不同的策略变化; 适配器可以修饰或套接函数对象。

转载请注明原文地址: https://www.6miu.com/read-1400413.html

最新回复(0)