Doubly linked list and how to move the iterator to the next node

Question

I have to build a Deque list and inside the the Deque list, it has a function call find, to find the value inside the list. But I'm having problem to try to move the iter over to the next node if that node does not contain the value that I am searching for. Her is the snippet of my find function:

unique_ptr<DequeIterator<E>> find(E match)
{
    assert(!is_empty());
    bool is_found = true;

        // set the pointer point to the first node from the beginning        
    unique_ptr<DequeIterator<E>> iter(iter_begin());

    while(iter->node()->value() != match)
    {
                // here is I want to move the iter position
                // over to the next node
        iter->next();
                // print out the value at the node to re-check if
                // it matches
        cout << iter->node()->value() << endl;
    }

    if(is_found)
    {
        cout << "found" << iter->node()->value() << endl;

    }
    else
        cout << "no match" << endl;
    return iter;
}


unique_ptr<DequeIterator<E>> iter_begin()
{       
        // _head is set to nullptr inside the constructor
    return unique_ptr<DequeIterator<E>>(new DequeIterator<E>(_head));
}

DequeIterator class

template<class E>
class DequeIterator {
public:
  // You may need to modify this class. Feel free to modify the definitions of
  // these functions, or add new member functions.

  DequeIterator(DNode<E>* node) {
    _node = node;
  }

  bool at_end() {
    return _node == nullptr;
  }

  E value() {
    assert(!at_end());
    return _node->value();
  }

  void set_value(E x) {
    assert(!at_end());
    _node->set_value(x);
  }

  void next() {
    assert(!at_end());
    _node = _node->next();
  }

  DNode<E>* node() { return _node; }

private:
  DNode<E>* _node;
};

This is my DNode class

template<class E>
class DNode {
public:
  DNode(DNode<E>* prev, E value, DNode<E>* next) {
    _value = value;
    _prev = prev;
    _next = next;
    dnode_census++;
  }

  ~DNode() {
    dnode_census--;
  }

  // The program crashes right here
  // after it goes into the E value()
  E value() { return _value; }
  void set_value(E value) { _value = value; }
  DNode<E>* prev() { return _prev; }
  void set_prev(DNode<E>* prev) { _prev = prev; }
  DNode<E>* next() { return _next; }
  void set_next(DNode<E>* next) { _next = next; }

private:
  E _value;
  DNode<E> *_prev;
  DNode<E> *_next;
};

Deque class

template<class E>
class Deque {
public:

Deque()
{
    _head = 0;
    _size = 0;
    _tail = 0;
}

  ~Deque() {
    clear();
  }

  // Make the deque empty. O(n) time.
  void clear() {
    while (!is_empty())
      erase_back();
  }

  // Return the current size of the deque. O(1) time.
  int size() {
    return _size;
  }

  // Return true when the deque is empty. O(1) time.
  bool is_empty() {
    return (size() == 0);
  }


unique_ptr<DequeIterator<E>> iter_begin()
{
    return unique_ptr<DequeIterator<E>>(new DequeIterator<E>(_head));
}

unique_ptr<DequeIterator<E>> iter_at(int index)
{
    assert((index >= 0) && (index <= size()));
    unique_ptr<DequeIterator<E>> iter(iter_begin());
    for(int j = 0; j < index; j++)
        iter->next();
    return iter;
}

E front()
{
    assert(!is_empty());
    return _head->value();
}


E back()
{
    assert(!is_empty());
    return _tail->value();
}


void insert_after(DequeIterator<E>& iter, E x)
{
    if(_size == 0)
    {
        insert_front(x);
    }
    else
    {
        assert(!iter.at_end());
        DNode<E>* temp = new DNode<E>(iter.node(), x, iter.node()->next());
        iter.node()->next()->set_next(temp);
        iter.node()->next()->set_prev(temp);
    }

    _size++;    
}

void insert_before(DequeIterator<E>& iter, E x)
{
    if(_size == 0)
    {
        insert_front(x);
    }
    else
    {
        assert(!is_empty());
        DNode<E>* temp2 = new DNode<E>(iter.node()->prev(), x, iter.node());
        (iter.node()->prev())->set_next(temp2);
        (iter.node()->prev())->set_prev(temp2);
    }
    _size++;    
}

void insert_front(E x)
{
    if(is_empty())
    {
        DNode<E>* temp = new DNode<E>(nullptr, x, nullptr);
        _head = temp;
        _tail = temp;
    }
    else
    {
        DNode<E>* temp = _head;
        DNode<E>* temp2 = new DNode<E>(nullptr, x, temp);
        _head = temp2;
    }
    _size++;
}


void insert_back(E x)
{
    if(is_empty())
    {
        insert_front(x);
    }
    else
    {
        assert(!is_empty());
        DNode<E>* temp = new DNode<E>(_tail, x, nullptr);
        _tail = temp;
        _size++;
        if(_size > 1)
            cout << _tail->prev()->value() << endl;
    }

}

void erase(DequeIterator<E>& iter)
{
    assert((!is_empty()) || !iter.at_end());

    DNode<E>* temp = iter.node();
    temp->next()->set_prev(temp->prev());
    temp->prev()->set_next(temp->next());

    delete iter.node()->next();
    _size--;
}

void erase_front()
{
    assert(!is_empty());
    DNode<E>* temp = _head;
    _head = temp->next();
    delete temp;
    _size--;

}


void erase_back()
{
    assert(!is_empty());
    DNode<E>* temp = _tail;
    _tail = temp->prev();
    delete temp;
    _size--;
}


unique_ptr<DequeIterator<E>> find(E match)
{
    assert(!is_empty());
    bool is_found = true;

    unique_ptr<DequeIterator<E>> iter(iter_begin());

    while(iter->value() != match)
    {
        iter->next();
        cout << iter->value() << endl;
    }

    if(is_found)
    {
        cout << "found" << iter->node()->value() << endl;

    }
    else
        cout << "no match" << endl;
    return iter;
}


 // Return the element value at position index, which must be
 // valid. O(n) time.
E get(int index) 
{
    assert((index >= 0) && (index < size()));

    unique_ptr<DequeIterator<E>> iter(iter_begin());

    for(int j = 0; j < index; j++)
        iter->next();
        return iter->node()->value();
}

void meld(Deque<E>& other)
{

}

private:
   DNode<E>* _head;
  DNode<E>* _tail;
  int _size;
};

main.cpp

int main() {
  assert_no_leak(0);

  // Element objects to reuse. All upper case letters of the alphabet.
  //const int N = 5;
  const int N = 26;
  char letters[N];
  for (int i = 0; i < N; i++)
    letters[i] = 'A' + i;

  // Now there are a series of unit tests. Each test checks a few
  // related member functions. The tests use assert(...) to look for
  // bugs, so if one of these assertions fails, that indicates a bug
  // in your deque code.

  print_test_title("Deque constructor");
  unique_ptr<Deque<char>> q(new Deque<char>());
  assert_no_leak(0);

  print_test_title("Deque::size");
  assert(q->size() == 0);

  print_test_title("Deque::is_empty");
  assert(q->is_empty());

  print_test_title("Deque::insert_back");
  for (int i = 0; i < N; i++) {
    assert(q->size() == i);
    assert_no_leak(i);

    q->insert_back(letters[i]);

    assert(!q->is_empty());
    assert(q->size() == (i+1));
    assert_no_leak(i+1);
  }




  print_test_title("iteration");
  unique_ptr<DequeIterator<char>> iter(q->iter_begin());
  assert(!iter->at_end());
  assert_no_leak(N);
  for (int i = 0; !iter->at_end(); i++, iter->next()) {
    assert(i < N);
    assert(iter->value() == letters[i]);
    assert_no_leak(N);
  }
  assert_no_leak(N);

 /* for (int i = 0; i < N; i++)
      cout << q->get(i) << endl;*/


  print_test_title("Deque::find");

  iter = q->find('A');
  assert(!iter->at_end());
  assert(iter->value() == 'A');
  assert_no_leak(N);

  **// This is where I got the unhandled exception**
  iter =  q->find('T');
  assert(!iter->at_end());
  assert(iter->value() == 'T');
  assert_no_leak(N);

  iter = q->find('?');
  assert(iter->at_end());
  assert_no_leak(N);

  print_test_title("Deque::get");
  for (int index = 0; index < N; index++) {
    assert(q->get(index) == letters[index]);
    assert_no_leak(N);
  }

  print_test_title("Deque::front");
  assert(q->front() == 'C');
  assert_no_leak(N);

  print_test_title("Deque::back");
  assert(q->back() == 'Z');
  assert_no_leak(N);

  print_test_title("Deque::erase_front");
  for (int i = 0; i < N; i++) {
    assert(q->front() == letters[i]);
    assert(q->size() == (N-i));
    assert_no_leak(N-i);
    q->erase_front();
  }
  assert(q->is_empty());
  assert_no_leak(0);

  print_test_title("Deque::erase_back");
  for (int i = 0; i < N; i++)
    q->insert_back(letters[i]);
  for (int i = 0; i < N; i++) {
    assert(q->back() == letters[N-i-1]);
    assert(q->size() == (N-i));
    assert_no_leak(N-i);
    q->erase_back();
  }
  assert(q->is_empty());
  assert_no_leak(0);

  print_test_title("Deque::insert_front");
  for (int i = 0; i < N; i++) {
    q->insert_front(letters[i]);
    assert(q->front() == letters[i]);
    assert(q->size() == (i+1));
    assert_no_leak(i+1);
  }
  assert(q->size() == N);
  assert_no_leak(N);

  print_test_title("Deque::clear");
  q->clear();
  assert(q->is_empty());
  assert_no_leak(0);
  for (int size = 0; size <= N; size++) {
    assert(q->is_empty());
    assert_no_leak(0);

    for (int i = 0; i < size; i++)
      q->insert_back(letters[i]);

    assert(q->size() == size);
    assert_no_leak(size);

    q->clear();
    assert(q->is_empty());
    assert_no_leak(0);
  }

  print_test_title("insert_after, insert_before, erase");
  assert(q->is_empty());
  iter = q->iter_begin(); // iter is at end of empty queue
  q->insert_before(*iter, 'X');
  assert(queue_equals_string(*q, "X"));
  assert_no_leak(1);
  iter = q->iter_begin(); // iter is at start of queue with 1 element
  q->insert_after(*iter, 'O');
  assert(queue_equals_string(*q, "XO"));
  assert_no_leak(2);
  q->insert_after(*iter, 'Z');
  assert(queue_equals_string(*q, "XZO"));
  assert_no_leak(3);
  iter->next(); // iter is at second position (Z)
  q->insert_before(*iter, 'C');
  assert(queue_equals_string(*q, "XCZO"));
  assert_no_leak(4);
  q->insert_after(*iter, 'A');
  assert(queue_equals_string(*q, "XCZAO"));
  assert_no_leak(5);
  iter->next(); // iter is at fourth position (A)
  q->erase(*iter); // erase A
  assert(queue_equals_string(*q, "XCZO"));
  assert_no_leak(4);
  iter = q->iter_begin(); // X
  iter->next(); // C
  iter->next(); // Z
  q->erase(*iter); // erase Z
  assert(queue_equals_string(*q, "XCO"));
  assert_no_leak(3);
  q->erase(*q->iter_begin()); // erase X
  assert(queue_equals_string(*q, "CO"));
  assert_no_leak(2);
  iter = q->iter_begin(); // erase O
  iter->next();
  q->erase(*iter);
  assert(queue_equals_string(*q, "C"));
  assert_no_leak(1);
  q->erase(*q->iter_begin()); // erase C
  assert(queue_equals_string(*q, ""));
  assert_no_leak(0);

  print_test_title("Deque::splice");
  assert(q->is_empty());
  assert_no_leak(0);
  unique_ptr<Deque<char>> q2(new Deque<char>());
  assert_no_leak(0);
  for (int i = 0; i < 5; i++) {
    q->insert_back(letters[i]);
    q2->insert_back(letters[i]);
  }
  assert(q->size() == 5);
  assert(q2->size() == 5);
  assert_no_leak(10);
  q->meld(*q2);
  assert(q->size() == 10);
  assert(q2->is_empty());
  assert_no_leak(10);
  assert(queue_equals_string(*q, "ABCDEABCDE"));

  if (DO_PERFORMANCE_TEST) {
    print_test_title("Performance");
    q->clear();
    time_t start = time(nullptr);
    for (int i = 0; i < BIG_N; i++) {
      q->insert_front('A');
      if ((i % 1000) == 0)
        cout << '.';
    }
    time_t stop = time(nullptr);
    assert(q->size() == BIG_N);
    cout << endl
         << "  Elapsed time to insert_front " << BIG_N << " times: " 
         << (stop - start) << " seconds" << endl;
  }

  return 0;
}

Answer 1

You're not really doing anything with that iterator. The whole point is you want to change it to point to the next item in the list.

Normally with iterators you would implement operator++. It might look something like this:

template <class E>
DequeIterator<E> & DequeIterator::operator++()
{
    _node = _node->next;
    return *this;
}

It's not clear why you are allocating your iterators and using unique_ptr. Normally you return iterators by value, and their internals are very simple (a pointer or two). No need to allocate them on the heap.

---

After seeing your iterator code, it seems you're just using the wrong next(). You're calling it on the current node, rather than the iterator:

iter->node()->next();   // incorrect
iter->next();           // correct

---

As suggested by WhozCraig in the comments:

the difference between this iterator and a post-increment matching implementation with its by-value temp-copy return may be warranted for the casual reader.

The ++ operation I gave was the prefix operator, meaning you need to do ++*iter. If you want to do (*iter)++, you need a postfix operator:

template <class E> DequeIterator<E> DequeIterator::operator++(int) {
    DequeIterator<E> temp(*this);
    _node = _node->next;
    return temp;
}

And since your list is double-linked, you might like to provide the appropriate -- prefix and postfix operators.