自定义Deque的pop_back与rebalance功能异常排查求助

我正在实现一个自定义Deque，编写了pop_back函数与rebalance功能。第三次执行pop_back后，我期望Deque内元素为a b c，以便能正常弹出c从而通过测试用例，但实际测试失败。我的rebalance功能在之前的测试用例中可正常运行，想请教这是rebalance问题还是pop_back问题？

测试日志 #

Front: a Back: e
c b a d 
Deque size after pop_back: 4
Front: a Back: d
c b a 
Deque size after pop_back: 3
Front: a Back: c
a c b 
Deque size after pop_back: 3
Front: a Back: b
a c 
Deque size after pop_back: 2
Front: a Back: c
main.cpp:167: Failure
Expected equality of these values:
  deque.back()
    Which is: 'c' (99, 0x63)
  'a'
    Which is: 'a' (97, 0x61)
a

测试用例 #

TEST(MyDequeTest, PopBackAndBackChar) {
  MyDeque<char> deque {'a', 'b', 'c', 'd', 'e'};
  EXPECT_EQ(deque.back(), 'e');
  deque.pop_back();
  EXPECT_EQ(deque.back(), 'd');
  deque.pop_back();
  EXPECT_EQ(deque.back(), 'c');
  deque.pop_back();
  EXPECT_EQ(deque.back(), 'b');
  deque.pop_back();
  EXPECT_EQ(deque.back(), 'a');
  deque.pop_back();
  EXPECT_TRUE(deque.empty());
}

相关代码 #

pop_back函数 #

template <typename T>
void MyDeque<T>::pop_back() {
    if (backVector.empty()) {
        if (frontVector.size() > 1) {
            rebalance(true);
            backVector.swap(frontVector);
        } else if (frontVector.size() == 1) {
            frontVector.pop_back();
        }
    } else {
        backVector.pop_back();
    }
    rebalance(false);
}

rebalance函数 #

template <typename T>
void MyDeque<T>::rebalance(bool front) {
    if (front) {
        // Rebalance frontVector
        while (frontVector.size() > (backVector.size() + 1)) {
            // Move an element from frontVector to backVector
            T temp = frontVector.back();
            frontVector.pop_back();
            // Find the correct position to insert the element in backVector
            typename std::vector<T>::iterator it = backVector.begin();
            while (it != backVector.end() && *it < temp) {
                ++it;
            }
            // Insert the element at the correct position in backVector
            backVector.insert(it, temp);
        }
    } else {
        // Rebalance backVector
        while (backVector.size() > (frontVector.size() + 1)) {
            // Move an element from backVector to frontVector
            T temp = backVector.front();
            backVector.erase(backVector.begin());
            // Find the correct position to insert the element in frontVector
            typename std::vector<T>::reverse_iterator rit = frontVector.rbegin();
            while (rit != frontVector.rend() && *rit > temp) {
                ++rit;
            }
            // Insert the element at the correct position in frontVector
            frontVector.insert(rit.base(), temp);
        }
    }
}

问题分析与修复 #

核心问题 #

问题出在rebalance函数的逻辑错误：你在rebalance时错误地对元素进行了排序插入，但Deque是需要保持插入顺序的容器，不是有序集合。测试日志里第三次pop_back后元素变成a c b，就是因为rebalance时把元素按升序插入，打乱了原本的a b c顺序，导致后续back()返回的值不符合预期。

另外，pop_back函数的逻辑也存在缺陷：当backVector为空时，调用rebalance(true)后直接swap两个vector的逻辑，不符合双端Deque的存储设计（通常frontVector反向存储前半段，backVector正向存储后半段）。

修复方案 #

1. 修正rebalance函数，移除排序逻辑，维持元素原始顺序：
   • 从frontVector移元素到backVector时，直接插入到backVector的开头（因为frontVector是反向存储，取back()得到的是前半段的最后一个元素，需要放到backVector开头来维持整体顺序）
   • 从backVector移元素到frontVector时，直接插入到frontVector的末尾（保证frontVector始终反向存储前半段）

修正后的rebalance函数：

template <typename T>
void MyDeque<T>::rebalance(bool front) {
    if (front) {
        // Rebalance frontVector：维持元素原始顺序，不排序
        while (frontVector.size() > (backVector.size() + 1)) {
            T temp = frontVector.back();
            frontVector.pop_back();
            // 插入到backVector开头，保证顺序正确
            backVector.insert(backVector.begin(), temp);
        }
    } else {
        // Rebalance backVector：维持元素原始顺序，不排序
        while (backVector.size() > (frontVector.size() + 1)) {
            T temp = backVector.front();
            backVector.erase(backVector.begin());
            // 插入到frontVector末尾，保证frontVector反向存储前半段
            frontVector.push_back(temp);
        }
    }
}

2. 修正pop_back函数的逻辑：
   当backVector为空时，将frontVector反转后转移到backVector，再执行pop_back，确保backVector始终存储正向的后半段元素。

修正后的pop_back函数：

template <typename T>
void MyDeque<T>::pop_back() {
    if (backVector.empty()) {
        // 将frontVector反转后转移到backVector，保证backVector是正向顺序
        std::reverse(frontVector.begin(), frontVector.end());
        backVector.swap(frontVector);
    }
    if (!backVector.empty()) {
        backVector.pop_back();
    }
    rebalance(false);
}

这样修改后，元素顺序会始终和插入顺序一致，back()返回的值也会符合测试用例的预期，能通过所有测试步骤。

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