STL如何实现与非线性数据结构的反向迭代器解引用？

Question

指针的使用没有指针的字面含义。对下一段持保留态度。

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

另外，在没有找到键的情况下，-ed()方法应该返回一个“OneAfterTheLast”检查迭代器，或者我的-ed方法是否应该同时检查两个标志(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

std::reverse_iterator通过持有一个普通的迭代器来实现，但(从概念上讲)在取消引用时返回*(i-1)。您可以执行相同的操作-或者直接使用std::reverse_iterator。

Answer 3

为了与C++中到处使用的迭代器模式保持一致，rbegin()应该创建一个指向最后一个元素(end()之前的元素)的迭代器，而rend()应该创建一个指向开始之前的元素(begin()之前的一个)的迭代器。

这允许您使用与典型迭代器for循环相同的逻辑：

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

你的问题不是很清楚。考虑把它整理一下。我甚至不确定我是否回答了你的问题