这是我想解决的问题:在 C++ 中，map、multimap 等的迭代器缺少两个理想的功能:(1) 无法在运行时检查它们的有效性，(2) 在那里它们上没有定义operator<，这意味着它们不能用作另一个关联容器中的键。 (我不关心操作符 < 是否与键排序有任何关系；我只希望有一些 < 至少可用于同一映射的迭代器。)
这里有一个可能的解决方案:说服map、multimap等将它们的键/数据对存储在 vector 中，然后让迭代器成为一个小结构，其中包含指向 vector 本身的指针和下标索引。然后可以比较两个迭代器，至少对于同一个容器(通过比较它们的下标索引)，并且可以在运行时测试迭代器是否有效。
这个解决方案可以用标准 C++ 实现吗？特别是，我可以为映射类定义“分配器”以实际将项目放入 vector 中，然后将 Allocator::pointer 类型定义为上一段中描述的小结构吗？映射的迭代器与 Allocator::pointer 类型有何关系？ Allocator::pointer 是否必须是一个实际的指针，或者它可以是任何支持取消引用操作的东西吗？
2013-06-11 更新:我不明白这些回复。如果(键，数据)对存储在 vector 中，那么获取给定下标的项的时间复杂度为 O(1)，仅比直接指针差一点，因此渐近没有变化。为什么响应者说 map 迭代器“没有保留”？该标准规定，只要迭代器引用的项未被删除，迭代器就保持有效。至于“真正的问题”:假设我对符号表使用多重映射(变量名称->存储位置；它是多重映射而不是映射，因为内部作用域中的变量名称可能会隐藏同名的变量)，并且现在说我需要第二个由变量作为键的数据结构。显然最简单的解决方案是使用第一个映射中变量名称的特定实例的迭代器作为第二个映射的键，如果只有迭代器具有运算符<。
最佳答案
我认为不会。
如果您能够以某种方式“说服”map 将其对存储在 vector 中，您将从根本上改变 map 上的某些(至少两个)保证:
insert、erase和find的复杂度不再是对数。insert将不再能够保证不受影响的迭代器的有效性，因为底层vector有时需要重新分配。
退一步来说，有两件事向我表明你正在尝试“解决”错误的问题。
首先，需要一个迭代器 vector 是不寻常的。
其次，需要检查迭代器的有效性是不常见的，因为迭代器通常不会保留。
我想知道您想要解决的真正问题是什么？
关于C++ 映射分配器将项目存储在 vector 中？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17030578/