容器

大多数计算任务都会涉及到创建值的集合然后对这些集合进行操作. 一个简单的例子就是读取字符存入string当中,然后打印这个string. 如果一个类的主要目的是保存对象, 我们通常称之为容器. 对给定的任务提供合适的容器即其上有用的基本操作,是构建任何程序的重要步骤.

容器用于表示由同类型元素构成的、长度可变的元素序列。

容器是由类模板来实现的，模板的参数是容器中元素的类型。

STL中包含了很多种容器，虽然这些容器提供了一些相同的操作，但由于它们采用了不同的内部实现方法，因此，不同的容器往往适合于不同的应用场合。

1. 顺序序列 顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

2. 动态数组 支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。提供了在序列末尾相对快速地添加/删除元素的操作。

3. 能够感知内存分配器的（Allocator-aware） 容器使用一个内存分配器对象来动态地处理它的存储需求。

4. 序列式容器

   • 向量(vector) 后端可高效增加元素的顺序表。
   • 数组(array)C++11，定长的顺序表，C 风格数组的简单包装。
   • 双端队列(deque) 双端都可高效增加元素的顺序表。
   • 列表(list) 可以沿双向遍历的链表。
   • 单向列表(forward_list) 只能沿一个方向遍历的链表。

5. 关联式容器

   • 集合(set) 用以有序地存储 互异 元素的容器。其实现是由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种比较元素大小的谓词进行排列。
   • 多重集合(multiset) 用以有序地存储元素的容器。允许存在相等的元素。
   • 映射(map) 由 {键，值} 对组成的集合，以某种比较键大小关系的谓词进行排列。
   • 多重映射(multimap) 由 {键，值} 对组成的多重集合，亦即允许键有相等情况的映射。

6. 无序（关联式）容器

   • 无序（多重）集合(unordered_set/unordered_multiset)C++11，与 set/multiset 的区别在于元素无序，只关心「元素是否存在」，使用哈希实现。
   • 无序（多重）映射(unordered_map/unordered_multimap)C++11，与 map/multimap 的区别在于键 (key) 无序，只关心 "键与值的对应关系"，使用哈希实现。

7. 容器适配器

   • stack
   • queue
   • 优先队列 std::priority_queue 是一种 堆，一般为 二叉堆。

容器适配器

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。比如stack<T>容器适配器

容器适配器其实并不是容器。它们不具有容器的某些特点（如：有迭代器、有 clear() 函数……）。

适配器是使一种事物的行为类似于另外一种事物行为的一种机制，适配器对容器进行包装，使其表现出另外一种行为。

栈(stack) 后进先出 (LIFO) 的容器，默认是对双端队列（deque）的包装。 队列(queue) 先进先出 (FIFO) 的容器，默认是对双端队列（deque）的包装。 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列，默认是对向量（vector）的包装。

概述

我们知道，unordered_set和unordered_map与set和map是一样的，前者不是真正的键值对，它的value值和key值相同；后者是真正的键值对。STL非常注重代码的复用，它们在底层使用了同一棵红黑树模板实现，这也是此文要用同一个哈希表实现unordered_set和unordered_map的原因。如果各自拥有一个哈希表，set和unordered_set只要一个key值即可。

unordered_set

template<class K>
class unordered_set
{
public:
    // ..
private:
    HashTable<K, K> _ht;
};

unordered_map

template<class K, class V>
class unordered_map
{
public:
    //...
private:
    HashTable<K, pair<K, V>> _ht;
};

标准库容器的部分操作

除非有非常充分的理由, 否则我们应该按标准库容器的风格来设计容器. 特别是, 通过容器实现为句柄并为其实现恰当的基本操作来令它是资源安全的.

标准库容器都知道自己的元素数目. 我们可以调用size()来获取.

for(size_t i = 0; i < c.size(); ++i) //size_t 是标准库size()返回类型的名字
    c[i] = 0;

但是标准库算法并不是使用从0到size()的下标来遍历容器, 二是依赖于序列sequence的概念,一个序列是用一对迭代器iterator框定的.

for(auto p = c.begin(); p!= c.end(); ++p) *p = 0;

这里c.begin()是一个指向c的首元素是的迭代器. 而c.end()指向尾元素. 类似于指针,迭代器使用++操作移动到下一元素, 以及用*访问指向元素的值. 这种迭代器模型, 具有非常高的通用性和效率,用来将序列传递给标准库算法.例如

sort(v.begin(),v.end())

另一种隐式使用元素数目的算法是范围for循环:

for(auto&x :v){
    x = 0;
};

这段代码隐式的使用了c.begin()和c.end(),它大致等价于显式使用迭代器循环.

• 容器类模板提供了一些成员函数来实现容器的基本操作，其中包括：
• 往容器中增加元素
• 从容器中删除元素
• 获取容器中指定位置的元素
• 在容器中查找元素
• 获取容器首/尾元素的迭代器

这些成员函数往往具有通用性（大部分容器类模板都包含它们）。