基于双Vector的Deque实现运行时复杂度过高的优化求助

核心问题分析 #

你当前的实现性能瓶颈确实在vector头部的插入/删除操作：

• push_front用insert(frontVector.begin(), val)、pop_front用erase(frontVector.begin())，都是O(n)时间复杂度，因为vector需要移动所有后续元素
• balanceVectors里每次只转移单个元素，且用到backVector.erase(backVector.begin())和backVector.insert(backVector.begin(), ...)，同样是O(n)操作，频繁调用会导致整体性能急剧下降

优化思路：反转frontVector的存储逻辑 #

把frontVector设计成倒序存储Deque的前半部分：

• frontVector的尾部对应Deque的头部（即Deque的front是frontVector的back）
• frontVector的头部对应Deque的中间位置（靠近backVector的一端）

这样所有前端操作都可以复用vector的尾部操作（O(1)均摊），同时调整balance策略，批量转移元素而非单次转移，保证均摊常数时间复杂度。

完整优化代码实现 #

#include <vector>
#include <initializer_list>

template <typename T>
class MyDeque {
private:
    std::vector<T> frontVector; // 倒序存储前半部分：back()是Deque的front
    std::vector<T> backVector;  // 正序存储后半部分：front()是Deque的中间，back()是Deque的back

    void balanceVectors() {
        int totalSize = size();
        // 目标：frontVector的大小为totalSize/2，backVector为totalSize - totalSize/2
        int targetFrontSize = totalSize / 2;

        if (frontVector.size() > targetFrontSize) {
            // 从frontVector尾部（Deque前端）转移多余元素到backVector头部
            int moveCount = frontVector.size() - targetFrontSize;
            // 批量插入到backVector的开头：用insert的范围版本，避免多次单个插入
            backVector.insert(backVector.begin(), frontVector.end() - moveCount, frontVector.end());
            // 截断frontVector的尾部
            frontVector.resize(targetFrontSize);
        } else if (frontVector.size() < targetFrontSize) {
            // 从backVector头部转移不足的元素到frontVector尾部
            int moveCount = targetFrontSize - frontVector.size();
            // 批量插入到frontVector的尾部（Deque的前端方向）
            frontVector.insert(frontVector.end(), backVector.begin(), backVector.begin() + moveCount);
            // 截断backVector的头部
            backVector.erase(backVector.begin(), backVector.begin() + moveCount);
        }
    }

public:
    MyDeque() = default;

    MyDeque(int n) : frontVector(n/2), backVector(n - n/2) {}

    MyDeque(std::initializer_list<T> vals) {
        // 先全部放入backVector，再平衡
        backVector.assign(vals.begin(), vals.end());
        balanceVectors();
    }

    void push_back(T val) {
        backVector.push_back(val);
        balanceVectors();
    }

    void push_front(T val) {
        // 直接push到frontVector尾部，对应Deque前端，O(1)均摊
        frontVector.push_back(val);
        balanceVectors();
    }

    void pop_back() {
        if (!backVector.empty()) {
            backVector.pop_back();
        } else if (!frontVector.empty()) {
            // 所有元素都在frontVector，倒序存储，back是frontVector的第一个元素
            frontVector.erase(frontVector.begin());
        }
        balanceVectors();
    }

    void pop_front() {
        if (!frontVector.empty()) {
            // 直接pop frontVector尾部，对应Deque前端，O(1)均摊
            frontVector.pop_back();
        } else if (!backVector.empty()) {
            backVector.erase(backVector.begin());
        }
        balanceVectors();
    }

    T& back() {
        if (!backVector.empty()) {
            return backVector.back();
        }
        // 所有元素在frontVector，倒序，back是frontVector的第一个元素
        return frontVector.front();
    }

    const T& back() const {
        if (!backVector.empty()) {
            return backVector.back();
        }
        return frontVector.front();
    }

    T& front() {
        if (!frontVector.empty()) {
            // frontVector的尾部是Deque的头部
            return frontVector.back();
        }
        return backVector.front();
    }

    const T& front() const {
        if (!frontVector.empty()) {
            return frontVector.back();
        }
        return backVector.front();
    }

    bool empty() const {
        return frontVector.empty() && backVector.empty();
    }

    int size() const {
        return static_cast<int>(frontVector.size() + backVector.size());
    }

    T& operator[](int i) {
        if (i < static_cast<int>(frontVector.size())) {
            // frontVector是倒序，所以索引i对应frontVector的size()-1 -i位置
            return frontVector[frontVector.size() - 1 - i];
        } else {
            return backVector[i - frontVector.size()];
        }
    }

    const T& operator[](int i) const {
        if (i < static_cast<int>(frontVector.size())) {
            return frontVector[frontVector.size() - 1 - i];
        } else {
            return backVector[i - frontVector.size()];
        }
    }
};

template class MyDeque<int>;
template class MyDeque<double>;
template class MyDeque<char>;
template class MyDeque<std::string>;

优化点说明 #

1. frontVector存储逻辑反转：
   • push_front变为frontVector.push_back(val)，pop_front变为frontVector.pop_back()，都是O(1)均摊时间
2. balanceVectors批量转移：
   • 不再单次转移单个元素，而是计算需要转移的数量，用vector的范围插入/删除操作一次性完成，均摊下来每个元素只被转移一次，保证整体均摊O(1)时间
3. operator[]适配反转逻辑：
   • 访问frontVector中的元素时，需要通过frontVector.size() -1 -i计算实际索引，因为frontVector是倒序存储的

性能验证 #

所有核心操作（push_front、push_back、pop_front、pop_back、balance）均为均摊常数时间，符合Deque的性能要求，解决了原实现中频繁O(n)操作导致的耗时问题。

内容的提问来源于stack exchange，提问作者MohannedUsama