How to implement equal range "iterator"

Question

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.

Do you really need that? Using `lower_bound/upper_bound` you can get an iterator to the beginning of the range. Then just iterate `while(*current == *next)`... — jrok, Jun 27 '13 at 09:45
@jrok " So I would like to have a way to iterate over each equal range easily(easily as in LOC way I know I can easily do it by manually checking for .end() and if next is the same as current...)" — NoSenseEtAl, Jun 27 '13 at 09:49
I missed that part, sorry. Well, how much boilerplate can you handle to save 1 or 2 LOC? :) — jrok, Jun 27 '13 at 09:51
@jrok it is not about that.. how much you save using std::swap instead of third tmp var? it is about readability... for (auto it = something.begin(), something.end() is much clearer than while ... if ... Ill update my answer — NoSenseEtAl, Jun 27 '13 at 10:25
What is an equal range iterator? `equal_range (v.begin(), v.end(), value)` how it becomes an iterator? Do you mean `value++`? Or your vector is not ordered so there may be multiple equal ranges? — kwjsksai, Jul 05 '13 at 08:24
I completely agree with you, but just a note regarding `std::swap` -- its purpose is *not* readability (or reducing LOC). In fact, calling `std::swap(a, b)` is precisely the wrong thing to do. You're supposed to day `using std::swap; swap(a, b);` because the whole goal is to allow the class of `a` to define its *own* `swap` function, which could get called *instead* of `std::swap`. `std::swap` is just the "default" case that's meant to handle cheap-to-copy objects; it's not the actual implementation for many classes. — user541686, Jul 08 '13 at 00:32
@Mehrdad I know... but tnx for saying it nicely if somebody else is reading it could be confusing... :) — NoSenseEtAl, Jul 08 '13 at 06:12

score 5 · Accepted Answer · edited Jan 14 '14 at 07:50

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

score 2 · Answer 2 · answered Jul 01 '13 at 16:50

Writing custom iterators can be a pain (if you're going to be rigorous in terms of meeting all the requirements of, say, the ForwardIterator concept).

Will the following suffice?

template <typename Range, typename Func>
void foreach_equal_range(Range& range, Func func)
{
    using std::begin;
    using std::end;
    foreach_equal_range(begin(range), end(range), func);
}

template <typename ForwardIt, typename Func>
void foreach_equal_range(ForwardIt begin, ForwardIt end, Func func)
{
     while (begin != end)
     {
         auto it = std::upper_bound(begin, end, *begin);
         func(begin, it);
         begin = it;
     }
}

score 1 · Answer 3 · answered Jun 27 '13 at 14:02

1

i would do something like this (hopefully i understood the question in detail..) :

template<typename Container, typename Function>
void                  apply(Container& a, const Container& b, Function f)
{
  auto                aItr = a.begin();
  auto                bItr = b.begin();

  for (; aItr != a.end() && bItr != b.end(); ++aItr, ++bItr)
    f(*aItr, *bItr);
}

Assuming you can use C++11, but it is still easilly modifiable to match older C++ norms.

jav

answered Jun 27 '13 at 14:02

jav974

1,022
10
22

lets say i have multimap that is a->1,a->2,a->3,b->4,b->3 ... I want to have iterate over equal_ranges(two of them in this case: from a->1 to a->3 and from b->4 to b-->3 – NoSenseEtAl Jun 27 '13 at 14:14
So what you call range is a number of elements through wich you want to iterate, but which are not strictly corresponding to each-others index, is that right ? – jav974 Jun 27 '13 at 14:30
@NoSenseEtAl: But then, why is it not appropriate `std::equal_range`? – rodrigo Jul 01 '13 at 09:16
when you do ++ on "equal range iterator" you get a new iterator that is begin and end of next equal range... aka ill use | to split equal ranges in example : (1,3) (1,4) | (2,3)| (3,10) (3,22) – NoSenseEtAl Jul 01 '13 at 11:58
so in this example iterator can have 3 values: (1,3)-(1,4) (2,3)-(2-3) (3,10)-(3,22) and maybe (range_end) - (range_end) – NoSenseEtAl Jul 01 '13 at 12:01

How to implement equal range "iterator"

3 Answers3