1

ポインティングは、ポインターの文字通りの意味なしで使用されます。次の段落を一粒の塩で取ってください。

rbegin() == end() と rend() == begin() を線形データ構造で作成して、逆イテレータを実装するのは簡単です。これは、イテレータが指している直前の要素への逆アクセスをマップできるためです ( rbegin() は end() を指しますが、たとえば end()-1 にアクセスします)。しかし、ツリー、または私の場合はハッシュ テーブルを扱う場合、このマッピングをどのように処理すればよいでしょうか? 私は現在、「OneAfterTheLast」フラグを使用して、転送反復セッションの終了をマークしています。逆反復子ロジックを手動で実装し、「OneBeforeTheFirst」フラグも追加することを考えています。それは良いデザインですか？

また、find() メソッドは、キーが見つからない場合に "OneAfterTheLast" 編集されたイテレータを返す必要がありますか、それとも check メソッドで両方のフラグ (OneAfterTheEnd と OneBeforeTheFirst) をチェックする必要がありますか?

これが私の公開インターフェースです。参考までに、まだリバース イテレータ メソッドを使用していません。コンテナ クラスとイテレータ クラスはどちらも不透明です。

typedef PWError (*PWDictCallback)(const char *key, const char *val, void *extra);
PWError pwdictCreate(PWDict **dictRef, PWDictImplementationId id, size_t elements);
PWError pwdictCreateWithImplementation(PWDict **dictRef, const PWDictImplementation* impl, size_t elements);
void pwdictDestroy(PWDict *dict);
unsigned int pwdictSize(const PWDict *dict);
unsigned long pwdictSizeInBytes(const PWDict *dict);
PWError pwdictGet(const PWDict *dict, const char *key, char *output, size_t size);
PWError pwdictSet(PWDict *dict, const char *key, const char *value);
PWError pwdictRemove(PWDict *dict, const char *key);
PWError pwdictIteratorCreate(PWDictIterator **itRef, PWDict *dict);
PWError pwdictIteratorBegin(PWDictIterator *it);
int pwdictIteratorIsEnd(PWDictIterator *it);
void pwdictIteratorDestroy(PWDictIterator *it);
PWError pwdictFind(PWDictIterator *it, const char *key);
const char *pwdictIteratorGetKey(const PWDictIterator *it);
const char *pwdictIteratorGetValue(const PWDictIterator *it);
PWError pwdictIteratorSetValue(PWDictIterator *it, const char *value);
PWError pwdictIteratorRemove(PWDictIterator *it);
PWError pwdictIteratorNext(PWDictIterator *it);
PWError pwdictClear(PWDict *dict);
PWError pwdictAdd(PWDict *dict, const PWDict *from);
int pwdictIsEqual(const PWDict *d1, const PWDict *d2);
PWError pwdictForeach(PWDict *dict, PWDictCallback cb, void *extra);
void pwdictPrint(const PWDict *dict, int logLevel);
4

3 に答える 3

3

std::reverse_iterator通常のイテレータを保持することでそれを行いますが、(概念的には)*(i-1)逆参照で戻ります。同じことを行うことも、直接使用することもできますstd::reverse_iterator。

于 2012-07-13T21:32:15.363 に答える
2

C++03 標準から:

逆反復子とそれに対応する反復子 i の間の基本的な関係は、次の恒等式によって確立されます&*(reverse_iterator(i)) == &*(i - 1)。

このマッピングは、配列の末尾を超えるポインターは常に存在するものの、配列の先頭の前には有効なポインターが存在しない可能性があるという事実によって決定されます。

(2 番目の文は C++11 標準から削除されました)

逆イテレータが通常実装される方法は、逆イテレータが論理的に参照する項目の後の要素を指すコンテナーの通常のイテレータが内部的に存在することです。そうすれば、内部反復子 ( を使用して取得できますreverse_iterator::base()) は、常にコンテナー内またはコンテナーの末尾を指します。したがって、常に有効です。逆方向イテレータを逆参照するときは、単純にベースをデクリメントし (双方向イテレータがある場合に実行できます)、それを逆参照します。

要件の一部であると述べているため、インターフェイスに動作中の双方向イテレータがあると想定します。だから、pwdictIteratorPrev()機能があると仮定します。また、リバース イテレータ機能にはプライベート イテレータを一時的に操作する必要があるため、イテレータをコピーする機能やイテレータを比較する機能など、さらにいくつかの機能があると思います。

したがって、これらの機能は (パブリック インターフェイスであろうとなかろうと) 利用可能である必要があります。おそらく簡単に書くことができると思います：

int pwdictIteratorIsEqual(PWDictIterator* it1, PWDictIterator* it2);
PWError pwdictIteratorCopy(PWDictIterator* dst, PWDictIterator const* src);
PWError pwdictIteratorEnd(PWDictIterator* it);

逆イテレータは次のようになります (エラー処理は示されていません)。

struct PWDictRIterator {
    PWDictIterator* base;
    PwDict* dict;
};

typdef struct PWDictRIterator PWDictRIterator;

PWError pwdictRIteratorCreate(PWDictRIterator **ritRef, PWDict *dict)
{
    PWError err;

    PWDictRIterator* riter = malloc(sizeof(PWDictRIterator));  // or however you want to allocate

    if (riter) {
        riter->dict = dict;
        err = pwdictIteratorCreate( &riter->base, dict);
    }

    return err;
}

PWError pwdictRIteratorBegin(PWDictRIterator *rit)
{
    return pwdictIteratorEnd(rit->base);
}

int pwdictRIteratorIsEnd(PWDictRIterator *rit)
{
    PWDictIterator* begin;

    PWError err;
    err = pwdictIteratorCreate( &begin, rit->dict);
    err = pwdictIteratorBegin(&begin);

    // there needs to be some way to do the following somehow - 
    //  I assume a plain old pointer compare won't do the trick
    int is_end = pwdictIteratorIsEqual( rit->base, begin);

    pwdictIteratorDestroy(begin);

    return is_end;
}


const char* pwdictRIteratorGetKey(onst PWDictRIterator *rit)
{
    // remember - to 'derefernce' a reverse iterator, we have to
    //  decrement the base first

    PWDictIterator* tmp;

    // all error handling elided...
    PWError err;
    err = pwdictIteratorCreate( &tmp, rit->dict);

    // we need a temporary iterator, so the base can stay the same
    //  I assume that some sort of copy operation can be created
    //  for iterators - it might not need to be part of the public interface
    err = pwdictIteratorCopy(tmp,rit->base);   

    err = pwdictIteratorPrev(tmp);

    const char* result = pwdictIteratorGetKey(tmp);

    pwdictIteratorDestroy(tmp);

    return result;
}


PWError pwdictRIteratorNext(PWDictRIterator *rit)
{
    return pwdictIteratorPrev(rit->base);
}

PWError pwdictRIteratorPrev(PWDictRIterator *rit)
{
    return pwdictIteratorNext(rit->base);
}

// further functions are basically variations on the above theme...
于 2012-07-14T00:06:35.257 に答える
1

C++ でどこでも使用される反復子パターンとの一貫性のために、rbegin() は最後の要素 (end() の前の要素) を指す反復子を作成し、rend() は要素の前の要素を指す反復子を作成する必要があります。開始 (begin() の 1 つ前)。

これにより、ループの典型的な反復子と同じロジックを使用できます。

for ([iterator type] i = something.rbegin(); i != rend(); ++i)

あなたの質問はあまり明確ではありませんでした。少し整理して考えてみてください。あなたが尋ねた質問に私が答えたかどうかさえ確信が持てない

于 2012-07-13T21:26:12.807 に答える