如何实现等价范围“迭代器”

Question

如何实现通用的(适用于multimap、排序向量等)相等范围迭代器？我的意思是一个由一对迭代器(begin和end表示特定equal_range的起始位置和结束位置)组成的迭代器。

这样做的动机是我有一个名为sortedword2word的multimap，我使用它来在一个字符串数组中检测变位词。因此，我希望有一种简单地遍历每个等值范围的方法(易于通过代码行数/可读性 - 我知道我可以通过手动检查.end()以及下一个是否与当前相同来轻松实现...)。

如果Boost已经实现了这样的功能，那也可以接受。

- NoSenseEtAl

---

你真的需要那个吗？使用 lower_bound/upper_bound 可以获得一个指向范围开头的迭代器。然后只需在 while(*current == *next) 迭代即可... - jrok

我错过了那部分，抱歉。那么，为了节省1或2行代码，你能处理多少样板文件呢？ :) - jrok

@jrok，这不是关于那个的问题...使用std::swap而不是第三个tmp变量可以节省多少并不重要，重要的是可读性...对于(auto it = something.begin(), something.end())，比while ... if ...更清晰。我会更新我的答案。 - NoSenseEtAl

什么是等值范围迭代器？equal_range(v.begin(), v.end(), value)它如何成为一个迭代器？你是指value++吗？或者你的向量没有排序，因此可能存在多个相等的范围？ - kwjsksai

@Mehrdad 我知道...但谢谢你说得这么好，如果有其他人看到可能会感到困惑... :) - NoSenseEtAl

Answer 1

也许像这样：

可能是这样：

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

使用方法：

auto r = er(v.begin(), v.end()), e = r.make_end();

while (r != e)
{
    for (auto x : r) { /* ... */ }
    ++r;
}

- Kerrek SB

Answer 2

编写自定义迭代器可能很麻烦（如果您要严格满足例如ForwardIterator概念的所有要求）。以下内容是否足够？

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

- Timothy Shields

Answer 3

我会这样做（希望我详细理解了问题...）：

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

假设您可以使用C++11，但仍然可以轻松修改以匹配旧的C++规范。

jav

(无需翻译)

- jav974

---

假设我有一个multimap，其中包括a->1、a->2、a->3、b->4和b->3等元素……我想要迭代两个相等范围：从a->1到a->3和从b->4到b->3。 - NoSenseEtAl

所以你所谓的范围是一些元素，你想要迭代它们，但它们并不严格对应于彼此的索引，对吗？ - jav974

@NoSenseEtAl：那么，为什么不适用std::equal_range呢？ - rodrigo

当您在“等范围迭代器”上执行++时，您将获得一个新的迭代器，它是下一个等范围的开始和结束...也就是说，在示例中我会使用|来分割相等的范围：(1,3) (1,4) | (2,3)| (3,10) (3,22)。 - NoSenseEtAl

所以在这个例子中，迭代器可以有3个值：(1,3)-(1,4)、(2,3)-(2-3)、(3,10)-(3,22)，还可能有(range_end)-(range_end)。 - NoSenseEtAl