编程参考 - C++ STL 容器概览

之前我们已经看过了C++数组array和向量容器vector containers，看到了为什么这些容器比标准的C风格的数组更好。

我们还了解到，容器可以利用诸如SBRM设计模式和基于范围的for循环(range-based for loops)等习语。

注：SBRM：“scope-bound resource management”，表示资源的申请和释放被封装起来，不需要用户来实现或 *** 心。

现在我们已经深入研究了两个容器（以及伪容器std::string），我想对其余的C++容器做一个概述。

目录

1. The Standard Containers 标准容器

    1.1 Sequence Containers 序列容器

    1.2 Container Adapters 容器适配器

    1.3 Associative Containers  关联容器

    1.4 Unordered Associative Containers 无序关联容器

2. Reasons to Use Standard Containers  使用标准容器的理由

3. Standard Container Thread Safety  标准容器的线程安全

1，标准容器

容器库是一个模板和算法的集合，实现了我们作为程序员工作常用的数据结构。

容器是一个存储元素elements（即其他对象）集合的对象。

每个容器为其元素管理存储空间，并通过迭代器和/或成员函数提供对每个元素的访问。

标准的容器实现了我们程序中常用的结构，比如说：

dynamic arrays  动态数组

queues 队列

stacks   堆栈

linked lists 链接列表

trees  树

associative sets  关联集合

我喜欢STL容器，因为它们消除了我在每个项目上重新实现的一整套样板代码。

容器库还得益于成员函数的标准化接口。

这些标准化的接口减少了你的记忆负担，并允许容器与STL算法一起使用。

C++容器库将容器分为四种类型：

* Sequence containers  序列式容器

* Sequence container adapters  序列容器适配器

* Associative containers  关联式容器

* Unordered associative containers  无序的关联容器

让我们来深入了解每个类别。

1.1 序列容器 Sequence containers 

序列容器是为了用来以线性方式存储相同类型对象的数据结构。

STL SequenceContainer的类型有：

* array represents a static contiguous array

* vector represents a dynamic contiguous array

* forward_list represents a singly-linked list

* list represents a doubly-linked list

* deque represents a double-ended queue, where elements can be added to the front or back of the queue.

 * array代表一个静态的连续数组

 * 向量代表一个动态连续的数组

 * forward_list代表一个单链的列表

 * list代表一个双链的列表

 * deque代表一个双端队列，其中元素可以被添加到队列的前面或后面。

  

虽然std::string不包括在大多数容器列表中，但事实上它确实符合SequenceContainer的要求。

1.2 序列容器适配器  Sequence container adapters

容器适配器是一种特殊类型的容器类。

它们本身不是完整的容器类，而是其他容器类型（如vector, deque, 或 list）的包装器。

这些容器适配器封装了底层的容器类型并相应地限制了用户接口。

让我们看一下 std::stack。

std::stack 是一个强制执行 LIFO 型数据结构的容器。

下面是std::stack的声明：

template<

    class T,

    class Container = std::deque

> class stack;

注意，Container默认包装了一个std::deque。

实际上你可以将底层容器的类型改为另一个STL SequenceContainer或你自己的自定义容器。

你指定的容器必须满足以下要求：

 - 该容器必须满足SequenceContainer的要求

 - 必须提供back()、push_back()和pop_back()接口

STL容器std::vector、std::deque和std::list都满足这些要求，可以用于底层存储。

标准模板库的容器适配器有：

 - stack    提供了一个LIFO数据结构

 - queue  提供了一个FIFO数据结构

 - priority_queue   提供了一个优先级队列，它允许以固定时间的性能进行查找最大的元素（默认情况下）。

1.3 关联式容器 Associative containers

关联容器提供了排序的数据结构，提供了使用键（keys）的快速查找（O(log n)时间的时间复杂度）。

STL的关联容器类型可以分为两种：需要唯一键的容器，以及允许多个条目(entries)使用同一键的容器。

- 键是唯一的情况

    - set是一个键的集合，每个键都是唯一的，按照键进行排序

    - map是一个键值对的集合，按照键进行排序。

    - set和map通常使用红黑树实现。

 - 多个条目允许使用同一个键的情况

    - multiiset是一个键的集合，按照键进行排序

    - multimap是一个键值对的集合，按照键进行排序

每个关联容器都可以在声明时指定一个比较函数。

让我们看一下std::set的定义：

template<

    class Key,

    class Compare = std::less,

    class Allocator = std::allocator

> class set;

关联式容器的默认比较函数是std::less。

这个比较函数被用来对键进行排序。

如果你喜欢不同的排序或分配方案，你应该在声明时重写这些函数。

1.4 无序关联容器 Unordered associative containers 

无序关联容器提供了可以使用散列(hash)访问的无排序数据结构。

访问时间在最坏的情况下是O(n)，但是对于大多数 *** 作来说，比线性时间快得多。

对于所有的STL UnorderedAssociativeContainer类型，一个散列键(hashed key)被用来访问数据。

与AssociativeContainer类似，标准库的类型按照键值是否唯一分类两类：

 - 键是唯一的

     - unordered set是一个键的集合，通过键进行散列处理

     - unordered_map是一个键值对的集合，通过键进行散列处理。

 - 允许多条记录(entries)使用同一个键

     - unordered_multiset是一个键的集合，通过键进行散列处理。

     - unordered_multimap是一个键值对的集合，通过键进行散列处理。

与其他容器类型一样，UnorderedAssociativeContainer类型可以重写细节。

我们来看看std::unordered_set：

template<

    class Key,

    class Hash = std::hash,

    class KeyEqual = std::equal_to,

    class Allocator = std::allocator

> class unordered_set;

你可以重新指定散列函数、键比较函数和分配器。

我不关心改进STL的散列功能，所以我通常不考虑这些细节。

然而，如果你想覆盖任何一个默认的函数，你必须在声明时完成。

2, 使用标准容器的理由

当我要建立一个新软件系统时，标准容器消除了许多需要编写的样板(boilerplate)代码。

它们简化了开发，并且应该被用来代替自定义的实现，原因很简单:

1, STL容器的实现是正确的，我不需要花时间去调试容器。

2, STL容器速度快，而且可能比我自己实现的任何东西都更有效。

3, STL容器有共同的接口，这使得利用不同的容器变得非常简单，不需要查找成员函数的定义。

4, STL容器有很好的文档，很容易被其他开发者理解，提高了我们项目的可理解性和可维护性。

通过利用STL容器，我可以成为一个更有效率的开发者。

我对我的代码的可靠性更有信心，而且我可以相信其他开发者在未来会更容易维护我的代码。

3, 标准容器线程安全

我想与你分享一些关于容器线程安全的相关要点，因为许多嵌入式系统可能需要跨线程共享对象。

以下是一般线程安全规则：

 - 所有的容器函数都可以在同一容器类型的不同对象上安全地并发调用（例如，在两个不同的线程上使用两个不同的std::vector实例是安全的

 - 所有的常量成员函数可以被不同的线程同时调用

 - 如果没有线程在进行异步写入，容器可以安全地从多个线程中读取

 - 除了std::vector的元素外，同一容器中的不同元素可以被并发修改。

(因为vector是按bit存储的)

 - 如果一个对象被一个线程写入并被其他线程读取，该对象必须被保护起来

 - 一般来说，迭代器从容器中进行读取 *** 作，但不修改它，所以它们是线程安全的。

需要记住的最重要的细节是：如果你在多个线程中修改容器，你将需要保护该容器以防止并发访问。

参考：

An Overview of C++ STL Containers - Embedded Artistry