0

我必须构建一个 Deque 列表，在 Deque 列表中，它有一个函数调用 find，用于查找列表中的值。但是，如果该节点不包含我正在搜索的值，我在尝试将 iter 移动到下一个节点时遇到问题。她是我的查找功能的片段：

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

主文件

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

1 回答 1

3

你并没有真正用那个迭代器做任何事情。重点是您要将其更改为指向列表中的下一项。

通常使用迭代器，您将实现operator++. 它可能看起来像这样：

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

目前尚不清楚为什么要分配迭代器并使用unique_ptr. 通常您按值返回迭代器，它们的内部结构非常简单（一个或两个指针）。无需在堆上分配它们。

在看到您的迭代器代码后，您似乎只是使用了错误的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;
}

由于您的列表是双向链接的，您可能希望提供适当的--前缀和后缀运算符。

于 2013-11-01T01:48:59.050 回答