title: insert x into the sorted list *without* using the iterator classes
body: <p>Im confused on how to finish the function<br>
  <strong>void raw_insert_in_order(const Object &amp;x)</strong> 
  The goal is to insert x into the sorted list <em>without</em> using the iterator classes  assuming the list is either empty or correctly sorted.
  This confuses me because the program itself uses iterator classes but the project asks for us to do a function without the use of them. Anyone have an idea on how to do this function of inserting in order? I could use the help. I appreciate it!</p>
  
  <pre><code>#ifndef LIST_H
  #define LIST_H
  
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  template&lt;typename Object&gt;
  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 &amp;d = Object{}, Node *p = nullptr, Node *n = nullptr)
          : data{d}, prev{p}, next{n} {}
  
      Node(Object &amp;&amp;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 &amp;operator*() const { return retrieve(); }
  
      const_iterator &amp;operator++() {
        current = current-&gt;next;
        return *this;
      }
  
      const_iterator operator++(int) {
        const_iterator old = *this;
        ++(*this);
        return old;
      }
  
      const_iterator &amp;operator--() {
        current = current-&gt;prev;
        return *this;
      }
  
      const_iterator operator--(int) {
        const_iterator old = *this;
        --(*this);
        return old;
      }
  
      bool operator==(const const_iterator &amp;rhs) const { return current == rhs.current; }
  
      bool operator!=(const const_iterator &amp;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 &amp;retrieve() const { return current-&gt;data; }
  
      // Protected constructor for const_iterator.
      // Expects a pointer that represents the current position.
      const_iterator(Node *p) : current{p} {}
  
      friend class List&lt;Object&gt;;
    };
  
    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 &amp;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 &amp;operator*() const { return const_iterator::operator*(); }
  
      iterator &amp;operator++() {
        this-&gt;current = this-&gt;current-&gt;next;
        return *this;
      }
  
      iterator operator++(int) {
        iterator old = *this;
        ++(*this);
        return old;
      }
  
      iterator &amp;operator--() {
        this-&gt;current = this-&gt;current-&gt;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&lt;Object&gt;;
    };
  
  public:
    List() { init(); }
  
    ~List() {
      // Place your code here.
        clear( );
        delete head;
        delete tail;
    }
  
    List(const List &amp;rhs) {
      init();
      for (auto &amp;x : rhs)
        push_back(x);
    }
  
    List &amp;operator=(const List &amp;rhs) {
      List copy = rhs;
      std::swap(*this, copy);
      return *this;
    }
  
  
    List(List &amp;&amp;rhs) : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail} {
      rhs.theSize = 0;
      rhs.head = nullptr;
      rhs.tail = nullptr;
    }
  
    List &amp;operator=(List &amp;&amp;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-&gt;next); }
  
    const_iterator begin() const { return const_iterator(head-&gt;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 &amp;front() { return *begin(); }
  
    Object &amp;raw_front() {
      // Return the element at the front of the list *without* using the iterator classes
      // (You may assume the list is not empty)
      // (Yes, this is bad code. I just needed something that will allow the stub to compile.)
        return head ;
    }
  
    const Object &amp;front() const { return *begin(); }
  
    Object &amp;back() { return *--end(); }
  
    Object &amp;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.)
        return tail;
    }
  
    const Object &amp;back() const { return *--end(); }
  
    void push_front(const Object &amp;x) { insert(begin(), x); }
  
    void push_back(const Object &amp;x) { insert(end(), x); }
  
    void raw_push_front(const Object &amp;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 &amp;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 &amp;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 &amp;&amp;x) { insert(begin(), std::move(x)); }
  
    void push_back(Object &amp;&amp;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 &amp;x) {
      Node *p = itr.current;
      ++theSize;
      return iterator(p-&gt;prev = p-&gt;prev-&gt;next = new Node{x, p-&gt;prev, p});
    }
  
    // Insert x before itr.
    iterator insert(iterator itr, Object &amp;&amp;x) {
      Node *p = itr.current;
      ++theSize;
      return iterator(p-&gt;prev = p-&gt;prev-&gt;next = new Node{std::move(x), p-&gt;prev, p});
    }
  
    // Erase item at itr.
    iterator erase(iterator itr) {
      Node *p = itr.current;
      iterator retVal(p-&gt;next);
      p-&gt;prev-&gt;next = p-&gt;next;
      p-&gt;next-&gt;prev = p-&gt;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&lt;Object&gt; &amp;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.**
  
        Node *p = position.current;
        theSize += lst.size();
        p-&gt;prev-&gt;next = lst.head-&gt;next;
        lst.head-&gt;next-&gt;prev = p-&gt;prev;
        lst.tail-&gt;prev-&gt;next = p;
        p-&gt;prev = lst.tail-&gt;prev;
        lst.init();
  
  
    }
  
  private:
    int theSize;
    Node *head;
    Node *tail;
  
    void init() {
      theSize = 0;
      head = new Node;
      tail = new Node;
      head-&gt;next = tail;
      tail-&gt;prev = head;
    }
  };
  
  #endif
  </code></pre>