时间戳

首页 > 解决方案 > 无序映射的迭代器

c++ - 无序映射的迭代器

问题描述

我想知道如何为无序地图创建自己的迭代器。我的地图使用向量，其中每个桶都是一个链表。但是，使用这种设计，我不确定如何迭代链接列表，然后从一个桶迭代到另一个桶。我不一定想要代码，而是想要做什么背后的概念。

标签： c++iterator

解决方案

迭代器实际上只是看起来像一个指针的东西，但它实际上根本不需要像一个指针。它可以是一个完整的类。

在您的情况下，您需要两个迭代器：一个用于存储桶，一个用于每个存储桶的元素。将其包装在一个类中：

struct my_unordered_map_iterator
{
  my_bucket_iterator bucket_iter;
  my_vector_iterator element_iter;
};

每次增加 时element_iter，请对照bucket_iter->end(). 如果您已到达存储桶的末尾，则增加bucket_iter并重置element_iter新存储桶的第一个元素。

然后创建迭代器只需要您正确填充内容：

  • begin()⟶{ bucket_begin(), bucket_begin()->elements.begin() }
  • end()⟶{ bucket_end(), nullptr }

当然，您还必须覆盖迭代器类的所有必要运算符以使迭代器工作：*、->、++、==、!=等。您实现的这些运算符中有多少取决于您的迭代器类。我建议您至少考虑一个双向迭代器，您可以通过前向迭代器和std::reverse_iterator.

推荐阅读