如果我的容器位于两个现有值之间，是否应该对迭代器类别进行修饰？

Question

我有一个使用自平衡顺序统计树作为其基础存储的绳索容器（每个树节点都包含变量，但通常绳索的元素很多，例如，如果存储字符，则树节点可能会保存〜 4000个元素）。

即使+，+ =，-，-=等操作实际上是对数复杂度（就与当前位置的距离而言），将绳索迭代器分配给std :: random_access_iterator_tag iterator_category是否合理？如果新位置位于当前树节点内（应该比较大的跳转更为频繁），则该操作实际上是随机访问所需的O（1），只有当需要沿着树前进时， O（1）复杂度丢失。但是，在所有情况下，它都比使用双向表示的O（n）好得多。

当然，我可以组成自己的类别标签，但是我需要专门研究各种独立的算法功能，以利用这一优势。

也许这是一个不很适合SO的见解问题，但我仍然很好奇人们对这个问题的看法。

Answer 1

假设您正在使用库中的容器。库的文档声称容器的迭代器满足随机访问迭代器的要求。您的程序存在性能问题，您可以追溯到这些迭代器的增量运算符为O（lg n）而不是O（1）。您抱怨/提交错误报告是否有道理？可能。

您是否想编写别人会抱怨的代码？可能不是。您的里程可能会有所不同，但是低估性能通常要好于高估性能。很少有人抱怨计算速度太快。