C++ STL 容器

2021-10-09 23:23:56

什么是STL

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表，容器和数组；

STL另一个重要特性是它不是面向对象的。 为了具有足够通用性，STL主要依赖于模板而不是封装，继承和虚函数（多态性）——OOP的三个要素。你在STL中找不到任何明显的类继承关系。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特征。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效；

从逻辑层次来看，在STL中体现了泛型化程序设计的思想，引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术；

从实现层次看，整个STL是以一种类型参数化的方式实现的，这种方式基于一个在早先C++标准中没有出现的语言特性--模板（template）。

STL内容

STL中六大组件：

容器（Container），是一种数据结构，如 list，vector，和 deques ，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器；
迭代器（Iterator），提供了访问容器中对象的方法。例如，可以使用一对迭代器指定 list 或 vector 中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是，迭代器也可以是那些定义了 operator*() 以及其他类似于指针的操作符地方法的类对象；
算法（Algorithm），是用来操作容器中的数据的模板函数。例如，STL用 sort() 来对一个 vector 中的数据进行排序，用 find() 来搜索一个 list 中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；
仿函数（Functor）
适配器（Adaptor）
分配器（allocator）

容器

STL中的容器有序列式容器，关联容器，容器适配器（congtainer adapters：stack, queue，priority queue，位集（bit_set，串包(string_package)等等。

(1) 序列式容器（Sequence containers），每个元素都有固定位置，元素位置取决于插入时机和地点，和元素值无关，array、vector、deque、list；

Vector：将元素置于一个动态数组中加以管理，可以随机存取元素（用索引直接存取），数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时；
Deque：是“double-ended queue”的缩写，可以随机存取元素（用索引直接存取），数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时；
List：双向链表，不提供随机存取（按顺序走到需存取的元素，O(n)），在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针；

(2) 关联式容器（Associated containers），元素位置取决于特定的排序准则，和插入顺序无关，set、multiset、map、multimap等。

Set/Multiset：内部的元素依据其值自动排序，Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素，内部由二叉树实现，便于查找；
Map/Multimap：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现，便于查找；

(3) 容器适配器，适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，STL 中包含三种适配器：stack 、queue 和priority_queue 。

Stack: 默认基于deque实现
Queue: 默认基于deque实现
Priority_queue: 默认基于vector实现

除上述容器外，c++ 11中又增加了无序容器：unordered_map,unordered_multimap,unordered_set,unordered_multiset。

容器类自动申请和释放内存，无需new和delete操作。

Array & Vector容器

Array&Vector笔记

Queue & Deque容器

Queue & Deque笔记

list容器

List 笔记

map/multimap 容器

map & multimap 笔记

priority_queue 容器

priority_queue 笔记

STL算法

STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。要使用 STL中的算法函数必须包含头文件<algorithm>，对于数值算法须包含<numeric>，<functional>中则定义了一些模板类，用来声明函数对象。
STL中算法大致分为四类：

非可变序列算法：指不直接修改其所操作的容器内容的算法。
可变序列算法：指可以修改它们所操作的容器内容的算法。
排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
数值算法：对容器内容进行数值计算。

查找算法

iterator adjacent_find(iterator beg, iterator end): 在[beg, end)范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回 end()。
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);: 在有序序列中使用二分查找法查找val，找到返回true。
size_t count(Iterator first, Iterator last, const T& val): 利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。
size_t count_if(Iterator first, Iterator last, const T& val, Compare comp):利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);: 底层采用二分查找法，必须是排序好的序列。该函数会返一个 pair 类型值，其包含 2 个正向迭代器。当查找成功时：第 1 个迭代器指向的是 [first, last) 区域中第一个等于 val 的元素；第 2 个迭代器指向的是 [first, last) 区域中第一个大于 val 的元素。反之如果查找失败，则这 2 个迭代器要么都指向大于 val 的第一个元素（如果有），要么都和 last 迭代器指向相同。
InputIterator find(InputIterator first, InputIterator last, const T& val);: 查找val元素，查找成功返回一个迭代器
ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2);: 查找序列 [first1, last1) 中最后一个子序列 [first2, last2)，[first2, last2)为要查找的序列。
InputIterator find_first_of (InputIterator first1, InputIterator last1,ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);：pred 可接收一个包含 2 个形参且返回值类型为 bool 的函数
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);: 组合 [first, last) 用于指定要查找的区域；pred 用于自定义查找规则。
lower_bound

//在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);

search

//查找 [first1, last1) 范围内第一个 [first2, last2) 子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2);
//查找 [first1, last1) 范围内，和 [first2, last2) 序列满足 pred 规则的第一个子序列
ForwardIterator search (ForwardIterator first1, ForwardIterator last1,
                        ForwardIterator first2, ForwardIterator last2,
                        BinaryPredicate pred);

search_n

//在 [first, last] 中查找 count 个 val 第一次连续出现的位置
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                          Size count, const T& val);
//在 [first, last] 中查找第一个序列，该序列和 count 个 val 满足 pred 匹配规则
ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                           Size count, const T& val, BinaryPredicate pred );

码农公寓