C++ “滚动”通过 stl::map 中的项目

Question

我创建了一种方法来滚动/环绕项目地图，这样如果到达末尾，该方法将返回第一个项目，反之亦然。

有更简洁的方法吗？

MyMap::const_iterator it = myMap.find(myKey);

if (it == myMap.end())
    return 0;

if (forward) {

    it++;

    if (it == myMap.end()) {
        it = myMap.begin();
    }

} else {

    if (it == myMap.begin()) {
        it = myMap.end();
    }

    it--;

}

Answer 1

您可以将环绕行为直接实现到新的迭代器类中 - 模板化为某些实际迭代器的包装器，为调用者提供更优雅的接口（以便其增量和减量运算符自动执行环绕） 。

另外 - 请小心空容器。当容器中没有元素时，您不想“环绕”。

Answer 2

您可以使用模板来完成此操作。正如之前的海报所述，从它永远不会到达终点的角度来看，这可能很麻烦，因此用户必须以某种方式控制它。我假设你有一个很好的理由，也许会产生一些循环行为。

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

template <class T>
class ScrollIterator
{
public:
    ScrollIterator(T &myCtr, typename T::iterator pos)
        :ctr(myCtr),
         it(pos)
    {

    }

    ScrollIterator operator++()
    {
        if (++it == ctr.end()) { it = ctr.begin(); }
        return *this;
    }

    bool operator!=(const ScrollIterator &rhs) const
    {
        return (this->it != rhs.it);
    }

    bool operator!=(const typename T::const_iterator &rhsIT) const
    {
        return (this->it != rhsIT);
    }

    typename T::value_type operator*() const
    {
        return *it;
    }

private:
    T &ctr;
    typename T::iterator it;
};


int main (int argc, char *argv[])
{
    vector<int> v;
    v.push_back(2);
    v.push_back(3);
    v.push_back(5);
    v.push_back(7);

    int i = 0;
    for (ScrollIterator<vector<int> > it(v,v.begin()); it != v.end() && i < 10; ++i, ++it)
    {
        cout << "Vector = " << i << " Value: " << *it << "\n";
    }

    set<string> s;
    s.insert("c");
    s.insert("a");
    s.insert("b");

    i = 0;
    for (ScrollIterator<set<string> > it(s,s.begin()); it != s.end() && i < 10; ++i, ++it)
    {
        cout << "Set = " << i << " Value: " << *it << "\n";
    }

    map<string, int> y;
    y["z"] = 10;
    y["y"] = 20;
    y["x"] = 30;

    i = 0;
    for (ScrollIterator<map<string, int> > it(y,y.begin()); it != y.end() && i < 10; ++i, ++it)
    {
        cout << "Map = " << i << " Iterator: " << (*it).first << " = " << (*it).second << "\n";
    }

    return 1;
}

Answer 3

您可以使用upper_bound和lower_bound。例如：

if (myMap.empty()) return 0;

MyMap::const_iterator it;

if (forward) {
    it = myMap.upper_bound(myKey);
    if (it == myMap.end()) it = myMap.begin();
} else {
    it = myMap.lower_bound(myKey);
    if (it == myMap.begin()) it = myMap.end();
    --it;
}

如果地图中不存在“myKey”，其行为也会有所不同。它将从钥匙所在的地方开始，而不是走到结束或开始。

Answer 4

您可以实现循环迭代器。

Answer 5

这是一个困难的设计。如果到达“结束”又回到“开始”，那么如何表示一个空容器？环绕思想对无限序列或环进行建模，但没有方法来检测迭代器是否仍然指向有效位置。

这个问题让人想起在不使用“虚拟条目”的情况下写入可变大小的环形缓冲区（例如队列）的尝试：如何区分空环和满环？存储基本位置和大小仅适用于随机访问存储（与链接节点相反），并且与指针或索引对相比不太适合锁定优化。