从零开始学C++之STL(一):STL六大组件简介

一、STL简介

(一)、泛型程序设计

泛型编程(generic programming) 将程序写得尽可能通用 将算法从数据结构中抽象出来,成为通用的 C++的模板为泛型程序设计奠定了关键的基础

(二)、什么是STL

1、STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。

2、包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性

3、从逻辑层次来看,在STL中体现了泛型化程序设计的思想(generic programming) 在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的方式处理各种不同情形。

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

基于模板(template)

二、STL组件

Container(容器) 各种基本数据结构

Adapter(适配器) 可改变containers、Iterators或Function object接口的一种组件

Algorithm(算法) 各种基本算法如sort、search…等

Iterator(迭代器) 连接containers和algorithms

Function object(函数对象) 

Allocator(分配器)

(一)、容器

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

七种基本容器:

向量(vector)、双端队列(deque)、列表(list)、集合(set)、多重集合(multiset)、映射(map)和多重映射(multimap)

标准容器的成员绝大部分都具有共同的名称

序列式容器

序列式容器Sequence containers,其中每个元素均有固定位置——取决于插入时机和地点,和元素值无关。(vector、deque、list)

关联式容器

关联式容器Associative containers,元素位置取决于特定的排序准则以及元素值,和插入次序无关。(set、multiset、map、multimap)

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

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

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

set/map/multiset/multimap 

set,同map一样,所有元素都会根据元素的键值自动被排序,因为set/map两者的所有各种操作,都只是转而调用RB-tree的操作行为,不过,值得注意的是,两者都不允许两个元素有相同的键值。

不同的是:set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素同时拥有实值和键值,且实值就是键值,键值就是实值,而map的所有元素都是pair,同时拥有实值(value)和键值(key),pair的第一个元素被视为键值,第二个元素被视为实值。

    至于multiset/multimap,他们的特性及用法和set/map完全相同,唯一的差别就在于它们允许键值重复,即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。In computer science, a multimap (sometimes also multihash) is a generalization of a map or associative arrayabstract data type in which more than one value may be associated with and returned for a given key.

摘自 sgi stl 红黑树数据结构定义:

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;
 
struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;
 
  _Color_type _M_color;
  _Base_ptr _M_parent;
  _Base_ptr _M_left;
  _Base_ptr _M_right;
 
  static _Base_ptr _S_minimum(_Base_ptr __x)
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }
 
  static _Base_ptr _S_maximum(_Base_ptr __x)
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};
 
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;
};

hash_set/hash_map/hash_multiset/hash_multimap

hash_set/hash_map,两者的一切操作都是基于hashtable之上。不同的是,hash_set同set一样,同时拥有实值和键值,且实值就是键值,键值就是实值,而hash_map同map一样,每一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上,所以不具备自动排序功能。为什么? 因为hashtable没有自动排序功能。

至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同,唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable(而multiset/multimap,上面说了,底层实现机制是RB-tree),所以它们的元素都不会被自动排序,不过也都允许键值重复。

所以说白了,什么样的结构决定其什么样的性质,因为set/map/multiset/multimap都是基于RB-tree之上,所以有自动排序功能,而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上,所以不含有自动排序功能,至于加个前缀multi_无非就是允许键值重复而已。

std::tr1::unordered_map 是无序哈希表,但操作效率要比 std::map、std::hash_map、 __gnu_cxx::hash_map 都要高,可以研究一下。

(二)、迭代器

1、迭代器Iterators,用来在一个对象群集(collection of objects)的元素上进行遍历。这个对象群集或许是个容器,或许是容器的一部分。迭代器的主要好处是,为所有容器提供了一组很小的公共接口。迭代器以++进行累进,以*进行提领,因而它类似于指针,我们可以把它视为一种smart pointer。

2、比如++操作可以遍历至群集内的下一个元素。至于如何做到,取决于容器内部的数据组织形式。

3、每种容器都提供了自己的迭代器,而这些迭代器能够了解容器内部的数据结构。

(三)、算法

算法Algorithms,用来处理群集内的元素。它们可以出于不同的目的而搜寻、排序、修改、使用那些元素。通过迭代器的协助,我们可以只需编写一次算法,就可以将它应用于任意容器,这是因为所有的容器迭代器都提供一致的接口。

(四)、适配器

1、适配器是一种接口类 为已有的类提供新的接口 目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合

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

(五)、函数对象

1、函数对象(function object)也称为仿函数(functor) 2、一个行为类似函数的对象,它可以没有参数,也可以带有若干参数。 3、任何重载了调用运算符operator()的类的对象都满足函数对象的特征 4、函数对象可以把它称之为smart function。 5、STL中也定义了一些标准的函数对象,如果以功能划分,可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象,需要包含头文件<functional>。

(六)、分配器

负责空间配置与管理。从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

隐藏在这些容器后的内存管理工作是通过STL提供的一个默认的allocator实现的。当然,用户也可以定制自己的allocator,只要实现allocator模板所定义的接口方法即可,然后通过将自定义的allocator作为模板参数传递给STL容器,创建一个使用自定义allocator的STL容器对象,如: stl::vector<int, UserDefinedAllocator> array;

大多数情况下,STL默认的allocator就已经足够了。这个allocator是一个由两级分配器构成的内存管理器,当申请的内存大小大于128byte时,就启动第一级分配器通过malloc直接向系统的堆空间分配,如果申请的内存大小小于128byte时,就启动第二级分配器,从一个预先分配好的内存池中取一块内存交付给用户,这个内存池由16个不同大小(8的倍数,8~128byte)的空闲列表组成,allocator会根据申请内存的大小(将这个大小round up成8的倍数)从对应的空闲块列表取表头块给用户。

这种做法有两个优点:

(1)小对象的快速分配。小对象是从内存池分配的,这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用,当内存池耗尽时再向系统申请一块新的区域,整个过程类似于批发和零售,起先是由allocator向总经商批发一定量的货物,然后零售给用户,与每次都向总经商要一个货物再零售给用户的过程相比,显然是快捷了。当然,这里的一个问题时,内存池会带来一些内存的浪费,比如当只需分配一个小对象时,为了这个小对象可能要申请一大块的内存池,但这个浪费还是值得的,况且这种情况在实际应用中也并不多见。

(2)避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片,给操作系统的内存管理带来了很大压力,系统中碎片的增多不但会影响内存分配的速度,而且会极大地降低内存的利用率。以内存池组织小对象的内存,从系统的角度看,只是一大块内存池,看不到小对象内存的分配和释放。

参考:

C++ primer 第四版 Effective C++ 3rd C++编程规范

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏知识分享

51单片机开发板(W25Q16学习)

---恢复内容开始--- 今天测试开发板的W25Q16(16Mbit--Flash)写一篇文章备忘一下 先说一下容量的单位 计算机存储单位一般用B,KB、MB、...

3224
来自专栏SDNLAB

Open vSwitch源码解析之基于VxLAN实现NSH解析功能

1. NSH-SFC概述 当前SFC的实现方案主要分为两种:一种基于NSH(network service header)。数据封装时,在L2或者L3数据后添加...

4255
来自专栏架构师之路

如何设计好的接口(Google分享)

本文源自Google工程师joshua bloch的经验分享,楼主进行了整理和总结。 一、好接口的特性 (1)易学 (2)易用,甚至不需要文档 (3)难于误用 ...

3446
来自专栏牛客网

知识总结:C++工程师106道面试题总结(含答案详解)

可以说个人秋招就要结束了,就等两个offer通知,然后签完搞定,这里提供一下自己复习的东西吧,我也就把这个东西给搞了一遍,然后面试基本没啥问题了,如果问的很深的...

3269
来自专栏Java学习网

60条面向对象设计原则

60条面向对象设计原则 你不必严格遵守这些原则,违背它们也不会被处以宗教刑罚。但你应当把这些原则看成警铃,若违背了其中的一条,那么警铃就会响起...

2286
来自专栏加米谷大数据

Redis数据类型及应用场景

通常我们都把数据存到关系型数据库中,但为了提升应用的性能,我们应该把访频率高且不会经常变动的数据缓存到内存中。Redis 没有像 MySQL 这类关系型数据库那...

812
来自专栏携程技术中心

干货 | 深入理解Python装饰器

作者简介 曾凡伟,携程信息安全部高级安全工程师,2015年加入携程,主要负责安全自动化产品的设计和研发,包括各类扫描器、漏洞管理平台、安全SaaS平台等。 Py...

2884
来自专栏瓜大三哥

文件地址映射之yaffs_GetTnode

yaffs文件系统在更新文件数据的时候,会分配一块新的chunk,也就是说,同样的文件偏移地址,在该地址上的数据更新前和更新后,其对应的flash上的存储地址是...

1676
来自专栏我的技术专栏

Socket编程(4)TCP粘包问题及解决方案

803
来自专栏微服务生态

由学习《软件设计重构》所想到的代码review(二)

我们接第一篇来继续说明在代码review中,有哪些属于“层次结构”中的坏味道。 第一篇链接如下:http://www.jianshu.com/p/07dbf6...

702

扫码关注云+社区