c++ - 包装 map 迭代器的 map

Question

我有一个主要包装 map<int, map<int, Stuff>> 的 C++ 类，我发现它比 map<pair<int, int>, Stuff> 更有效.但是，我希望迭代器接口(interface)是后一种风格。

例如，我希望能够执行以下操作:

for (const auto& loc_to_stuff : instance) {
  pair<int, int> loc = loc_to_stuff.first;
  int src = loc.first;
  int dst = loc.second;
  ...
}

Answer 1

我不确定 C++ 在这里能为您提供多少帮助:您只需要实现一个迭代器即可。

请记住，迭代器只是一个具有特定成员的类。迭代器是一个带有运算符 * 的类, -> , == , != , 和 ++ ，如果您可以返回和/或进行随机搜索，也许还有更多。

在内部，您的迭代器会将两个迭代器保存到您的 map 中，一个 map<int, map<int, Stuff>>::iterator (“外部”迭代器)和 map<int, Stuff>::iterator (“内部”迭代器)。

++将尝试增加内部迭代器，如果失败，则增加外部迭代器，并在外部迭代器也指向的映射处启动内部迭代器。像这样的东西:

iterator &operator ++ () {
    ++m_inner;
    // if we've reached the end of the inner iterator,
    // find the next non-empty map, and start iterating through it.
    // Stop if we read the end of the outer map.
    // (we're pointing to end() of the whole thing._
    while(m_inner == m_outer->end() && m_outer != m_outer_end) {
        ++m_outer;
        m_inner = m_outer->begin();
    }
}

(该循环用于跳过空 map 。请注意，您在 begin 实现中需要一个类似的循环。)

在您的主类中，您还需要实现 begin , end (const 和非常量)。

一旦您了解迭代器只是普通对象，其他运算符就很简单了。

希望您能明白为什么这可能需要一些代码来处理:您可能会考虑一些关于使用其他 map 类型 (map<pair<int, int>, Stuff>) 的评论建议，这会让您只需要 typedef map<pair<int, int>, Stuff>::iterator iterator .