1

在没有指针字面意义的情况下使用指向。用一粒盐来看待下一段。

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

此外，在找不到密钥的情况下，find() 方法应该返回一个“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);
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)。

这种映射是由以下事实决定的：虽然数组末尾总是有一个指针，但数组开头之前可能没有有效指针。

（第二句从 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() 之前的一个）。

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

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

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

于 2012-07-13T21:26:12.807 回答