个人中心
gpt4 book ai didi

c++ - 这个迭代器会出什么问题？

转载 作者：太空宇宙 更新时间：2023-11-04 13:47:25 25 4
gpt4 key购买 nike

<分区>

我的教授告诉我这个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;
}

谢谢!如果您需要我提供更多信息，请发表评论!

25 4 0
文章推荐： html - 用线条连接 Canvas
文章推荐： c++ - 循环依赖问题
文章推荐： java - Arrays.asList() 创建的 List 上的 remove() 抛出 UnsupportedOperationException
文章推荐： java - Fragment 类型的 getSupportFragmentManager() 方法未定义
太空宇宙
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com