没有 LegacyRandomAccessIterator 的迭代器范围的平衡分区

Question

让我们从一个简单的例子开始：

std::vector<int> foo;
... // fill it
auto begin = foo.begin();
auto end = foo.end();
auto middle = begin + std::distance(begin, end) / 2;

如果迭代器具有LegacyRandomAccessIterator特征，迭代器范围的理想双分区是非常容易的，因此任何形式的分而治之类型的算法也是如此。这种模式在 STL 实现中也很常见。

如果他们只提供LegacyForwardIteratortrait，那么我们在恒定时间内唯一能做的就是：

std::set<int> foo;
... // fill it
auto begin = foo.begin();
auto end = foo.end();
auto middle = (begin != end) ? ++(begin) : begin;

如果没有线性扫描，就没有机会以远程平衡的方式处理迭代器范围。

很容易理解，对于大多数不提供 的容器LegacyRandomAccessIterator，理想的分区方案不可能是免费的。但是，大多数容器仍然能够以1:n-1恒定成本提供比平均更好的分区方案。

任何基于自平衡树的容器都能够根据内在的实现细节保证最坏情况的比率。任何哈希表——无论是基于桶还是基于多轮——仍然有很高的机会提供一个好的分区，只需将哈希表本身切成两半。

只有不平衡的树或普通列表在设计上是不合适的。

这种不足也显示在 STL 内部算法中，这取决于某种平衡的划分，例如std::for_each(std::execution::par_unseq, ...). 尽管几乎所有实现中的大多数 STL 容器都有实现细节，允许将恒定时间划分为远程平衡块，但我还没有看到任何 STL 实现处理任何东西，除了LegacyRandomAccessIterator比纯单元素循环更好。通常会导致缓存行的错误共享，以及远远超出任何实际价值的同步开销。

这就引出了一个问题，为什么 C++ 语言没有提供接口来为任何 STL 容器请求更好的分区方案？或者有没有我不知道的？

Answer 1

虽然这个问题在真空中是有意义的，但我找不到一个重要的容器。

1. 所有关联容器都已经进行了固有排序，并且已经提供了专门的访问器和 API。

2. 我们可以忽略提供随机访问的序列容器，因为我们不关心它们。

3. 只剩下std::list和std::forward_list。两者都没有提供平衡划分所需的布局。

因此，没有留下出现此问题的容器，至少在标准库中没有。除非，也许您正在谈论使用例如。std::lower_bound与例如。a std::map（也许出于某种通用目的）？

std::for_each(std::execution::par_unseq, ...)关于以下工作的案例std::set：

这是特殊情况。即使在这种情况下也有选择，并且在性能上存在权衡（请记住，实现std::set是严格私有的- 不能保证它是用 RB 树实现的，因此不一定知道中位数/精确划分）。我猜，如果没有精确的划分，对于许多处理用例来说，情况可能会更糟。因此，您的案例/需求对于标准库来说过于专业化，您可能应该只实现一个专门的for_each来处理您的实际需求。或者尝试使用排序 std::vector（无论是保持排序还是在需要时排序都会影响或破坏性能），即。如果中间没有太多插入并且需要对其进行排序 - 您std::deque也可以尝试一下。

话虽这么说，这个想法将来可能会被添加到新的迭代器概念中，但我想到目前为止还没有人真正考虑过它。