物联网综合应用讲义（研究生）-03 嵌入式软件设计专题之数据结构

未分类

4 数据结构基础

• 经典名言“算法 + 数据结构 = 程序。”
• 所谓的数据结构，就是数据在计算机里的存储和组织形式，比如堆、数组、链表、二叉树、B+ 树、哈希表，等等。

在计算机的发展历史上，众多“大牛”孜孜不倦地发明创造了这么多的数据结构，为什么呢？因为没有一种数据结构是万能的、可以应用于任何场景。毕竟，不同的数据结构存储数据的形式不一样，效率也就不一样。有的是连续存放，有的是分散存放，有的存储效率高，有的查找效率高，我们必须要依据具体的应用场合来进行取舍。

4.1 数组（Array）

4.1.1 几个基本概念：数组、线性表、非线性表

• 数组（Array）
  是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

• 线性表和非线性表

  • 线性表（Linear List）
    顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
    除了数组，链表、队列、栈等也是线性表结构。
    

  • 非线性表
    比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
    

4.1.2 数组元素的操作：随机访问和插入删除

• 数组的特点是占用连续的内存空间和存储相同类型的数据。
• “杀手锏”的特性：“随机访问”。
  用数组下标直接访问（这也是数组从0开始编号的原因）
  
• 但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
• 插入操作
  
  • 如果数组中的数据是有序的，我们在某个位置插入一个新的元素时如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。
  • 如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数据插入到第k个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。
    
• 删除操作
  跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
  

4.1.3 警惕数组元素的越界访问问题！

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

因为，数组大小为 3，a[0]，a[1]，a[2]，而我们的代码因为书写错误，导致 for 循环的结束条件错写为了 i<=3 而非 i<3，所以当 i=3 时，数组 a[3]访问越界。

在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据我们前面讲的数组寻址公式，a[3]也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么a[3]=0就相当于i=0，所以就会导致代码无限循环。

4.1.4 容器和数组

容器能否完全替代数组？

4.2 链表（Linked list）

• 数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。
• 而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。
  

4.2.1 单链表

• 链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。
  
• 第一个结点叫作头结点，把最后一个结点叫作尾结点。
• 头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。
• 尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

• 与数组一样，链表也支持数据的查找、插入和删除操作。
  

  • 针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。

  • 链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

4.2.2 循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。

4.2.3 双向链表

• 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
  
• 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

4.2.4 双向循环链表

4.2.5 链表的代码实现

#include <stdio.h>
#include <stdbool.h>
struct single_list {
    struct single_list *next;
    int val;
};
struct single_list_head {
    struct single_list *head;
};
bool is_empty(struct single_list_head *head)
{
    return head->head == NULL;
}
void dump(struct single_list_head *head)
{
    struct single_list *tmp = head->head;
    int idx = 0;
    while (tmp) {
        printf("[%02d]: %08d\n", idx++, tmp->val);
        tmp = tmp->next;
    }
}
void insert(struct single_list **prev, struct single_list *elem)
{
    if (!prev)
        return;
    elem->next = *prev;
    *prev = elem;
}
void insert_head(struct single_list_head *head, struct single_list *elem)
{
    insert(&head->head, elem);
}
struct single_list* del(struct single_list **prev)
{
    struct single_list *tmp;
    if (!prev)
        return NULL;
    if (*prev == NULL)
        return NULL;
    tmp = *prev;
    *prev = (*prev)->next;
    tmp->next = NULL;
    return tmp;
};
struct single_list* delete_head(struct single_list_head* head)
{
    return del(&head->head);
};
struct single_list** search(struct single_list_head* head, int target)
{
    struct single_list **prev, *tmp;
    for (prev = &head->head, tmp = *prev;
         tmp && (tmp->val < target);
         prev = &tmp->next, tmp = *prev)
        ;
    return prev;
};
void reverse(struct single_list_head* head)
{
    struct single_list_head tmp = {NULL};
    struct single_list *elem;
    while (!is_empty(head)) {
        elem = delete_head(head);
        insert_head(&tmp, elem);
    }
    head->head = tmp.head;
}
bool is_cyclic(struct single_list_head* head)
{
    struct single_list *s1, *s2;
    s1 = s2 = head->head;
    while(s1 && s2) {
        s1 = s1->next;
        s2 = s2->next ? s2->next->next:s2->next;
        if (s1 == s2)
            return true;
    }
    return false;
}
struct single_list* middle(struct single_list_head* head)
{
    struct single_list *s1, *s2;
    struct single_list pseudo_head;
    pseudo_head.next = head->head;
    s1 = s2 = &pseudo_head;
    while (true) {
        if (!s2 || !s2->next)
            return s1;
        s1 = s1->next;
        s2 = s2->next->next;
    }
    return NULL;
};
int main()
{
    struct single_list_head head = {NULL};
    struct single_list lists[10];
    struct single_list **prev;
    int idx;
    for (idx = 0; idx < 10; idx++) {
        lists[idx].val = idx;
        lists[idx].next = NULL;
    }
    insert_head(&head, &lists[6]);
    insert_head(&head, &lists[5]);
    insert_head(&head, &lists[4]);
    insert_head(&head, &lists[1]);
    insert_head(&head, &lists[0]);
    printf("=== insert 0, 1, 4, 5, 6\n");
    dump(&head);
    prev = search(&head, 2);
    insert(prev, &lists[2]);
    printf("=== insert 2\n");
    dump(&head);
    printf("middle elem is %d\n", middle(&head)->val);
    prev = search(&head, 2);
    if ((*prev) && ((*prev)->val == 2))
        printf("The list contains 2\n");
    else
        printf("The list not contains 2\n");
    del(prev);
    prev = search(&head, 2);
    printf("After remove 2\n");
    if ((*prev) && ((*prev)->val == 2))
        printf("The list contains 2\n");
    else
        printf("The list not contains 2\n");
    dump(&head);
    printf("After reverse \n");
    reverse(&head);
    dump(&head);
    printf("middle elem is %d\n", middle(&head)->val);
    lists[0].next = &lists[6];
    printf("list is%s cyclic\n", is_cyclic(&head)?"":" not");
    return 0;
}

4.3 栈(stack)

4.3.1 栈的基本概念

• 关于“栈”，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。
  
• 从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
• 栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小
  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }
  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

4.3.2 栈的应用场景

• 函数调用

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}
int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

• 表达式求值
  实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
  

• 栈在括号匹配中的应用

我们假设表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。
那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？这里也可以用栈来解决。我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

4.4 队列（queue）

当需要申请资源的时候，可能没有空闲资源了，这时候就需要排队，这就是队列的应用场景。

4.4.1 如何理解队列？

队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。

我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。
队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

所以，队列跟栈一样，也是一种操作受限的线性表数据结构。
队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列。

4.4.2 顺序队列和链式队列

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;
  // 申请一个大小为capacity的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }
  // 入队
  public boolean enqueue(String item) {
    // 如果tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }
  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。你可以结合下面这幅图来理解。当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。

当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。

随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这个问题该如何解决呢？

接下来，我们再来看下基于链表的队列实现方法。基于链表的实现，我们同样需要两个指针：head 指针和 tail 指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->next= new_node, tail = tail->next；出队时，head = head->next。

4.4.3 循环队列

我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队列的解决思路。循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。

图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：

通过这样的方法，我们成功避免了数据搬移操作。
看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代，最关键的是，确定好队空和队满的判定条件。在用数组实现的非循环队列中，队满的判断条件是 tail == n，队空的判断条件是 head == tail。
那针对循环队列，如何判断队空和队满呢？

• 队列为空的判断条件仍然是 head == tail。
• 队列满的判断条件(tail+1)%n=head
  

就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head表示队头下标，tail表示队尾下标
  private int head = 0;
  private int tail = 0;
  // 申请一个大小为capacity的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }
  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }
  // 出队
  public String dequeue() {
    // 如果head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

4.4.4 阻塞队列和并发队列

• 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
  
• 生产者-消费者模型
  这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。
  
• 并发队列
  前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？线程安全的队列我们叫作并发队列。
  最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

4.4.5 小结

• 对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
• 队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。循环队列是我们这节的重点。要想写出没有 bug 的循环队列实现代码，关键要确定好队空和队满的判定条件。
• 阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。

4.5 容器

在 C++ 里，容器就是这个公式里面的“数据结构”。
容器，其实就是 C++ 对数据结构的抽象和封装。

4.5.1 顺序容器

• 顺序容器就是数据结构里的线性表，一共有 5 种：array、vector、deque、list、forward_list。
  按照存储结构，这 5 种容器又可以再细分成两组。
  
  • 连续存储的数组：array、vector 和 deque。
  • 指针结构的链表：list 和 forward_list。
  • array 和 vector 直接对应 C 的内置数组，内存布局与 C 完全兼容，所以是开销最低、速度最快的容器。它们两个的区别在于容量能否动态增长。array是静态数组，大小在初始化的时候就固定了，不能再容纳更多的元素。而 vector 是动态数组，虽然初始化的时候设定了大小，但可以在后面随需增长，容纳任意数量的元素。

array<int, 2> arr;                // 初始一个array，长度是2
assert(arr.size() == 2);        // 静态数组的长度总是2
vector<int> v(2);              // 初始一个vector，长度是2
for(int i = 0; i < 10; i++) {
    v.emplace_back(i);          // 追加多个元素
}
assert(v.size() == 12);          // 长度动态增长到12

deque 也是一种可以动态增长的数组，它和 vector
的区别是，它可以在两端高效地插入删除元素，这也是它的名字 double-end queue 的来历，而 vector 则只能用 push_back 在末端追加元素。

deque<int> d;                  // 初始化一个deque，长度是0
d.emplace_back(9);              // 末端添加一个元素
d.emplace_front(1);              // 前端添加一个元素
assert(d.size() == 2);          // 长度动态增长到2

• vector 和 deque 里的元素因为是连续存储的，所以在中间的插入删除效率就很低，-
• 而 list 和 forward_list 是链表结构，插入删除操作只需要调整指针，所以在任意位置的操作都很高效。
• 链表的缺点是查找效率低，只能沿着指针顺序访问，这方面不如 vector 随机访问的效率高。
• list 是双向链表，可以向前或者向后遍历，而 forward_list，顾名思义，是单向链表，只能向前遍历，查找效率就更低了。链表结构比起数组结构还有一个缺点，就是存储成本略高，因为必须要为每个元素附加一个或者两个的指针，指向链表的前后节点。
• vector/deque 和 list/forward_list 都可以动态增长来容纳更多的元素，但它们的内部扩容机制却是不一样的。当 vector 的容量到达上限的时候（capacity），它会再分配一块两倍大小的新内存，然后把旧元素拷贝或者移动过去。这个操作的成本是非常大的，所以，你在使用 vector 的时候最好能够“预估”容量，使用 reserve 提前分配足够的空间，减少动态扩容的拷贝代价。vector 的做法太“激进”，而 deque、list 的的扩容策略就“保守”多了，只会按照固定的“步长”（例如 N 个字节、一个节点）去增加容量。但在短时间内插入大量数据的时候就会频繁分配内存，效果反而不如 vector 一次分配来得好。
• 说完了这 5 个容器的优缺点，你该怎么选择呢？如果没有什么特殊需求，首选的容器就是 array 和 vector，它们的速度最快、开销最低，数组的形式也令它们最容易使用，搭配算法也可以实现快速的排序和查找。剩下的 deque、list 和 forward_list 则适合对插入删除性能比较敏感的场合，如果还很在意空间开销，那就只能选择非链表的 deque 了。
  

4.5.2 有序容器

• 顺序容器的特点是，元素的次序是由它插入的次序而决定的，访问元素也就按照最初插入的顺序。
• 而有序容器则不同，它的元素在插入容器后就被按照某种规则自动排序，所以是“有序”的。
• C++ 的有序容器使用的是树结构，通常是红黑树——有着最好查找性能的二叉树。
• 标准库里一共有四种有序容器：set/multiset 和 map/multimap。
• set 是集合，map 是关联数组（在其他语言里也叫“字典”）。有 multi 前缀的容器表示可以容纳重复的key，内部结构与无前缀的相同，所以也可以认为只有两种有序容器。
  因为有序容器的数量很少，所以使用的关键就是要理解它的“有序”概念，也就是说，容器是如何判断两个元素的“先后次序”，知道了这一点，才能正确地排序。这就导致了有序容器与顺序容器的另一个根本区别，在定义容器的时候必须要指定 key 的比较函数。只不过这个函数通常是默认的 less，表示小于关系，不用特意写出来：

template<
    class T                          // 模板参数只有一个元素类型
> class vector;                      // vector
template<
    class Key,                      // 模板参数是key类型，即元素类型
    class Compare = std::less<Key>  // 比较函数
> class set;                        // 集合
template<
    class Key,                      // 第一个模板参数是key类型
    class T,                        // 第二个模板参数是元素类型
    class Compare = std::less<Key>  // 比较函数
> class map;                        // 关联数组

C++ 里的 int、string 等基本类型都支持比较排序，放进有序容器里毫无问题。但很多自定义类型没有默认的比较函数，要作为容器的 key 就有点麻烦。虽然这种情况不多见，但有的时候还真是个“刚性需求”。

除了比较函数这点，有序容器其实没有什么太多好说的，因为就这两个，选择起来很简单：集合关系就用 set，关联数组就用 map。

因为有序容器在插入的时候会自动排序，所以就有隐含的插入排序成本，当数据量很大的时候，内部的位置查找、树旋转成本可能会比较高。还有，如果你需要实时插入排序，那么选择 set/map 是没问题的。如果是非实时，那么最好还是用 vector，全部数据插入完成后再一次性排序，效果肯定会更好。

4.5.3 无序容器

无序容器也有四种，名字里也有 set 和 map，只是加上了 unordered（无序）前缀，分别是 unordered_set/unordered_multiset、unordered_map/unordered_multimap。

无序容器同样也是集合和关联数组，用法上与有序容器几乎是一样的，区别在于内部数据结构：它不是红黑树，而是散列表（也叫哈希表，hash table）。

因为它采用散列表存储数据，元素的位置取决于计算的散列值，没有规律可言，所以就是“无序”的，你也可以把它理解为“乱序”容器。下面的代码简单示范了无序容器的操作，虽然接口与有序容器一样，但输出元素的顺序是不确定的乱序：

using map_type =                    // 类型别名
    unordered_map<int, string>;      // 使用无序关联数组
map_type dict;                      // 定义一个无序关联数组
dict[1] = "one";                      // 添加三个元素
dict.emplace(2, "two");
dict[10] = "ten";
for(auto& x : dict) {                // 遍历输出
    cout << x.first << "=>"           // 顺序不确定
         << x.second << ",";          // 既不是插入顺序，也不是大小序
} 

无序容器虽然不要求顺序，但是对 key 的要求反而比有序容器更“苛刻”一些，拿 unordered_map 的声明来看一下：

template<
    class Key,                          // 第一个模板参数是key类型
    class T,                            // 第二个模板参数是元素类型
    class Hash = std::hash<Key>,        // 计算散列值的函数对象
    class KeyEqual = std::equal_to<Key> // 相等比较函数
> class unordered_map; 

它要求 key 具备两个条件，一是可以计算 hash 值，二是能够执行相等比较操作。第一个是因为散列表的要求，只有计算 hash 值才能放入散列表，第二个则是因为 hash 值可能会冲突，所以当 hash 值相同时，就要比较真正的 key 值。

有序容器和无序容器的接口基本一样，这两者该如何选择呢？其实看数据结构就清楚了，如果只想要单纯的集合、字典，没有排序需求，就应该用无序容器，没有比较排序的成本，它的速度就会非常快。

4.6.4 容器小结

• 标准容器可以分为三大类，即顺序容器、有序容器和无序容器；
• 所有容器中最优先选择的应该是 array 和 vector，它们的速度最快，开销最低；
• list 是链表结构，插入删除的效率高，但查找效率低；
• 有序容器是红黑树结构，对 key 自动排序，查找效率高，但有插入成本；
• 无序容器是散列表结构，由 hash 值计算存储位置，查找和插入的成本都很低；
• 有序容器和无序容器都属于关联容器，元素有 key 的概念，操作元素实际上是在操作 key，所以要定义对 key 的比较函数或者散列函数。