Complexity of Deque implementation

I was asked to implement a deque in a programming course using two vectors (frontVector and backVector), which should contain half of the data of the deque. However, my implementation seems to be taking so much runtime. Here is the template with all functions included.

template <typename T>
MyDeque<T>::MyDeque() {}

template <typename T>
MyDeque<T>::MyDeque(int n) : frontVector(n/2), backVector(n/2 + n%2) {}

template <typename T>
MyDeque<T>::MyDeque(std::initializer_list<T> vals) : frontVector(), backVector(int(vals.size())) {
    int i = 0;
    for (const auto& item : vals) {
        backVector[i++]=item;
    }
    balanceVectors();
}

template <typename T>
void MyDeque<T>::push_back(T val) {
    backVector.push_back(val);
    balanceVectors();
}

template <typename T>
void MyDeque<T>::push_front(T val) {
    frontVector.insert(frontVector.begin(),val);
    balanceVectors();
}

template <typename T>
void MyDeque<T>::pop_back() {
    if (!backVector.empty()) {
        backVector.pop_back();
        balanceVectors();
    }
    else if (!frontVector.empty()) {
        frontVector.pop_back();
        balanceVectors();
    }
}

template <typename T>
void MyDeque<T>::pop_front() {
    if (!frontVector.empty()) {
        frontVector.erase(frontVector.begin());
        balanceVectors();
    }
    else if (!backVector.empty()) {
        backVector.pop_back();
        balanceVectors();
    }
}

template <typename T>
T& MyDeque<T>::back() {
    if (!backVector.empty()) {
        return backVector.back();
    }
    return frontVector.front();
}

template <typename T>
const T& MyDeque<T>::back() const {
    if (!backVector.empty()) {
        return backVector.back();
    }
    return frontVector.front();
}

template <typename T>
T& MyDeque<T>::front() {
    if (!frontVector.empty()) {
        return frontVector.front();
    }
    return backVector.back();
}

template <typename T>
const T& MyDeque<T>::front() const {
    if (!frontVector.empty()) {
        return frontVector.back();
    }
    return backVector.front();
}

template <typename T>
bool MyDeque<T>::empty() const {
  return frontVector.empty() && backVector.empty();
}

template <typename T>
int MyDeque<T>::size() const {
  return int(frontVector.size()) + int(backVector.size());
}

template <typename T>
T& MyDeque<T>::operator[](int i) {
    if (i < static_cast<int>(frontVector.size())) {
        return frontVector[i];
    } 
    else {
        return backVector[i - frontVector.size()];
    }
}

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


template <typename T>
void MyDeque<T>::balanceVectors() {
    if (backVector.size() > frontVector.size() + 1) {
        frontVector.push_back(backVector.front());
        backVector.erase(backVector.begin());
    } 
    else if (frontVector.size() > backVector.size() + 1) {
        backVector.insert(backVector.begin(), frontVector.back());
        frontVector.pop_back();
    }
}

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

I think that this complexity is because of the balanceVectors() function, which requires removing and inserting elements from the beginning of both vectors. However, I am not sure how can this be implemented using amortized constant time. Any help in decreasing the complexity will be appreciated.

You have two problems:

• Since you can only efficiently push to the end of a vector, you need
  to represent the front part of the deque in reverse order
  relative to the deque so that when you push to the front internally you are
  pushing to the back of a vector.

• Since rebalancing involves O(n) copying you should not rebalance unless you have to. Never rebalance after pushing. Only rebalance before you would have to pop from either the front vector or the back vector but can't because it is empty.

Also note that there is a symmetry to the rebalancing logic such that you rebalance by doing one copy with a reverse iterator and one copy with a forward iterator when rebalancing from front to back or from back to front.

Here is some example code if you need it.