插入大部分已排序数据并保持排序顺序的数据结构

Question

名称已经说明了一切，但是为了解释清楚，我有一份带有时间戳的向量列表。它们大部分是按顺序排序的，但会有一些无序值。我想要按顺序输出它们，但是向量将以流的方式出现，我不希望有太大的缓冲区，因为我希望及时输出结果。

所以我想要保持一个“前瞻”列表，其中包含N个向量。当我读入新的向量时，我想将其插入到列表中，然后从列表顶部弹出最旧的向量以输出，以使列表保持恒定的N个向量长。

当我插入列表时，我希望向量被排序并在列表中正确的位置添加，因为我认为这是最有效的方法。

我需要很好的效率，但不希望花费太长时间来实施和测试。因此，我对易于解决方案（例如，如果存在现有的C ++结构，则进行重用）以及更难实现但可以提供显着速度提升的解决方案感兴趣。我更喜欢使用标准C ++，但是如果有一个boost或类似的库可以完全满足我的需求，我会很乐意听取它的建议。

谢谢。

编辑：感谢所有的建议。然而，我忽略了时间戳不是唯一的事实。时间戳只有秒精度，因此很可能会得到多个具有相同时间戳的向量。在这种情况下，我更希望保留它们的顺序，但这并非必要。

- dsollen

---

请查看Boost.MultiIndex。 - ildjarn

你说大部分已排序，但流的末尾可能有最低时间戳的奇怪值 - 如果不是这样，输入提供了什么保证？ - mmmmmm

@Mark，据我所知不会。当向量顺序错乱时，这是由于滞后/延迟问题，因此任何顺序错乱的输入都应该接近其正确位置。 - dsollen

如果值接近它们应该结束的位置，为什么不只是保持一个具有N个元素的链表，并手动保持其排序呢？将每个时间戳插入到其位置应该只需要几个操作。这些集合没有利用您对数据的了解。 - Ivan Vergiliev

Answer 1

请查看 std::multiset 类。

你应该检查它的插入（insert）方法：

#include <set>
#include <functional>

const size_t max_item_number = 100;

struct your_type
{
  std::string str;
  time_t datetime;
};

class your_less : std::binary_function<your_type,your_type,bool>
{
public:
  bool operator()( const your_type &left, const your_type &right ) const
  {
    return ( left.datetime < right.datetime );
  }
};


std::multiset<your_type,your_less> store;
std::multiset<your_type,your_less>::iterator helper = store.begin();

helper = store.insert( helper, new_value );
helper = store.insert( helper, new_value );

// fixed size: remove the oldest value
// you could use it e.g. in loop
if ( store.size() == max_item_number )
{
  store.erase( store.begin() );
  helper = store.begin();
}

如果流已排序，则插入时间可以保持不变。

- Naszta

Answer 2

简单的选择： priority_queue O(lg n) 插入和提取最小值，比 set/multiset 快得多（整数约为3倍），并且占用更少的内存空间

如果输入几乎已经排序好了，那么可以使用某种插入排序的变体。你只需要保持排序好的 deque，将元素插入到后面的某个位置，然后从前面弹出最小值。

- usamec

Answer 3

看一下 std::set 类。

- Asha

Answer 4

如果您要在一个大缓冲区中进行一次大排序，Timsort是非常优秀的。它能够利用部分排序的优势。但是您说您不需要那个。

如果您需要在循环内部保持可管理性而不需要排序，那么最好使用像treap或红黑树这样的东西。

Treaps平均速度很快（我最近在Python下对树数据结构进行了性能比较，在许多不同条件下发现treaps始终是平均速度最快或第二快的 - 另外两个根据工作负载有时比treaps稍快，但不是一直）

据报道，红黑树给出低标准偏差的操作时间（它们与treap相比有点慢，但如果这是实时或交互式应用程序，则红黑树可能更适合其低操作时间变异性）。

- user1277476