3.3 序列式容器-deque、stack、queue、heap、priority_queue

deque

3.1定义

std::deque（双端队列）是C++标准模板库（STL）中的一种容器，表示双端队列数据结构。它提供了在两端高效地进行插入和删除操作的能力。与vector的连续线性空间类似，但有所不同，deque动态地以分段连续空间组合而成的，随时可以增加一段新的空间并链接起来。因此deque的迭代器并不是普通的指针；

之前提到vector的动态内存增长需要涉及到更大内存的分配；内存数据的复制；原内存空间的释放。deque避开了vector中的反复内存搬移，但是数据结构的设计和迭代器架构却异常复杂。deque的代码实现量远比vector和list多得多。

3.2deque中控器

deque微观上看起来是连续空间，但宏观上看，deque内部并没有完全在一块连续空间，而是由一段一段的连续空间构成。而这一段一段的连续空间的管理就需要一个中控器。deque采用一块连续的“map”映射区（并不是STL中的map）来管理这些空间。其中每个元素（即一个节点）都是指针，指向一块较大的连续的线性空间，这一块较大的连续线性空间才是deque储存空间的主体。

map其实是一个二级指针，T**，它是一个指针，所指之物又是一个指针，指向一块型别为T的空间。

3.3迭代器

deque迭代器属于最高级的随机访问迭代器，但是相对于vector的普通指针迭代器，deque的迭代器实现相当复杂。

deque迭代器结构：

struct _deque_iterator
{
    typedef __deque_iterator<T,T&,T*,BufSize> iterator;
    static size_t buffer_size(){return __deque_buf_size(BufSize,sizeof(T));}
    //保持与容器的联结
    //此迭代器所指缓冲区中的当前行(current)元素
    T* cur;
    //缓冲区的头部元素
    T* first;
    //缓冲区的尾部元素
    T* last;
    //缓冲区管理中心
    map_pointer node;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

deque迭代器的关键成员函数：

迭代器的++,—重载都要考虑临界的情况。

3.4数据结构

deque除了维护一个指向map的指针外，也维护两个迭代器，start和finish，分别指向第一个缓冲区的第一个元素和最后一个缓冲区的最后一个元素（的下一个位置）。此外还有map的大小，当map用完之后，还需要重新配置一块更大的map。

deque数据结构代码：

template <class T,class Alloc=alloc,size_t BufSiz=0>
class deque
{
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef size_t size_type;
    ...
protected:
    //元素的指针的指针
    typedef pointer* map_pointer;
    //第一个节点
    iterator start;
    //最后一个节点
    iterator finish;
    //指向是连续空间
    map_pointer map;
    //map内指针数量
    size_type map_size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

deque的map节点的分配会以最中间开始，保证前后两端指向可扩充的空间大小相同。

stack

stack基于LIFO（Last-In, First-Out）原则，允许在容器的末尾添加元素，并从末尾移除元素。stack其实是一个容器适配器，它是基于其他底层容器实现的。可以是 std::deque, std::list 或 std::vector。默认情况下，std::deque 被用作 std::stack 的底层容器。

stack没有迭代器，所有元素都是先进后出的规则。



可以看到用组合的形式，使用底层容器queue的功能。

queue

std::queue 是基于FIFO（First-In, First-Out）原则的容器，允许在容器的末尾添加元素，并在容器的前端移除元素。，queue是一个适配器容器，基于底层的容器实现。并且默认情况下，std::deque 被用作 std::queue 的底层容器。std::queue 提供了队列的基本操作，例如 push、pop 和 front，分别用于在队尾添加元素、移除队首元素和获取队首元素的值。

queue没有迭代器。

heap

heap又叫做堆，不属于STL的容器组件，只是优先队列中会用到。

可以了解一下堆的排序算法：

在这里插入图片描述

建堆的时间复杂度为：o(n)

时间复杂度 ： o(nlogn)

下标为i的节点的父节点下表：（i-1)/2

下标为i的节点的左孩子下表：i*2+1

下标为i的节点的右孩子下表：i*2+2

void sortSolution::maxHeap(vector<int>& arr, int i, int heapSize) {
    int l = i * 2 + 1;
    int r = l + 1;
    int largest = i;
    if(l < heapSize && arr[l] > arr[largest]) {
        largest = l;
    }
    if(r < heapSize && arr[r] > arr[largest]) {
        largest = r;
    }
    if(largest != i) {
        swap(arr[i], arr[largest]);
        maxHeap(arr, largest, heapSize);
    }
}
void sortSolution::buildMaxHeap(vector<int>& arr) {
    for(int i = arr.size() / 2 - 1; i >= 0; --i) {
        maxHeap(arr, i, arr.size()); 
    }
}
void sortSolution::heapSort(vector<int>& arr) {
    buildMaxHeap(arr);
    for(int i = arr.size() - 1; i > 0; --i) {
        swap(arr[0], arr[i]);
        maxHeap(arr, 0, i);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

priority_queue

priority_queue是一个具有权值观念的queue，它允许加入新元素、移除旧元素、审视元素值等功能。其内部的函数是按照权值进行排序的。也属于容器适配器。

默认情况下，std::priority_queue 是一个最大堆（Max Heap），即根节点的值大于或等于其子节点的值。