Iterator over std::unordered_map<int, std::vector<Element>>

Question

I have a class storing some data in unordered_map. Let us assume that the class looks as follows:

class Container {
    std::unordered_map<int, std::vector<Element>> map;
};

And for convenience, I would like to iterate over the contents of my Container using range-for-loop, so that I would get all the Elements in nested vectors.

for (const Element& e : Container(...)) {
    magic(e);
}

To do this I need to implement iterator, that would iterate over the elements of nested vectors. I tried to do it myself, but ended up with such a malfunctioning monstrosity, that I don't even dare to put it here. I just provide a link to the code I wrote, but it's just terrible and it doesn't work properly because I was unable to implement end correctly.

So my question is, can it be done in some elegant manner? Or at least correctly? Any help is much appreciated.

Answer 1

There is a trick I learned a long time ago to convert a normal function into a kind of generator (or coroutine, or whatever it is called these days).

Imagine that C++ had the yield keyword, like Python or C#. Then doing the iteration would be simple:

void shift()
{
    for (auto mapIt = bag->begin(); mapIt != bat->end(); ++mapIt)
    {   
        for (auto vecIt = mapIt->second.begin(); vecIt != mapIt->second.end(); ++vecIt)
        {   
            yield *vecIt; //Alas, C++ cannot yield!
        }
    }
}

The transformation to a proper C++ function can be done semi-automatically, following these easy steps:

1-Move all local variables to the top of the function:

void shift()
{
    mapIt_t mapIt; //assume the proper typedefs somewhere
    vecIt_t vecIt;

    for (mapIt = bag->begin(); mapIt != bat->end(); ++mapIt)
    {   
        for (vecIt = mapIt->second.begin(); vecIt != mapIt->second.end(); ++vecIt)
        {   
            yield *vecIt; //Alas, C++ cannot yield!
        }
    }
}

2-Transform the local variables into member variables. Add a int m_state; member variable, initialized to 0.

mapIt_t m_mapIt;
vecIt_t m_vecIt;
int m_state = 0;
void shift()
{

    for (m_mapIt = bag->begin(); m_mapIt != bat->end(); ++m_mapIt)
    {   
        for (m_vecIt = m_mapIt->second.begin(); m_vecIt != m_mapIt->second.end(); ++m_vecIt)
        {   
            yield *m_vecIt; //Alas, C++ cannot yield!
        }
    }
}

3-Wrap the function in a switch (m_state) statement. Put a case 0: at the beginning:

mapIt_t m_mapIt;
vecIt_t m_vecIt;
int m_state = 0;
void shift()
{switch (m_state) { case 0: //behold my fancy indentation!

    for (m_mapIt = bag->begin(); m_mapIt != bat->end(); ++m_mapIt)
    {   
        for (m_vecIt = m_mapIt->second.begin(); m_vecIt != m_mapIt->second.end(); ++m_vecIt)
        {   
            yield *m_vecIt; //Alas, C++ cannot yield!
        }
    }

}}

4-Replace each yield with the following statements: m_state = N; return; case N:;, being N a different integer for each place used. Add m_state = -1; return; case -1:; at the end of the function. Use a macro if you feel it is worth it.

mapIt_t m_mapIt;
vecIt_t m_vecIt;
int m_state = 0;
void shift()
{switch (m_state) { case 0: //behold my fancy indentation!

    for (m_mapIt = bag->begin(); m_mapIt != bat->end(); ++m_mapIt)
    {   
        for (m_vecIt = m_mapIt->second.begin(); m_vecIt != m_mapIt->second.end(); ++m_vecIt)
        {   
            m_state = 1; return; case 1:;
        }
    }
    m_state = -1; return; case -1:;
}}

5-Done! You can make the container as complex as you want: if you can write a function that does the full iteration, you will be able to convert it into an iterator class.

---

With all that in mind I have written the following sample code, that seems to work fine.

class Bag
{
public:
    typedef std::unordered_map<int, std::vector<std::string> > container_t;
    container_t cnt;
};

class BagIterator : public std::iterator<std::forward_iterator_tag, std::string>
{
public:
    friend BagIterator begin(const Bag &bag);
    friend BagIterator end(const Bag &bag);

    BagIterator()
    {
        m_bag = NULL;
        m_state = -1;
    }

    const value_type &operator*() const
    {
        return *m_vecIt;
    }
    BagIterator &operator++()
    {
        shift();
        return *this;
    }
    BagIterator operator++(int)
    {
        BagIterator tmp = *this;
        operator++();
        return tmp;
    }
    bool operator==(const BagIterator &r) const
    {
        if (m_state != r.m_state)
            return false;
        if (m_state == -1)
            return true;
        return m_bag == r.m_bag && m_mapIt == r.m_mapIt && m_vecIt == r.m_vecIt;
    }
    bool operator!=(const BagIterator &r) const
    {
        return !operator==(r);
    }
private:
    typedef Bag::container_t::const_iterator mapIt_t;
    typedef std::vector<std::string>::const_iterator vecIt_t;
    const Bag *m_bag;
    mapIt_t m_mapIt;
    vecIt_t m_vecIt;
    int m_state;

    void shift()
    {switch (m_state) { case 0:
        for (m_mapIt = m_bag->cnt.begin(); m_mapIt != m_bag->cnt.end(); ++m_mapIt)
        {
            for (m_vecIt = m_mapIt->second.begin(); m_vecIt != m_mapIt->second.end(); ++m_vecIt)
            {
                m_state = 1; return; case 1:;
            }
        }
        m_state = -1; return; case -1:;
    }}
};

BagIterator begin(const Bag &bag)
{
    BagIterator res;
    res.m_bag = &bag;
    res.m_state = 0;
    res.shift();
    return res;
}
BagIterator end(const Bag &bag)
{
    BagIterator res;
    res.m_bag = &bag;
    return res;
}

A few comments:

• Note how I derived the custom iterator from std::iterator so that the standard library will know how it works.
• Note also how I implemented the operator==(). First it checks that the state is the same, then if both are end() (m_state==-1), and finally if both point to the same element.