c++ - STL 如何使用非线性数据结构实现反向迭代器取消引用？

Question

Pointing 的使用没有指针的字面意思。对下一段持保留态度。

很容易实现反向迭代器，使 rbegin() == end() 和 rend() == begin() 具有线性数据结构，因为您可以将反向访问映射到迭代器所在位置之前的元素指向(例如，rbegin() 指向 end()，但访问 end()-1)。但是当处理树或者在我的例子中是哈希表时，我应该如何处理这个映射？我目前正在使用“OneAfterTheLast”标志来标记转发迭代 session 的结束，并且我正在考虑手动实现反向迭代器逻辑并添加一个“OneBeforeTheFirst”标志。这是一个好的设计吗？

此外，如果找不到 key ，find() 方法应该返回一个“OneAfterTheLast”编辑的迭代器，或者我的检查方法是否应该检查两个标志(OneAfterTheEnd 和 OneBeforeTheFirst)？

这是我的公共(public)接口(interface)，仅供引用，仍然没有反向迭代器方法。容器类和迭代器类都是不透明的。

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

std::reverse_iterator 通过持有普通迭代器但(概念上)在取消引用时返回 *(i-1) 来实现。您可以这样做 - 或者直接使用 std::reverse_iterator。