c++ - 用于有序迭代、有序推送和移除的排序数据结构(仅从顶部开始的 N 个元素)

Question

什么被认为是按顺序推送某些东西的最佳数据结构(因此在任何位置插入，能够找到正确的位置)，按顺序迭代，并从顶部弹出 N 个元素(因此 N 个最小的元素，N 确定通过与阈值比较)？推送和弹出需要特别快(运行循环的每次迭代)，而数据的有序完整迭代以可变速率发生，但可能要少一个数量级。数据不能被完全迭代清除，它需要保持不变。被压入的所有东西最终都会被弹出，但是由于弹出可以删除多个元素，所以压入的次数可能比弹出的次数多。结构中的数据规模在任何时候都可能达到数百或数千个元素。

我目前正在使用 std::deque 和二进制搜索按升序插入元素。分析显示它占用了大部分时间，因此必须做出一些改变。 std::priority_queue 不允许迭代，我见过的 hacks 不会按顺序迭代。即使在有限的测试中(没有完整的迭代!)，std::set 类的性能也比我的 std::deque 方法差。

我遇到的所有类似乎都不是根据这个用例构建的。如果出于某种原因在 STL 或 boost 中找不到数据结构，我不反对创建自己的类。

编辑:

目前主要有两个功能，push 和prune。 push 使用了 65% 的时间，prune 使用了 32%。 push 中使用的大部分时间是由于插入 deque(65% 中的 64%)。只有 1% 来自二分查找位置。

template<typename T, size_t Axes>
void Splitter<T, Axes>::SortedData::push(const Data& data) //65% of processing
{
 size_t index = find(data.values[(axis * 2) + 1]);

 this->data.insert(this->data.begin() + index, data); //64% of all processing happens here
}

template<typename T, size_t Axes>
void Splitter<T, Axes>::SortedData::prune(T value) //32% of processing
{
 auto top = data.begin(), end = data.end(), it = top;

 for (; it != end; ++it)
 {
  Data& data = *it;

  if (data.values[(axis * 2) + 1] > value) break;
 }

 data.erase(top, it);
}

template<typename T, size_t Axes>
size_t Splitter<T, Axes>::SortedData::find(T value)
{
 size_t start = 0;
 size_t end = this->data.size();

 if (!end) return 0;

 size_t diff;

 while (diff = (end - start) >> 1)
 {
  size_t mid = diff + start;

  if (this->data[mid].values[(axis * 2) + 1] <= value)
  {
   start = mid;
  }
  else
  {
   end = mid;
  }
 }

 return this->data[start].values[(axis * 2) + 1] <= value ? end : start;
}

Answer 1

根据您的要求，根据您的需要量身定制的混合数据结构可能会表现最佳。正如其他人所说，连续内存非常重要，但我不建议始终保持数组排序。我建议您使用 3 个缓冲区(1 个 std::array 和 2 个 std::vector):

• 1(常量大小)“插入堆”的缓冲区。需要放入缓存。
• 2 个(可变大小)缓冲区 (A+B)，用于维护和更新排序数组。

当你压入一个元素时，你通过 std::push_heap 将它添加到插入堆。由于插入堆大小不变，它可能会溢出。当发生这种情况时，您std::sort 它向后 和std::merge 它与已经排序的序列缓冲区 (A) 到第三 (B)，根据需要调整它们的大小。这将是新的排序缓冲区，旧的缓冲区可以被丢弃，即你为下一个批量操作交换 A 和 B。当您需要排序序列进行迭代时，您也可以这样做。当你删除元素时，你将堆中的顶部元素与排序序列中的最后一个元素进行比较并将其删除(这就是为什么你向后排序，这样你就可以 pop_back 而不是 pop_front).

作为引用，这个想法大致基于 sequence heaps .