C++ "Scrolling" through items in an stl::map

Question

I've made a method to scroll/wrap around a map of items, so that if the end is reached, the method returns the first item and vice-versa.

Is there more succinct way of doing this?

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

You could implement the wrap-around behavior directly into a new iterator-class - templated to be a wrapper for some actual iterator, that supplies a more elegant interface to the caller (so that its increment and decrement operators do the wrap-around automatically).

Also - be careful of the empty container. You don't want to "wrap-around" when there are no elements in the container.

Answer 2

You can use *upper_bound* and *lower_bound*. For example:

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;
}

This will also behave differently if "myKey" doesn't exist in the map. It will take up from where the key would have been rather than going to the end or the beginning.

Answer 3

This is a difficult design. If reaching the "end" wraps around to the "beginning", how do you represent an empty container? The wraparound idea models an infinite sequence or a ring, but without a means to detect whether the iterator is still pointing to a valid position.

This problem is reminiscent of attempts to write a variable-sized ring buffer (such as a queue) without using a "dummy entry": How does one distinguish an empty ring from a full ring? Storing a base position and a size is only appropriate for random-access storage (as opposed to linked nodes), and is less amenable to locking optimization than pointer or index pairs.

Answer 4

You can do this with a template. As was stated by a previous poster, this can be cumbersome from the standpoint that it never reaches the end so the user must somehow control this. I'm assuming you have a good reason, perhaps producing some round robin behavior.

#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 5

You could implement a cyclical iterator.