Question

Language: C++

Complete this function

1.Object &raw_front() { // Return the element at the front of the list *without* using the iterator classes // (You may assume the list is not empty) // Place your code here.

Code:

#ifndef LIST_H
#define LIST_H

#include 

using namespace std;

template
class List {
private:
  // The basic doubly linked list node.
  // Nested inside of List, can be public
  // because the Node is itself private
  struct Node {
    Object data;
    Node *prev;
    Node *next;

    Node(const Object &d = Object{}, Node *p = nullptr, Node *n = nullptr)
        : data{d}, prev{p}, next{n} {}

    Node(Object &&d, Node *p = nullptr, Node *n = nullptr)
        : data{std::move(d)}, prev{p}, next{n} {}
  };

public:
  class const_iterator {
  public:

    // Public constructor for const_iterator.
    const_iterator() : current{nullptr} {}

    // Return the object stored at the current position.
    // For const_iterator, this is an accessor with a
    // const reference return type.

    const Object &operator*() const { return retrieve(); }

    const_iterator &operator++() {
      current = current->next;
      return *this;
    }

    const_iterator operator++(int) {
      const_iterator old = *this;
      ++(*this);
      return old;
    }

    const_iterator &operator--() {
      current = current->prev;
      return *this;
    }

    const_iterator operator--(int) {
      const_iterator old = *this;
      --(*this);
      return old;
    }

    bool operator==(const const_iterator &rhs) const { return current == rhs.current; }

    bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); }

  protected:
    Node *current;

    // Protected helper in const_iterator that returns the object
    // stored at the current position. Can be called by all
    // three versions of operator* without any type conversions.
    Object &retrieve() const { return current->data; }

    // Protected constructor for const_iterator.
    // Expects a pointer that represents the current position.
    const_iterator(Node *p) : current{p} {}

    friend class List;
  };

  class iterator : public const_iterator {
  public:

    // Public constructor for iterator.
    // Calls the base-class constructor.
    // Must be provided because the private constructor
    // is written; otherwise zero-parameter constructor
    // would be disabled.
    iterator() {}

    Object &operator*() { return const_iterator::retrieve(); }

    // Return the object stored at the current position.
    // For iterator, there is an accessor with a
    // const reference return type and a mutator with
    // a reference return type. The accessor is shown first.
    const Object &operator*() const { return const_iterator::operator*(); }

    iterator &operator++() {
      this->current = this->current->next;
      return *this;
    }

    iterator operator++(int) {
      iterator old = *this;
      ++(*this);
      return old;
    }

    iterator &operator--() {
      this->current = this->current->prev;
      return *this;
    }

    iterator operator--(int) {
      iterator old = *this;
      --(*this);
      return old;
    }

  protected:
    // Protected constructor for iterator.
    // Expects the current position.
    iterator(Node *p) : const_iterator{p} {}

    friend class List;
  };

public:
  List() { init(); }

  ~List() {
    // Place your code here.
      clear( );
      delete head;
      delete tail;
  }

  List(const List &rhs) {
    init();
    for (auto &x : rhs)
      push_back(x);
  }

  List &operator=(const List &rhs) {
    List copy = rhs;
    std::swap(*this, copy);
    return *this;
  }


  List(List &&rhs) : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail} {
    rhs.theSize = 0;
    rhs.head = nullptr;
    rhs.tail = nullptr;
  }

  List &operator=(List &&rhs) {
    std::swap(theSize, rhs.theSize);
    std::swap(head, rhs.head);
    std::swap(tail, rhs.tail);

    return *this;
  }

  // Return iterator representing beginning of list.
  // Mutator version is first, then accessor version.
  iterator begin() { return iterator(head->next); }

  const_iterator begin() const { return const_iterator(head->next); }

  // Return iterator representing endmarker of list.
  // Mutator version is first, then accessor version.
  iterator end() { return iterator(tail); }

  const_iterator end() const { return const_iterator(tail); }

  // Return number of elements currently in the list.
  int size() const { return theSize; }

  // Return true if the list is empty, false otherwise.
  bool empty() const { return size() == 0; }

  void clear() {
    while (!empty())
      pop_front();
  }

  // front, back, push_front, push_back, pop_front, and pop_back
  // are the basic double-ended queue operations.
  Object &front() { return *begin(); }

  Object &raw_front() {
    // Return the element at the front of the list *without* using the iterator classes
    // (You may assume the list is not empty)

      Node *p = new Node(, nullptr, head);
      if(tail == nullptr)
          tail = p;
      head = p;
      ++theSize;

    // (Yes, this is bad code. I just needed something that will allow the stub to compile.)

  }

  const Object &front() const { return *begin(); }

  Object &back() { return *--end(); }

  Object &raw_back() {
    // Return the element at the end of the list *without* using the iterator classes
    // (You may assume the list is not empty)

    // Place your code here.  

    // (Yes, this is bad code. I just needed something that will allow the stub to compile.)

  }

  const Object &back() const { return *--end(); }

  void push_front(const Object &x) { insert(begin(), x); }

  void push_back(const Object &x) { insert(end(), x); }

  void raw_push_front(const Object &x) {
    // insert x at the head of the list *without* using the iterator classes
    // Place your code here.
      Node *p = new Node(x, nullptr, head);
      if(tail == nullptr)
          tail = p;
      head = p;
      ++theSize;
  }

  void raw_push_back(const Object &x) {
    // insert x at the tail of the list *without* using the iterator classes
    // Place your code here.
      Node *p = new Node(x, tail, nullptr);
      if(head == nullptr)
          head = p;
      tail = p;
      ++theSize;
  }


  void raw_insert_in_order(const Object &x) {
    // insert x into the sorted list *without* using the iterator classes.
    // You may assume the list is either empty or correctly sorted.

    // Place your code here.  
  }

  void push_front(Object &&x) { insert(begin(), std::move(x)); }

  void push_back(Object &&x) { insert(end(), std::move(x)); }

  void pop_front() { erase(begin()); }

  void pop_back() { erase(--end()); }

  // Insert x before itr.
  iterator insert(iterator itr, const Object &x) {
    Node *p = itr.current;
    ++theSize;
    return iterator(p->prev = p->prev->next = new Node{x, p->prev, p});
  }

  // Insert x before itr.
  iterator insert(iterator itr, Object &&x) {
    Node *p = itr.current;
    ++theSize;
    return iterator(p->prev = p->prev->next = new Node{std::move(x), p->prev, p});
  }

  // Erase item at itr.
  iterator erase(iterator itr) {
    Node *p = itr.current;
    iterator retVal(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    --theSize;

    return retVal;
  }

  iterator erase(iterator from, iterator to) {
    for (iterator itr = from; itr != to;)
      itr = erase(itr);

    return to;
  }

  void splice(iterator position, List &lst ) {
    // Removes all the items from lst, add them prior to position in *this.
    // You may assume lst and *this are different lists.
    // **Your routine must run in constant time.**


      lst.begin().current->prev=position.current->prev;
      position.current->prev->next=lst.begin();
      position.current->prev=lst.end();
      lst.end().current->next=position;
      lst.head->next=lst.tail;
      lst.tail->prev=lst.head;

    //  if (lst.theSize == 0) return;
     // if (position.curr->prev) hook(position.curr->prev, lst.first);
     // else first = lst.first;
    //  hook(lst.last->prev, position.curr);
    //  lst.first = lst.last = nullptr;
     // theSize += lst.theSize;
     // lst.theSize = 0;

  }

private:
  int theSize;
  Node *head;
  Node *tail;

  void init() {
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
  }
};

#endif

Answer 1

I have completed the raw_front() function. Also the implementations for raw_push_back() and raw_push_front() had to be corrected. The code you had for those functions was correct only if you did not have dummy head and tail nodes for your list. But I notice you have dummy nodes. So I have corrected the code for raw_push_back() and raw_push_front() as well. Hope it helps.

#ifndef LIST_H
#define LIST_H

#include

using namespace std;

template
class List {
private:
// The basic doubly linked list node.
// Nested inside of List, can be public
// because the Node is itself private
struct Node {
Object data;
Node *prev;
Node *next;

Node(const Object &d = Object{}, Node *p = nullptr, Node *n = nullptr)
: data{d}, prev{p}, next{n} {}

Node(Object &&d, Node *p = nullptr, Node *n = nullptr)
: data{std::move(d)}, prev{p}, next{n} {}
};

public:
class const_iterator {
public:

// Public constructor for const_iterator.
const_iterator() : current{nullptr} {}

// Return the object stored at the current position.
// For const_iterator, this is an accessor with a
// const reference return type.

const Object &operator*() const { return retrieve(); }

const_iterator &operator++() {
current = current->next;
return *this;
}

const_iterator operator++(int) {
const_iterator old = *this;
++(*this);
return old;
}

const_iterator &operator--() {
current = current->prev;
return *this;
}

const_iterator operator--(int) {
const_iterator old = *this;
--(*this);
return old;
}

bool operator==(const const_iterator &rhs) const { return current == rhs.current; }

bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); }

protected:
Node *current;

// Protected helper in const_iterator that returns the object
// stored at the current position. Can be called by all
// three versions of operator* without any type conversions.
Object &retrieve() const { return current->data; }

// Protected constructor for const_iterator.
// Expects a pointer that represents the current position.
const_iterator(Node *p) : current{p} {}

friend class List;
};

class iterator : public const_iterator {
public:

// Public constructor for iterator.
// Calls the base-class constructor.
// Must be provided because the private constructor
// is written; otherwise zero-parameter constructor
// would be disabled.
iterator() {}

Object &operator*() { return const_iterator::retrieve(); }

// Return the object stored at the current position.
// For iterator, there is an accessor with a
// const reference return type and a mutator with
// a reference return type. The accessor is shown first.
const Object &operator*() const { return const_iterator::operator*(); }

iterator &operator++() {
this->current = this->current->next;
return *this;
}

iterator operator++(int) {
iterator old = *this;
++(*this);
return old;
}

iterator &operator--() {
this->current = this->current->prev;
return *this;
}

iterator operator--(int) {
iterator old = *this;
--(*this);
return old;
}

protected:
// Protected constructor for iterator.
// Expects the current position.
iterator(Node *p) : const_iterator{p} {}

friend class List;
};

public:
List() { init(); }

~List() {
// Place your code here.
clear( );
delete head;
delete tail;
}

List(const List &rhs) {
init();
for (auto &x : rhs)
push_back(x);
}

List &operator=(const List &rhs) {
List copy = rhs;
std::swap(*this, copy);
return *this;
}

List(List &&rhs) : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail} {
rhs.theSize = 0;
rhs.head = nullptr;
rhs.tail = nullptr;
}

List &operator=(List &&rhs) {
std::swap(theSize, rhs.theSize);
std::swap(head, rhs.head);
std::swap(tail, rhs.tail);

return *this;
}

// Return iterator representing beginning of list.
// Mutator version is first, then accessor version.
iterator begin() { return iterator(head->next); }

const_iterator begin() const { return const_iterator(head->next); }

// Return iterator representing endmarker of list.
// Mutator version is first, then accessor version.
iterator end() { return iterator(tail); }

const_iterator end() const { return const_iterator(tail); }

// Return number of elements currently in the list.
int size() const { return theSize; }

// Return true if the list is empty, false otherwise.
bool empty() const { return size() == 0; }

void clear() {
while (!empty())
pop_front();
}

// front, back, push_front, push_back, pop_front, and pop_back
// are the basic double-ended queue operations.
Object &front() { return *begin(); }

Object &raw_front() {
// Return the element at the front of the list *without* using the iterator classes
// (You may assume the list is not empty)
return (head->next).data;
}

const Object &front() const { return *begin(); }

Object &back() { return *--end(); }

Object &raw_back() {
// Return the element at the end of the list *without* using the iterator classes
// (You may assume the list is not empty)

// Place your code here.

// (Yes, this is bad code. I just needed something that will allow the stub to compile.)

}

const Object &back() const { return *--end(); }

void push_front(const Object &x) { insert(begin(), x); }

void push_back(const Object &x) { insert(end(), x); }

void raw_push_front(const Object &x) {
// insert x at the head of the list *without* using the iterator classes
// Place your code here.
Node *p = new Node(x, head, head->next);
   head->next = p;
   p->next->prev = p;
++theSize;
}

void raw_push_back(const Object &x) {
// insert x at the tail of the list *without* using the iterator classes
// Place your code here.
Node *p = new Node(x, tail->prev, tail);
   tail->prev = p;
   p->prev->next = p;
++theSize;
}

void raw_insert_in_order(const Object &x) {
// insert x into the sorted list *without* using the iterator classes.
// You may assume the list is either empty or correctly sorted.

// Place your code here.
}

void push_front(Object &&x) { insert(begin(), std::move(x)); }

void push_back(Object &&x) { insert(end(), std::move(x)); }

void pop_front() { erase(begin()); }

void pop_back() { erase(--end()); }

// Insert x before itr.
iterator insert(iterator itr, const Object &x) {
Node *p = itr.current;
++theSize;
return iterator(p->prev = p->prev->next = new Node{x, p->prev, p});
}

// Insert x before itr.
iterator insert(iterator itr, Object &&x) {
Node *p = itr.current;
++theSize;
return iterator(p->prev = p->prev->next = new Node{std::move(x), p->prev, p});
}

// Erase item at itr.
iterator erase(iterator itr) {
Node *p = itr.current;
iterator retVal(p->next);
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
--theSize;

return retVal;
}

iterator erase(iterator from, iterator to) {
for (iterator itr = from; itr != to;)
itr = erase(itr);

return to;
}

void splice(iterator position, List &lst ) {
// Removes all the items from lst, add them prior to position in *this.
// You may assume lst and *this are different lists.
// **Your routine must run in constant time.**

lst.begin().current->prev=position.current->prev;
position.current->prev->next=lst.begin();
position.current->prev=lst.end();
lst.end().current->next=position;
lst.head->next=lst.tail;
lst.tail->prev=lst.head;

// if (lst.theSize == 0) return;
// if (position.curr->prev) hook(position.curr->prev, lst.first);
// else first = lst.first;
// hook(lst.last->prev, position.curr);
// lst.first = lst.last = nullptr;
// theSize += lst.theSize;
// lst.theSize = 0;

}

private:
int theSize;
Node *head;
Node *tail;

void init() {
theSize = 0;
head = new Node;
tail = new Node;
head->next = tail;
tail->prev = head;
}
};

#endif