CODEWITHSUNDEEP
c++deque
Milk_QD
Milk_QD

Reputation: 135

Undefined Behavior When Getting the Size of Deque which is a Class Variable

I used two deques as class variables to implement a data structure to allow efficient adding to the middle. So whenever I add an element to the my DS, the two deques will re-balance themselves if the difference in sizes of the two deques is greater than 1 as shown in the rebalace().

However, the condition of (deque2.size() - deque1.size()) > 1 didn't work as expected. The first element will always be pushed to deque1 and it will have size 1 while deque2 will have size 0. Yet, when i debug, (deque2.size() - deque1.size()) evaluates to some very big integer and caused the condition to be true.

When I tried to use local variables to store the sizes of deques and their differences in size. It works as expected.

class teque{
private:
    deque<ui> firstHalf;  
    deque<ui> secondHalf;
    void rebalance(){
        int size1 = firstHalf.size();
        int size2 = secondHalf.size();
        int diff1 = firstHalf.size() - secondHalf.size();
        int diff2 = secondHalf.size() - firstHalf.size();
        if(firstHalf.size() == secondHalf.size()) return;
        else if (firstHalf.size() - secondHalf.size() > 1){
            secondHalf.push_front(firstHalf.back());
            firstHalf.pop_back();
        }
        else if ((secondHalf.size() - firstHalf.size()) > 1){ //Didn't work as expected
            cout << (secondHalf.size() - firstHalf.size()); //Output a very large number
            firstHalf.push_back(secondHalf.front());
            secondHalf.pop_front();
        }
        //debug();
    }
public:
    teque() {};
    void push_back(ui ele){
        firstHalf.size() == 0 ? firstHalf.push_back(ele) : secondHalf.push_back(ele);
        rebalance();
    }
    void push_front(ui ele){
        firstHalf.push_front(ele);
        rebalance();
    }
    void push_middle(ui ele){
        firstHalf.push_back(ele);
        rebalance();
    }
    ui get (ui index){
        if(index < firstHalf.size()) return firstHalf[index];
        else //if(index >= firstHalf.size()) 
            return secondHalf[index-firstHalf.size()];
    }

int main(){
    teque test = teque();
    teque.push_back(9);
}

Is it my understanding of Class in C++ is wrong some where?

Upvotes: 1

Views: 543

Answers (1)

DevSolar
DevSolar

Reputation: 70243

deque.size() returns a value of size_type, which is unsigned. So if you would get a negative value, you will get a very large positive one instead.

Upvotes: 1

Related Questions