2

这是我想解决的问题：在 C++ 中，map、multimap 等的迭代器缺少两个理想的功能：(1) 无法在运行时检查它们的有效性，以及 (2) 没有运算符< 在它们上定义，这意味着它们不能用作另一个关联容器中的键。（我不在乎 operator< 是否与键排序有任何关系；我只希望有一些 < 至少可用于同一映射的迭代器。）

这是这个问题的一个可能的解决方案：说服 map、multimap 等将它们的键/数据对存储在一个向量中，然后让迭代器成为一个包含指向向量本身的指针和下标索引的小结构。然后可以比较至少对于同一个容器的两个迭代器（通过比较它们的下标索引），并且可以在运行时测试迭代器是否有效。

这个解决方案可以在标准 C++ 中实现吗？特别是，我可以为映射类定义“分配器”以实际将项目放入向量中，然后将分配器::指针类型定义为上一段中描述的小结构吗？映射的迭代器如何与 Allocator::pointer 类型相关？Allocator::pointer 是否必须是一个实际的指针，或者它可以是任何支持取消引用操作的东西？

2013-06-11 更新：我不理解回复。如果 (key,data) 对存储在向量中，那么获得给定下标的项目是 O(1)，仅比直接指针稍差，因此渐近性没有变化。为什么响应者说地图迭代器“没有保留”？该标准规定，只要迭代器引用的项目未被删除，迭代器就保持有效。至于“真正的问题”：假设我对符号表使用多重映射（变量名称->存储位置；它是多重映射而不是映射，因为内部范围内的变量名称可能会影响具有相同名称的变量），并且现在说我需要第二个由变量键入的数据结构。

4

1 回答 1

4

我想不是。

如果您能够以某种方式“说服”map将其对存储在向量中，那么您将从根本上改变某些（至少两个）保证map：

  1. insert，erase并且find不再是对数的复杂性。
  2. insert 将不再能够保证未受影响的迭代器的有效性，因为vector有时需要重新分配底层。

不过，退后一步，有两件事向我表明您正在尝试“解决”错误的问题。

首先，需要一个迭代器向量是不寻常的。

其次，需要检查迭代器的有效性是不常见的，因为迭代器通常不会被保留。

我想知道您要解决的真正问题是什么？

于 2013-06-10T18:50:54.653 回答