2

I created a pop_back function and rebalancing for this deque I am making, but when it rebalances, I wanted it to become a b c after the 3rd pop back so that the c can be popped off, therefore, passing the test case.

Would this be a rebalance issue or a pop back issue as my rebalance is working and passing previous test cases (any advice appreciated)?

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());
}

my pop back function is looking like this

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);

and my rebalance function is looking like this

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);
        }
    }
}
BadCoder12
  • 21
  • 1
  • please post a [mcve] – 463035818_is_not_an_ai Apr 19 '23 at 10:56
  • 1
    +1 for actually running tests and having identified the issue, but...`MyDequeTest` isnt something others can compile and run, it is good background information but does not replace a [mcve] that also others can compile debug and test – 463035818_is_not_an_ai Apr 19 '23 at 10:58
  • How about you print out the front and back vector before and after each part, and then you can find out which one is wrong? – user253751 Apr 19 '23 at 11:01
  • In the case `backVector.empty() && frontVector.size() > 1`, `MyDeque::pop_back` doesn't call `pop_back` on either vector, so the total size of the two vectors remains unchanged. – Igor Tandetnik Apr 22 '23 at 20:14

0 Answers0