Modify your Deque implementation to improve pop_front() and pop_back(). For pop_front() if vecOne is empty, first half of the elements from vecTwo is moved to vecOne, then pop_back() on vecOne is called. For pop_back() if vecTwo is empty, first half of the elements from vecOne is moved to vecTwo, then pop_back on vecTwo is called. This test program should work correctly with your new implementation.

__________________________________________________________________________________________________________________

My Deque Class

___________________________________________________________________________________________________________________

#ifndef DEQUE_H #define DEQUE_H

#include

using namespace std;

template class DequeIterator;

template class Deque { public: typedef DequeIterator iterator;

Deque(): vecOne(), vecTwo() { } Deque(const unsigned int size, const T & initial): vecOne(size/2, initial), vecTwo(size-(size/2), initial) { } Deque(const Deque & d): vecOne(d.vecOne), vecTwo(d.vecTwo) { } ~Deque() { } // destructors for vecOne and vecTwo are automatically called // never call a destructor explicitly Deque & operator=(const Deque & d);

T & operator[](unsigned int); T & front(); T & back(); bool empty(); iterator begin(); iterator end(); //void erase(const iterator &); //void erase(const iterator &, const iterator &); //void insert(const iterator &, const T &); int size(); void push_front(const T & value); void push_back(const T & value); void pop_front(); void pop_back();

protected: vector vecOne; vector vecTwo; };

template Deque & Deque::operator=(const Deque & d) { vecOne = d.vecOne; vecTwo = d.vecTwo; return *this; } // operator=

template T & Deque::operator[](unsigned int index) { unsigned int n = vecOne.size(); if(index < n) return vecOne[(n-1) - index]; else return vecTwo[index - n]; } // operator []

template T & Deque::front() { if(vecOne.empty()) return vecTwo.front(); return vecOne.back(); } // front

template T & Deque::back() { if(vecTwo.empty()) return vecOne.back(); return vecTwo.back(); } // back

template bool Deque::empty() { return ( vecOne.empty() && vecTwo.empty() ); } // empty

template DequeIterator Deque::begin() { return iterator(this, 0); } // begin

template DequeIterator Deque::end() { return iterator(this, size()); } // end

template int Deque::size() { return vecOne.size() + vecTwo.size(); } // size

template void Deque::push_front(const T & value) { vecOne.push_back(value); } // push_front

template void Deque::push_back(const T & value) { vecTwo.push_back(value); } // push_back

template void Deque::pop_front() { if(vecOne.empty()) vecTwo.erase(vecTwo.begin()); else vecOne.pop_back(); } // pop_front

template void Deque::pop_back() { if(vecTwo.empty()) { cout << "running pop_back if "; vecOne.erase(vecOne.begin()); } else { cout << "running pop_back else "; vecTwo.pop_back(); } } // pop_back

template class DequeIterator { friend class Deque; typedef DequeIterator iterator;

public: DequeIterator(): theDeque(0), index(0) { } DequeIterator(Deque * d, int i): theDeque(d), index(i) { } DequeIterator(const iterator & d): theDeque(d.theDeque), index(d.index) { }

T & operator*(); iterator & operator++(); iterator operator++(int); iterator & operator--(); iterator operator--(int); bool operator==(const iterator & r); bool operator!=(const iterator & r); //bool operator<(const iterator & r); //T & operator[](unsigned int i); iterator operator=(const iterator & r); iterator operator+(unsigned i); iterator operator-(unsigned i);

protected: Deque * theDeque; int index; };

template T & DequeIterator::operator*() { return (*theDeque)[index]; } // operator*

template DequeIterator & DequeIterator::operator++() { if( index < ( theDeque->size() ) ) index++;

return *this; } // operator++ (pre-increment)

template DequeIterator DequeIterator::operator++(int) { iterator temp(*this); if( index < ( theDeque->size() ) ) index++;

return temp; } // operator++ (post-increment)

template DequeIterator & DequeIterator::operator--() { if(index > 0) index--; return *this; } // operator-- (pre-decrement)

template DequeIterator DequeIterator::operator--(int) { iterator temp(*this); if(index > 0) index--; return temp; } // operator-- (post-decrement)

template bool DequeIterator::operator==(const iterator & r) { return (index == r.index) && (theDeque == r.theDeque); } // operator==

template bool DequeIterator::operator!=(const iterator & r) { return !( (index == r.index) && (theDeque == r.theDeque) ); } // operator!=

template DequeIterator DequeIterator::operator=(const iterator & r) { theDeque = r.theDeque; index = r.index; return *this; } // operator=

template DequeIterator DequeIterator::operator+(unsigned i) { if( index + i < theDeque->size() ) index += i; return iterator(*this); } // operator+

template DequeIterator DequeIterator::operator-(unsigned i) { if(index - i > 0) index -= i; return iterator(*this); } // operator-

#endif

___________________________________________________________________________________________

Test Program

____________________________________________________________________________________________

#include  #include "Deque.h" using namespace std; main() { Deque d; d.push_front(1); d.push_front(2); d.push_front(3); d.push_back(50); d.push_back(20); // 3 2 1 50 20 d.pop_back(); d.pop_back(); d.pop_back(); // 3 2 Deque::iterator i; for (i = d.begin(); i != d.end(); ++i) cout << *i << " "; cout << endl; d.push_back(60); d.push_back(70); // 3 2 60 70 for (i = d.begin(); i != d.end(); ++i) cout << *i << " "; cout << endl; d.pop_front(); d.pop_front(); d.pop_front(); // 70 for (i = d.begin(); i != d.end(); ++i) cout << *i << " "; cout << endl; }