c++ - 二重連結リストとイテレータを次のノードに移動する方法

Question

Deque リストを作成する必要があり、Deque リスト内には、リスト内の値を見つけるための関数呼び出し find があります。しかし、そのノードに探している値が含まれていない場合、反復を次のノードに移動しようとすると問題が発生します。彼女は私の検索機能のスニペットです：

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 クラス

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;
};

これは私の DNode クラスです

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;
};

デキュークラス

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

そのイテレータで実際には何もしていません。全体のポイントは、リスト内の次の項目を指すように変更することです。

通常、イテレータを使用して実装しoperator++ます。次のようになります。

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

イテレータを割り当てて を使用する理由は明らかではありませんunique_ptr。通常、反復子は値で返します。その内部構造は非常に単純です (1 つまたは 2 つのポインター)。それらをヒープに割り当てる必要はありません。

---

イテレータ コードを確認した後、間違った を使用しているようですnext()。イテレータではなく、現在のノードで呼び出しています。

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

---

コメントでWhozCraigが示唆したように：

このイテレータと、値による一時コピーを返すポストインクリメント マッチングの実装との違いは、カジュアルな読者にとっては当然のことかもしれません。

私が与えた++操作は前置演算子でした。つまり、実行する必要があります++*iter。したい場合は(*iter)++、後置演算子が必要です。

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

また、リストは二重にリンクされているため、適切な--前置演算子と後置演算子を提供することをお勧めします。