简易STL实现 | Deque的实现

一种 在内存中存储元素的数据结构，它支持 在两端添加和删除元素（使用循环数组实现）

1、deque的特性（分段deque实现）

1、双端操作： deque支持在前端和后端执行快速的插入和删除操作

2、随机访问： 与list不同，deque允许在常量时间内 对元素进行随机访问。这是因为 deque的内部结构采用分段数组，而不是链表
myDeque[2] 和 myDeque[4] 的访问时间是常量的，不受deque的大小的影响
这是因为std::deque 使用了分段数组的结构，每个分段都是一个固定大小的数组，因此可以直接计算索引的位置，而不需要遍历整个容器

将数据存储 在多个较小的数组（块）中，而不是 单个连续的大数组。这样做的好处是 可以更有效地扩展容量，避免频繁的内存重新分配

#include <iostream>
#include <stdexcept>
#include <vector>

template <typename T>
class Deque {
public:
    Deque() : capacity(1), size(0), frontIndex(0), backIndex(0) {
        blocks.push_back(new T[blockSize]); // 每次新分配小块数组都是固定大小（都是blockSize，就是多少个的问题）
    }

    ~Deque() {
        clear();
        for (auto block : blocks) {
            delete[] block;
        }
    }

    void push_back(const T& e) {
        if (size == capacity) {
            resize();
        }
        blocks[backIndex / blockSize][backIndex % blockSize] = e; // 核心思路
        backIndex = (backIndex + 1) % capacity;
        size++;
    }

    void push_front(const T& e) {
        if (size == capacity) {
            resize();
        }
        frontIndex = (frontIndex - 1 + capacity) % capacity; // 思路一致，在不需要分块的代码的基础上（见后面）加一个在哪个块的计算
        blocks[frontIndex / blockSize][frontIndex % blockSize] = e;
        size++;
    }

    void pop_back() {
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        size--;
        backIndex = (backIndex - 1 + capacity) % capacity;
    }

    void pop_front() {
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        size--;
        frontIndex = (frontIndex + 1) % capacity;
    }

    void clear() {
        while (size > 0) {
            pop_back();
        }
    }

    size_t getSize() const {
        return size;
    }

    T& operator[](size_t index) {
        if (index >= size) {
            throw std::out_of_range("index out of range");
        }
        size_t realIndex = (frontIndex + index) % capacity;
        return blocks[realIndex / blockSize][realIndex % blockSize];
    }

    void printElement() const {
        if (size == 0) {
            std::cout << "empty";
        } else {
            size_t cur = frontIndex;
            for (size_t i = 0; i < size; i++) {
                std::cout << blocks[cur / blockSize][cur % blockSize] << " ";
                cur = (cur + 1) % capacity;
            }
        }
        std::cout << std::endl;
    }

private:
    static const size_t blockSize = 64;  // 每个块的大小
    std::vector<T*> blocks;  // 存储块的指针
    size_t capacity;  // 总容量（所有块的总和）
    size_t size;  // 当前元素数量
    size_t frontIndex;  // 队首索引
    size_t backIndex;  // 队尾索引

    void resize() { // 核心思路
        size_t newCapacity = 2 * capacity;
        size_t newBlockCount = (newCapacity + blockSize - 1) / blockSize;
        blocks.resize(newBlockCount);
        for (size_t i = capacity / blockSize; i < newBlockCount; i++) {
            blocks[i] = new T[blockSize];
        }

        // 重新排列元素
        if (frontIndex > backIndex) {
            size_t shift = newCapacity - capacity;
            for (size_t i = 0; i < backIndex; i++) {
                blocks[(i + shift) / blockSize][(i + shift) % blockSize] = blocks[i / blockSize][i % blockSize];
            }
            backIndex += shift;
        }

        capacity = newCapacity;
    }
};

块数组的引入：
使用 std::vector<T*> blocks 来存储每个块的指针。每个块的大小由 blockSize 决定。每次新分配小块数组都是固定大小（都是blockSize，就是多少个的问题）

push_back 和 push_front：（pop跟不是块数组一致）
当插入新元素时，确定插入位置是否需要跨块，如果需要，则计算正确的块索引和块内的偏移量（思路一致，在不需要分块的代码的基础上（见后面）加一个在哪个块的计算）

resize：
当当前容量不足时，resize 函数会将容量扩展到原来的两倍，并重新分配块
如果 frontIndex 在 backIndex 后面（即队列在数组中是环形排列的），则需要将后半部分元素移至新位置

void resize() { // 核心思路
        size_t newCapacity = 2 * capacity;
        size_t newBlockCount = (newCapacity + blockSize - 1) / blockSize;
        blocks.resize(newBlockCount);
        for (size_t i = capacity / blockSize; i < newBlockCount; i++) {
            blocks[i] = new T[blockSize];
        }

        // 重新排列元素
        if (frontIndex > backIndex) {
            size_t shift = newCapacity - capacity;
            for (size_t i = 0; i < backIndex; i++) {
                blocks[(i + shift) / blockSize][(i + shift) % blockSize] = blocks[i / blockSize][i % blockSize];
            }
            backIndex += shift;
        }

        capacity = newCapacity;
    }

分段数组：Deque 内部的元素存储在多个小块数组（即“blocks”）中，而不是单一的大数组中。每个块的大小是固定的（由 blockSize 定义）。
动态扩展：当 Deque 需要存储更多元素时，resize() 函数会动态增加存储空间
size_t newCapacity = 2 * capacity;：动态扩展时，通常会将容量加倍以减少未来的扩展次数
size_t newBlockCount = (newCapacity + blockSize - 1) / blockSize;：计算扩展后的块数量 newBlockCount。每个块的大小是 blockSize，因此总块数为 newCapacity 除以 blockSize。(newCapacity + blockSize - 1) 用来确保向上取整，这样可以容纳所有的新元素
blocks.resize(newBlockCount);：blocks 是存储块指针的 std::vector，通过 resize 将 blocks 的大小调整为新的块数 newBlockCount

for (size_t i = capacity / blockSize; i < newBlockCount; i++) {
    blocks[i] = new T[blockSize];
}

为新增的块分配内存。循环遍历 blocks 中的新块区域，为每个新块分配大小为 blockSize 的数组

if (frontIndex > backIndex) {
    size_t shift = newCapacity - capacity;
    for (size_t i = 0; i < backIndex; i++) {
        blocks[(i + shift) / blockSize][(i + shift) % blockSize] = blocks[i / blockSize][i % blockSize];
    }
    backIndex += shift;
}

检测队列是否环绕：frontIndex > backIndex 表示当前的队列元素在数组中是环绕排列的（即头部索引在尾部索引后面）
计算偏移量 shift：新旧容量之间的差值 shift 是新元素需要移动的步数
元素重新排列：将当前 blocks 中 backIndex 前的元素依次复制到新的位置。新的位置是在旧的位置上加上 shift 偏移后的索引。通过这个操作，确保环绕的部分正确地移动到新的空间中（将环绕的部分（即 backIndex 之前的部分）移动到新的存储空间的后半部分，以使队列不再环绕），保持 Deque 的正确顺序
更新 backIndex：将 backIndex 也相应地向前移动 shift 个位置，以反映它在新扩展后的块数组中的位置

访问和打印：
operator[] 访问时，通过计算得到正确的块索引和块内偏移量
printElement 函数遍历元素，并以正确的顺序打印出来

3、动态扩展： deque的大小可以动态调整，无需 事先分配固定大小的内存。这使得 deque 适用于需要动态增长和缩小的情况

4、内存局部性： deque的内部结构利用了多个缓冲区，有助于提高内存局部性，从而在某些情况下提供更好的性能（指程序在执行过程中访问的内存地址 具有一定的规律性，即在时间和空间上相邻的内存地址被频繁访问）
与单一的大数组相比，deque 的分段数组结构 使得每个缓冲区的大小固定且较小。这样，即使需要扩展，也不会频繁地移动大量内存数据，只需操作当前使用的缓冲区即可，这降低了缓存未命中的可能性
分段数组结构 使得最近访问的缓冲区和其中的元素很可能会被缓存，从而在访问这些数据时 具有较高的缓存命中率，这在需要频繁操作队列的前后端时尤其明显

2、deque 工作原理

backIndex指向的位置是当前末尾元素的下一个位置, 也就是还没有有效的数据(如果容量满了, 其会指向frontIndex的位置)

3、实现 deque（不分段）

#include <iostream>
#include <stdexcept>
#include <string>
#include <sstream>

template <typename T>
class Deque {
public:
    Deque() : elements(nullptr), capacity(0), size(0), frontIndex(0), backIndex(0) {}

    ~Deque() {
        clear();
        delete[] elements;
    }

    void push_back(const T& e) {
        if (size == capacity) {
            resize();
        }
        elements[backIndex] = e;
        backIndex = (backIndex + 1) % capacity;
        size++;
    }

    void push_front(const T& e) {
        if (size == capacity) {
            resize();
        }
        size_t newFrontIndex = (frontIndex - 1 + capacity) % capacity; // 为了防止数组索引为负, 使其指向尾端
        frontIndex = newFrontIndex;
        elements[frontIndex] = e;
        size++;
    }

    void pop_back() { // 不需要负责内存的释放，内存的释放由析构函数解决
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        size--;
        backIndex = (backIndex - 1 + capacity) % capacity;
    }

    void pop_front() {
        if (size == 0) {
            throw std::out_of_range("Deque is empty");
        }
        size--;
        frontIndex = (frontIndex + 1) % capacity;
    }

    void clear() {
        while (size > 0) {
            pop_back(); // 可以复用
        }
    }

    size_t getSize() {
        return size;
    }

    T& operator[](int index) { // 参数必须是int，不然就有可能越界（size_t转换负值为未知正整数）
        if (index < 0 || index >= size) {
            throw std::out_of_range("index out of range");
        }
        return elements[(frontIndex + index) % capacity]; // 注意下标不是直接是index
    }

    void printElement() {
        if (size == 0) {
            std::cout << "empty";
        }
        size_t cur = frontIndex;
        for (size_t i = 0; i < size; i++) {
            std::cout << elements[cur] << " ";
            cur = (cur + 1) % capacity;
        }
        std::cout << std::endl;

    }
private:
    T* elements;
    size_t capacity;
    size_t size;
    size_t frontIndex;
    size_t backIndex;

    void resize() {
        size_t newCapacity = (capacity == 0) ? 1 : 2 * capacity;
        T* newElements = new T[newCapacity];
        size_t cur = frontIndex;
        for (size_t i = 0; i < size; i++) {
            newElements[i] = elements[cur];
            cur = (cur + 1) % capacity;
        }
        delete[] elements;
        elements = newElements;
        frontIndex = 0;
        backIndex = size;
        capacity = newCapacity;
    }


}; // 类定义后别忘了；

int main() {
    Deque<int> myDeque;
    int N;
    std::cin >> N;
    getchar();
    for (int i = 0; i < N; i++) {
        std::string line;
        std::getline(std::cin, line);
        std::istringstream iss(line);
        std::string command;
        iss >> command;
        if (command == "push_back") {
            int num;
            iss >> num;
            myDeque.push_back(num);
        }
        else if (command == "push_front") {
            int num;
            iss >> num;
            myDeque.push_front(num);
        }
        else if (command == "pop_back") { // pop要判断是否为空
            if (myDeque.getSize() == 0) {
                continue;
            }
            myDeque.pop_back();
        }
        else if (command == "pop_front") {
            if (myDeque.getSize() == 0) {
                continue;
            }
            myDeque.pop_front();
        }
        else if (command == "clear") {
            myDeque.clear();
        }
        else if (command == "size") {
            std::cout << myDeque.getSize() << std::endl;
        }
        else if (command == "get") {
            size_t pos;
            iss >> pos;
            std::cout << myDeque[pos] << std::endl;
        }
        else if (command == "print") {
            myDeque.printElement();
        }
    }

    return 0;
}

和 C++ STL标准库实现版本的区别：
1、标准库中的 std::deque（双端队列）通常是通过 多个连续存储区域（即一维数组）来实现的，而不是单一的连续数组, 这多个一维数组 连接起来形成了deque数组, 目前的实现采用的是循环数组, 缺点就是resize时要复制旧数组, 而官方的std::deque只需要再串联一个一维数组就可以了, 效率更高

2、内存管理： 在实际的 STL 中，内存管理通常会更加复杂和高效。STL 会使用分配器（allocator）来管理内存，而不是直接使用 new 和 delete。分配器允许用户提供自定义的内存管理策略

3、迭代器和算法支持： STL 提供了丰富的迭代器和算法支持，允许通用的方式操作容器
迭代器的支持
输入迭代器：只能进行读操作，且只能单向遍历

#include <iostream>
#include <iterator>
#include <numeric>

int main() {
    std::istream_iterator<int> input(std::cin), eof;
    int sum = std::accumulate(input, eof, 0);
    std::cout << "Sum: " << sum << std::endl;
    return 0;
}

输出迭代器：只能进行写操作，且只能单向遍历

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::ostream_iterator<int> output(std::cout, " ");
    std::copy(vec.begin(), vec.end(), output);
    std::cout << std::endl;
    return 0;
}

前向迭代器：可以读写操作，并且可以多次遍历

#include <iostream>
#include <algorithm>
#include <forward_list>

int main() {
    std::forward_list<int> flist = {1, 2, 3, 2, 1};
    std::replace(flist.begin(), flist.end(), 2, 10);
    for (int n : flist) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

双向迭代器：可以前后遍历，例如 list 容器的迭代器

#include <iostream>
#include <algorithm>
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    std::reverse(lst.begin(), lst.end());
    for (int n : lst) {
        std::cout << n << " ";
    }
    std::cout << std::endl;
    return 0;
}

随机访问迭代器：支持常数时间内的随机访问操作，例如 vector 和 deque 容器的迭代器

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 3, 9, 1, 7};
    std::sort(vec.begin(), vec.end());
    if (std::binary_search(vec.begin(), vec.end(), 3)) {
        std::cout << "Found!" << std::endl;
    }
    return 0;
}

算法的支持
排序算法：std::sort 可以对任何随机访问迭代器（如 vector、deque）容器进行排序
搜索算法：std::find 可以在线性时间内在任何容器中查找特定元素
修改算法：std::transform 可以对容器中的每个元素应用指定的函数并存储结果
复制算法：std::copy 可以将一个容器的内容复制到另一个容器中

4、性能优化： 实际的 STL 库通常会进行更多的性能优化，包括使用更复杂的数据结构、考虑缓存友好性等

5、标准兼容性： 实际的 STL 遵循 C++ 标准，确保在不同的平台和编译器上的一致行为。它还提供了许多其他功能，如分配器的自定义、迭代器标签（iterator tags）等

4、高频面试题

1、deque 和 vector 的主要区别是什么
内存分配：vector 使用单一连续的内存空间来存储元素，而 deque 使用多个分散的内存块。这意味着 deque 可以在两端进行高效的插入和删除操作，而 vector 只能在尾部高效地进行这些操作
插入效率：在 deque 的前端和后端插入或删除元素的操作效率很高，但在中间插入或删除元素效率较低，因为它需要移动多个内存块中的元素。而 vector 在尾部插入和删除元素高效（头部不行），但在前端或中间进行这些操作效率较低，因为可能需要移动大量元素
随机访问：vector 提供了更快的随机访问性能，因为它使用连续内存，而 deque 由于其分散的内存块，随机访问性能稍低
内存耗费：vector 在扩展时可能会有较大的内存重新分配成本，而 deque 因为是分块存储，所以通常不需要大量的内存重新分配

2、使用 deque 实现固定大小滑动窗口

#include <iostream>
#include <deque>

class SlidingWindow {
public:
    SlidingWindow(size_t windowSize) : maxSize(windowSize) {}

    void add(int value) {
        // 如果窗口已满，则删除最早的元素
        if (window.size() == maxSize) {
            window.pop_front();
        }
        // 添加新元素到窗口
        window.push_back(value);
    }

    double getAverage() const {
        if (window.empty()) return 0.0;
        
        double sum = 0;
        for (int value : window) {
            sum += value;
        }
        return sum / window.size();
    }

    void printWindow() const {
        for (int value : window) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }

private:
    std::deque<int> window;
    size_t maxSize;
};

3、在 deque 中使用 [] 操作符和 at() 方法有何区别
operator[] 提供对元素的无检查访问，这意味着如果使用超出范围的索引，它不会抛出异常，而是导致未定义行为
at() 方法提供边界检查的访问。如果指定的索引超出了 deque 的范围，at() 方法会抛出一个 std::out_of_range 异常。因此，at() 比 operator[] 更安全，但可能会略微降低性能
使用 at() 方法可以帮助调试中发现越界错误，而 operator[] 在确定不会越界时可以提供更好的性能

4、在 deque 的前端插入一个元素时，迭代器会发生什么

1. std::deque 的行为
   std::deque 是一个双端队列，允许在两端快速插入和删除元素。与 std::vector 不同，std::deque 是分段存储的，因此在内部的实现中有多个内存块
   1）前端插入：
   在 std::deque 的前端插入元素时，通常不会导致整个容器的重新分配。但如果前端没有足够的空间（即最前面的块已满），std::deque 可能会在前端分配一个新的块
   由于 std::deque 可能需要移动或重新分配内部的内存块，因此所有的迭代器、引用和指针可能会失效
   2）后端插入：
   在 std::deque 的尾部插入元素时，情况与前端插入类似。如果后端没有足够的空间，可能需要分配新的块，从而导致迭代器、引用和指针失效
2. std::vector 是一个动态数组，当在尾部插入元素时，其行为如下：
   1）尾部插入：
   如果 std::vector 的当前容量足够，那么插入新元素不会导致迭代器、引用和指针失效
   但是，如果插入新元素导致 std::vector 的容量不足，它会分配更大的内存块，并将现有的元素复制到新分配的内存中。这种情况下，所有指向旧元素的迭代器、引用和指针都会失效
   2）前端或中间插入：
   在 std::vector 的前端或中间插入元素时，即使没有触发容量重新分配，由于元素需要移动以为新元素腾出空间，指向被移动元素的迭代器、引用和指针也会失效

5、 解释 deque 的内部工作机制。它是如何实现 两端插入和删除操作的高效性的
std::deque 维护了一系列定长数组（称为块或缓冲区），并且有一个中央控制器（通常是指针数组）来管理这些块。每个块可以独立地增长和收缩，这意味着当在两端添加或删除元素时，只有相关联的块受到影响

在前端插入：如果第一个块有空间，则在该块的开始插入新元素。如果没有空间，deque 会分配一个新块 并将其链接到现有的块序列中
在后端插入：如果最后一个块有空间，则在该块的末尾插入新元素。如果没有空间，deque 会分配一个新块 并将其链接到现有的块序列中
在前端删除：移除第一个块的第一个元素。如果该块变空，则释放该块资源 并更新中央控制器
在后端删除：移除最后一个块的最后一个元素。如果该块变空，则释放该块资源 并更新中央控制器

6、deque 的构造函数

std::deque<int> dq; // 创建一个空的 deque

std::deque<int> dq(10, 5); // 10个元素，每个都是5

std::vector<int> vec{1, 2, 3, 4, 5};
std::deque<int> dq(vec.begin(), vec.end()); // 复制给定迭代器范围内的元素

std::deque<int> dq1(10, 5);
std::deque<int> dq2(dq1); // 拷贝构造函数

std::deque<int> dq1(10, 5);
std::deque<int> dq2(std::move(dq1)); // 移动构造函数

std::deque<int> dq{1, 2, 3, 4, 5}; // 使用一个初始化列表来创建

// 带有分配器的默认构造函数：创建一个空的 deque，但是使用自定义的分配器来分配内存
std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq(alloc);

std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq(10, 5, alloc); // 10个元素，每个都是5，使用自定义分配器

std::vector<int> vec{1, 2, 3, 4, 5};
std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq(vec.begin(), vec.end(), alloc);

std::deque<int> dq1(10, 5);
std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq2(dq1, alloc); // 拷贝dq1，使用自定义分配器

std::deque<int> dq1(10, 5);
std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq2(std::move(dq1), alloc); // 移动dq1，使用自定义分配器

std::allocator<int> alloc;
std::deque<int, std::allocator<int>> dq({1, 2, 3, 4, 5}, alloc);