我的教授告诉我iterator，特别是generation，在这个链表中不是万无一失的。有人能告诉我为什么这种方法不是万无一失的检查"stale iterator"?
//Linklist.h
#ifndef linklist_h
#define linklist_h
class List; // Tracks the first and last items in a list.
class ListItem; // Stores the actual items in the list.
class ListIterator; // Used to loop over all items in a list.
class IteratorException; // Thrown if iterator becomes out of date.
class Meeting;
typedef int (*COMPARATOR)( ListItem* item_in_list, void* search_key );
// ListItem is an ADT that provides the capability to insert and
// remove items from a List. We use it by deriving a type from
// ListItem and defining a CompareByInsertKey member function.
class ListItem // ADT
{
friend class List;
friend class ListIterator;
public:
ListItem() {inserted=0; next=prev=NULL; plist=NULL;};
// CompareByInsertKey is invoked upon something derived from
// ListItem which we are inserting into a List. It takes as an
// argument another ListItem which is already in the list.
// It compares the keys of these two ListItems, returning a
// value in the usual manner for comparators (e.g. strcmp).
virtual int CompareByInsertKey( ListItem* item_in_list ) = 0;
// Clone the item.
virtual ListItem* Clone() = 0;
// Provides each ListItem the ability to delete itself from
// the list which contains it.
void Delete();
private:
ListItem* next; // Ptr to next item.
ListItem* prev; // Ptr to previous item.
int inserted; // Item has been inserted in a list.
List* plist; // Ptr to list containing this item.
};
class Meeting: public ListItem
{
};
// List keeps track of the first and last items in a List.
// It also keeps a generation count, which is incremented each
// something is inserted or deleted. The purpose of this
// generation count is to enable iterators to detect when the
// list has changed while being iterated.
class List
{
friend class ListIterator;
friend class ListItem;
public:
List() {head=tail=NULL; generation=0;};
// Insert new_item into the List.
void Insert( ListItem* new_item );
// Search the List for an item containing a key equal
// to search_item_key, as determined by c.
ListItem* Find( void *search_item_key, COMPARATOR c);
// Delete deleted_item from the list.
void Delete( ListItem* deleted_item );
// Delete the item containing a key equal
// to deleted_item_key, as determined by c.
int Delete( void* deleted_item_key, COMPARATOR c );
// Clone the list.
virtual List* Clone();
private:
ListItem* head; // First item in last.
ListItem* tail; // Last item in last.
unsigned long generation; // Generation number of the list.
// Provides validity check for iterators.
unsigned long NextGeneration() {return ++generation;};
unsigned long GetGeneration() {return generation;};
//Linklist.cpp
#include <iostream>
#include <string.h>
#include "linklist.h"
void ListItem::Delete()
{
plist->Delete(this);
}
void List::Insert( ListItem *new_item )
{
ListItem *search; // Ptr to search items in list.
// Want to find first item in list
// with a key >= new_item's key.
if (! head) // List is currently empty.
{
head = tail = new_item;
new_item->next = new_item->prev = NULL;
}
else // Find first item larger than inserted item.
{
for (search=head; search; search=search->next)
if (new_item->CompareByInsertKey(search) < 0)
break;
if (search==head) // Inserting new first item.
{
head = new_item;
new_item->next = search;
search->prev = head;
new_item->prev = NULL;
}
else if (! search) // Means insert as new last item.
{
tail->next = new_item;
new_item->prev = tail;
new_item->next = NULL;
tail = new_item;
}
else
{
new_item->prev = search->prev;
search->prev->next = new_item;
new_item->next = search;
search->prev = new_item;
}
}
new_item->inserted = 1;
new_item->plist = this;
NextGeneration();
}
ListItem* List::Find( void *search_item_key, COMPARATOR c)
{
ListItem *search; // Ptr to traverse each item in list.
for (search=head; search; search=search->next)
if (! c(search,search_item_key))
return search;
return NULL;
}
void List::Delete( ListItem *deleted_item )
{
if (head == deleted_item)
head = deleted_item->next;
else
deleted_item->prev->next = deleted_item->next;
if (tail == deleted_item)
tail = deleted_item->prev;
else
deleted_item->next->prev = deleted_item->prev;
deleted_item->next = NULL;
deleted_item->prev = NULL;
deleted_item->inserted = 0;
deleted_item->plist = NULL;
NextGeneration();
}
int List::Delete( void *deleted_item_key, COMPARATOR c )
{
ListItem *search; // Ptr to traverse each item in list.
if (search=Find(deleted_item_key,c))
{
Delete(search);
return 1;
}
else
return 0;
}
List* List::Clone()
{
List *newList; // Ptr to duplicate list.
ListItem *p; // Ptr to traverse original list.
ListItem *pdup; // Ptr to duplicate of p.
ListIterator *iter; // Iterator over original list.
newList = new List;
if (! newList)
return NULL;
iter = new ListIterator(*this);
while (p=(iter->NextItemInList()))
{
pdup = p->Clone();
if (! pdup)
return newList;
newList->Insert(pdup);
}
delete iter;
return newList;
}
ListIterator::ListIterator( List& list_to_iterate )
{
l = &list_to_iterate;
next_item = l->head;
generation = l->GetGeneration();
}
ListItem* ListIterator::NextItemInList()
{
ListItem *rv; // Return value - ptr to next item.
if (generation != l->GetGeneration()) // The list changed!
throw IteratorException(*l);
rv = next_item;
if (next_item)
next_item = next_item->next;
return rv;
}
谢谢!如果您需要我提供更多的信息，请评论!
假设unsigned long为32位。如果在下次尝试使用迭代器之前发生了232插入和删除操作，则您将认为列表仍然与创建迭代器时相同。