c++stliteratorequal-range

How to implement equal range "iterator"


how would one implement generic (aka works for multimap, sorted vector ...) equal range iterator? By this I mean it is an iterator that is a pair of iterators (begin and end of a particular equal_range)

Motivation for this is that I have a multimap that is called sortedword2word , and I use it to detect anagrams in an array of strings. So I would like to have a way to iterate over each equal range easily (easily as in LOC/readability way - I know I can easily do it by manually checking for .end() and if next is the same as current...)

If boost has implemented functionality like this that is acceptable A also.


Solution

  • Maybe like this:

    template <typename Iter> class eqrange
    {
        Iter a, b, e;
    
        void adv()
        {
            e = a;
            while (e != b && *e == *a) { ++e; }
        }
    
    public:
    
        eqrange(Iter x, y) : a(x), b(y) { adv(); }
    
        Iter begin() { return a; }
        Iter end()  { return e; }
    
        eqrange & operator++() { b = e; adv(); }
    
        bool operator==(eqrange const & rhs) const
        {
            return a == rhs.a && b == rhs.b && e == rhs.e;
        }
    
        eqrange make_end() const
        { 
            return eqrange(b, b);
        }
    };
    
    template <typename Iter>
    eqrange<Iter> er(Iter b, Iter e)
    {
        return eqrange<Iter>(b, e);
    }
    

    Usage:

    auto r = er(v.begin(), v.end()), e = r.make_end();
    
    while (r != e)
    {
        for (auto x : r) { /* ... */ }
        ++r;
    }