STL如何使用非線性數據結構實現反向迭代器解引用？

Question

指針的使用沒有指針的字面含義。拿下一節鹽。

很容易實現一個反向迭代器，使用線性數據結構創建rbegin（）== end（）和rend（）== begin（），因爲您可以將反向訪問映射到元素的前面，迭代器指向（rbegin（）指向end（），但訪問結束（） - 1）。但是在處理樹或者在我的情況下，散列表時，我應該如何處理這個映射？我目前使用「OneAfterTheLast」標誌來標記轉發迭代會話的結束，我正在考慮手動實現反向迭代器邏輯並添加一個「OneBeforeTheFirst」標誌。這是一個很好的設計嗎？另外，find（）方法應該在沒有找到關鍵字的情況下返回一個「OneAfterTheLast」迭代器，或者我的檢查方法是否應該檢查兩個標誌（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); 

Answer 1

從C++ 03標準：

一個反向迭代及其相應的迭代i由身份之間建立的基本關係：&*(reverse_iterator(i)) == &*(i - 1)。

這個映射是由一個事實決定的，儘管總是有一個指針超出數組的末尾，但在數組開始之前可能沒有有效的指針。

（第二句從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... 

Answer 2

對於在C++中到處被使用迭代器模式相合，你rbegin（）應該創建一個指向最後一個元素，你的撕裂（（（）結束前的一個）的迭代器），應該創建一個迭代器，指向元素之前（begin（）之前的元素）。

這允許您使用相同的邏輯作爲一個典型的迭代器循環：

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

你的問題不是很清楚。考慮整理一下。我甚至不確定我是否回答了您提問的問題

Answer 3

std::reverse_iterator通過保持正常的迭代器，但在概念上返回*(i-1)取消引用。你可以做同樣的事情 - 或者直接使用std::reverse_iterator。