浅谈杂交数据结构之分块 deque 原理及实现

FlowerAccepted · 2025-08-27 11:36:06 · 科技·工程

前言

@_KagamineRin : 会慢得跟屎一样，最关键的是我要封装 || @AKPC : 用数组手写双端队列 || @_KagamineRin : vector 在首尾添加很慢，deque 随机访问很慢，那能不能把这两个 STL 结合起来？？

其实可以的，鸽们，可以的！我有个好办法！

可以整体用重载 [] 的 std::list 维护约 \sqrt{n} 个块。块内用数组维护约 \sqrt{n} 个元素。

我所说的这个数据结构，平均可以做到 \mathcal{O}(1) 首尾插入、删除操作，\mathcal{O}(\sqrt{n}) 随机地址访问！空间复杂度也不高，只比 \mathcal{O}(n) 大出最多两个块长（\sqrt{n}）。

但是若当前块长 \sqrt{n}，则再插入 3n 个元素后就需要将分块 deque 拍了重建不然性能查询性能大大影响。重建和初始化复杂度均为 \mathcal{O}(n)。而从空一个元素一个元素插入最多重建 \log_4n 次，所以整体复杂度还是很优秀的。

这里用定长数组（为了方便，还是 std::vector 但是 reserve 过的）

虽然 std::deque 也使用了类似的思路但是本质并不相同，各有千秋。这边内存是 std::deque 的 \frac{1}{16}。

但是这边思路确实我独立想到的啊！wssb？

“寂”术细节

小前言

设 BN 个块，块长 BL，计算块长时分块 deque 大小 n，实际大小 len。

下标

首先，因为块 0 可能会出现前面空位，所以使用一个 pre 记录空位数量。

为了兼容一些特殊用途，这个杂交数据结构是 \texttt{0-base} 的，因为本蒟蒻太菜所以无法一发确定，所以经过大量调试发现原下标 i 在本数据结构中处在第 \lfloor\frac{i + pre}{BL}\rfloor 个块下标为 i + pre \mod BL 的位置。

因为有些用，所以把上述两式封装函数。反正可以开强制内联。

于是就可以重载 [] 运算符咯！

建立空分块 deque

将 n 和 len 均设为初始长度，设置块长 BL 为 \lfloor\sqrt{n}\rfloor + 1，块数 BN 为 \lceil\frac{n}{BL}\rceil。往链表里面塞 BN 个长度 BL 的空 vector。

从 std::vector 导入

建立长度为 n 的分块 deque，然后一个一个替换为目标数据即可。

精力有限，后面的不想写了，请大家看代码理解。

原型代码

轻量版实现，功能很少，没有边界判断，谨防溢出，没有迭代器。适合较纯粹场景。

注意到本项目数据越大插入修改的优势就越大，但是替代大量单点查询没得准的。（n 根 n 还是有点大）

也就是一个小糖思路，主要是优化了 deque 的十六倍空间。 :::info[点击打开]

#ifndef blkarr_h
#define blkarr_h
#include <vector>
#include <cmath>
#include <list>
using namespace std;
#define ila inline __attribute__((always_inline))

template<typename Tp>
class __list : public std::list<Tp> {
public:
    using list<Tp>::list;
    ila Tp& operator[](size_t index) {
        auto it = this->begin();
        advance(it, index);
        return *it;
    }
};

template <typename Tp>
struct Blkarr {
    int BL, BN, len, n, pre;
    long long mln;
    __list<vector<Tp>> a;
    ila int __getb(int i) const {
        return (i + pre) / BL;
    }
    ila int __getidx(int i) const {
        return (i + pre) % BL;
    }
    ila Tp& operator [](int i) {
        return a[__getb(i)][__getidx(i)];
    }
    ila const Tp& operator [](int i) const {
        return a[__getb(i)][__getidx(i)];
    }
    ila void push_back(Tp x) {
        if (__getb(len) == BN) {
            a.push_back(vector<Tp>(BL));
            BN ++;
            len ++;
            a.back()[0] = x;
            if (len >= mln) {
                rebuild();
            }
        } else {
            a.back()[__getidx(len)] = x;
            len ++;
        }
    }
    ila void push_front(Tp x) {
        if (!pre) {
            a.push_front(vector<Tp>(BL));
            pre = BL - 1;
            a.front()[pre] = x;
            BN ++;
            len ++;
            if (len >= mln) {
                rebuild();
            }
        } else {
            pre --;
            a.front()[pre] = x;
            len ++;
        }
    }
    ila void pop_back() {
        if (!__getidx(len)) {
            a.pop_back();
            BN --;
            len --;
            if (len <= BL) {
                rebuild();
            }
        } else {
            len --;
        }
    }
    ila void pop_front() {
        if (pre + 1 == BL) {
            a.pop_front();
            BN --;
            len --;
            pre = 0;
            if (len <= BL) {
                rebuild();
            }
        } else {
            pre ++;
            len --;
        }
    }
    ila void reclear(int l) {
        a.clear();
        n = len = l;
        BL = sqrt(n) + 1;
        BN = ceil(1.0 * len / BL);
        mln = n << (int)(sqrt(BL));
        pre = 0;
        for (int i = 0; i < BN; i ++) {
            a.push_back(vector<Tp>(BL));
        }
    }
    ila void operator = (vector<Tp> v) {
        reclear((int)v.size());
        auto cb = a.begin();
        int cbi = 0, cbs = 0, cbe = BL - pre - 1;
        for (int i = 0; i < len; i++) {
            if (i > cbe) {
                cb ++;
                cbi ++;
                cbs = cbe + 1;
                cbe = cbs + BL - 1;
            }
            int pib = i - cbs;
            (*cb)[pib] = v[i];
        }
    }
    ila void rebuild() {
        vector<Tp> v;
        v.resize(len);
        auto cb = a.begin();
        int cbi = 0, cbs = 0, cbe = BL - pre - 1;
        for (int i = 0; i < len; i++) {
            if (i > cbe) {
                cb ++;
                cbi ++;
                cbs = cbe + 1;
                cbe = cbs + BL - 1;
            }
            int pib = i - cbs;
            v[i] = (*cb)[pib];
        }
        *this = v;
    }
    ila Blkarr() {
        BL = 1;
        BN = len = n = pre = 0;
    }
    ila Blkarr(int l) {
        reclear(l);
    }
    ila Blkarr(const vector<Tp>& v) {
        *this = v;
    }
};
#undef ila
#endif

:::