Deque-Implementation push-front

[Mae4ashy]

Hello fellow programmers,
here I am again with another question.

I'm currently trying to implement a class structure for a Deque with the two functions push_back und push_front. The push_back function is working just fine, but I can't seem to make push_front work.

This is my code so far:

template <typename T>
class Deque {

public:

  using iterator = T*;
  // constructor(s)
  Deque (): first {nullptr}, last{nullptr}, limit{nullptr}
  {
  }

  // copy constructor
  Deque (const Deque& deque):Deque(deque.last - deque.first)
  {
    std::copy(deque.first, deque.last, first);
  }
  
  // deconstructor
  ~Deque ()
  {
    delete [] first;
  }

  // assignment
  Deque& operator = (const Deque& deque)
  {
    Deque copy {deque};
    swap (copy);
    return *this;
  }

  // subscript operators
  const T& operator[](unsigned i) const{
    return first[i];
  }

  T& operator[](unsigned i) {
    return first[i];
  }
  
  // iterators
  T* begin(){
    return first;
  }

  T* end(){
    return last;
  }

  const T* begin() const{
    return first;
  }

  const T* end() const{
    return last;
  }
  
  std::size_t size () const
  {
    return last - first;
  }

  void swap (Deque& deque)
  {
    std::swap (first, deque.first);
    std::swap (last, deque.last);
    std::swap (limit, deque.limit);
  }
  
  // push_back an element
  void push_back(T x){
    
    if (last == limit)
    {
      std::size_t size = this->size();
      Deque deque {size, size * 2 + 1};
      std::move (first, last, deque.first);
      swap (deque);
    }

    *last = x;
    ++last;
  }
  
  // push_front an element
  void push_front(T x){
    
  }

private: 
  Deque (std::size_t size, std::size_t capacity) :
      first {new T[capacity]}, last {first + size}, limit {first + capacity}
    {
    }

  iterator first;
  iterator last;
  iterator limit;
};

I've read on the internet, that this is often pictured as a circular container, so I was thinking that push front could maybe move the first pointer to the end of the container if it is at the beginning, but how do I know when it is at the beginning? And what am I supposed to do with the limit at that point?

Thanks a lot for your help,
Marie

[DizzyDon]

You would need to keep a separate pointer to the start of the allocated array in order to delete it properly. So you would use that pointer to tell when you are at the beginning.

Your iterators would be more complicated, too, since you can't just use a simple pointer anymore as this won't "wrap around" automatically. You'll need an iterator class with a special increment function.

[Mae4ashy]

Okay, that sounds kinda complicated... is there an easier way?

[jonnin]

No, not really. You can probably simplify a few of the implementation details with a total from scratch redo, but the gains would be minor cleanup: you still have to do the things you have to do, and those are going to take some hands-on code writing no matter how you slice it, unless you use the STL building blocks deeper to do the heavy lifting (you already did a fair bit of this) and rewire them to look like a new thing. Even then, you still need it to do what it needs to do, you are just borrowing already written code and splicing around that.

[Mae4ashy]

Mhhhh okay thanks. I will try that out :)

[jonnin]

well the easy thing to do is just morph https://www.cplusplus.com/reference/deque/deque/ into your function names and class name :P

That being probably not the intent of the exercise, you can look for anything else with 'front' commands (push and pop front).

[coder777]

push_front(...) isn't that much different from push_back(...). In fact most of it is the same. Except for line 81. Before *first = x; you need to move all elements in that array using move_backward(...). See:

http://www.cplusplus.com/reference/algorithm/move_backward/

The Example basically does what you need.

[Mae4ashy]

Thanks a lot @jonnin and @coder777 that helped a lot and i figured it out now :))