STL 使用问题--概述

目录

引言

STL有六大组件

容器类型

按内存分布的分类

连续内存容器

基于节点的容器

按元素在容器中的排列特性分类

序列式容器

关联式容器

无序关联容器

容器适配器


引言

目前C++版本已经到C++23,之前的还有11, 14, 17, 20。不同编译器的不同版本所支持的STL略有不同,使用时需要注意。本系列文章将基于Effective STL 这本书罗列出目前有意义的使用问题。

执行时间,一般来说效率上,常数时间 > 对数时间 > 线性时间。

常数时间:其性能不受容器元素数量的影响。比如list中插入删除。

对数时间:与容器中元素数量n的对数成正比。如map中find。

线性时间:与容器中元素数量n成正比。标准算法count。

STL有六大组件

STL有六大组件,但主要包含容器、算法和迭代器三个部分。

容器(Containers):用来管理某类对象的集合。各种数据结构,如array、vector、list、deque、set、map、unordered_map等,用来存放数据,从实现角度来看,STL容器是一种class template。

算法(Algorithms):用来处理对象集合中的元素,各种常用的算法,如sort、find、copy、for_each。从实现的角度来看,STL算法是一种function template。

迭代器(Iterators):用来在一个对象集合的元素上进行遍历动作。扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator-> , operator++, operator–-等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数(Function object):行为类似函数,可作为算法的某种策略。从实现角度来看,仿函数是一种重载了operator()的class 或者class template。在使用到c++ stl中算法的时候,很多情况下需要传入函数对象或函数指针,传递函数对象运行效率要比函数指针高。原因是算法函数中可以根据函数对象内联展开调用的函数,而当传入函数指针时,这种内联展开的技术不可能实现,因此存在大量函数调用的情况。c++11新特性中提供了lambda函数,lambda函数是一种匿名函数,使用lambda函数的效率与使用函数对象是一样的,他们都能够在编译期将代码内联展开,减少函数调用的时间。编译器实际上将lambda函数转化为一个函数对象,所以,它与使用函数对象是一样高效的。

适配器(Adaptor):一种用来修饰容器或者仿函数或迭代器接口的东西。

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

STL 的基本观念就是将数据和操作分离。数据由容器进行管理,操作则由算法进行,而迭代器在两者之间充当粘合剂,使任何算法都可以和任何容器交互运作。通过迭代器的协助,我们只需撰写一次算法,就可以将它应用于任意容器之上,这是因为所有容器的迭代器都提供一致的接口。

STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略的变化,适配器可以修饰仿函数。

容器类型

STL 使用问题--概述

 

按内存分布的分类

连续内存容器

是基于数组的容器,元素存放在一块或多块内存中,每块内存中存有对个元素,当插入或删除时,同一个内存中的其他元素要向前或向后移动,这种移动影响效率和异常安全性。支持随机访问迭代器

基于节点的容器

每一个动态分配的内存块中只存放一个元素。容器中插入或删除值影响到指向节点的指针,而不影响节点本身的内容。链表和红黑树支持双向访问迭代器哈希表只支持前向迭代器

按元素在容器中的排列特性分类

序列式容器

序列式容器实现能按顺序访问的数据结构,不是数值顺序。其中每个元素均有固定位置—取决于插入时机和地点,和元素值无关。如果你以追加方式对一个群集插入六个元素,它们的排列次序将和插入次序一致。STL提供了以下几种序列式容器:

array(C++11)

静态的连续数组(类模板)

vector

动态的连续数组(类模板)

deque

双端队列(类模板)

forward_list(C++11 起)

单链表(类模板)

list

双链表(类模板)

关联式容器

每个元素位置取决于特定的排序准则以及元素值,和插入次序无关。关联容器基于【红黑树】。实现能快速查找( O(log n) 复杂度)的数据结构。

set

唯一键的集合,按照键排序(类模板)

map

键值对的集合,按照键排序,键是唯一的(类模板)

multiset

键的集合,按照键排序(类模板)

multimap

键值对的集合,按照键排序(类模板)

无序关联容器

每个元素位置取决于特定的排序准则以及元素值,和插入次序无关。无序关联容器基于【哈希表】。无序关联容器提供能快速查找(均摊 O(1) ,最坏情况 O(n) 的复杂度)的无序(哈希)数据结构。

unordered_set(C++11 起)

唯一键的集合,按照键生成散列(类模板)

unordered_map(C++11 起)

键值对的集合,按照键生成散列,键是唯一的(类模板)

unordered_multiset(C++11 起)

键的集合,按照键生成散列(类模板)

unordered_multimap(C++11 起)

键值对的集合,按照键生成散列(类模板)

容器适配器

容器适配器提供顺序容器的不同接口。

stack

适配一个容器以提供栈(LIFO 数据结构)(类模板)

queue

适配一个容器以提供队列(FIFO 数据结构)(类模板)

priority_queue

适配一个容器以提供优先级队列(类模板)

以上是对stl的简单介绍,在后续的文章中在列出使用中的问题。


凡是过往,即为序章

上一篇:C/C++编程:STL 迭代器源码与 traits 编程学习


下一篇:养猪日记 2022.1.22