c++ - 有效地填补有序数字列表中的第一个空白

Question

我正在写一些需要从数字列表开始的东西，这些数字已经按顺序排列但可能有间隙，然后找到第一个间隙，在该间隙中填充一个数字，然后返回它填充的数字。数字是 [0, inf) 范围内的整数。我有这个，而且效果很好:

list<int> TestList = {0, 1, 5, 6, 7};

int NewElement;
if(TestList.size() == 0)
{
    NewElement = 0;
    TestList.push_back(NewElement);
}
else
{
    bool Selected = false;
    int Previous = 0;
    for(auto Current = TestList.begin(); Current != TestList.end(); Current++)
    {
        if(*Current > Previous + 1)
        {
            NewElement = Previous + 1;
            TestList.insert(Current, NewElement);
            Selected = true;
            break;
        }
        Previous = *Current;
    }
    if(!Selected)
    {
        NewElement = Previous + 1;
        TestList.insert(TestList.end(), NewElement);
    }
}

但我担心效率问题，因为我使用等效的代码片段在我编写的类包装器后面的 OpenGL 中分配统一的 block 绑定(bind)位置(但这与问题并不完全相关 :))。有什么提高效率的建议吗？我什至不确定 std::list 是否是它的最佳选择。

Answer 1

一些建议:

• 尝试其他容器并进行比较。链表可能具有良好的理论特性，但连续存储(例如在排序 vector 中)在现实生活中的好处可能是巨大的。

• 由于您的范围已经排序，您可以执行二进制搜索来查找间隙:从中间开始，如果那里的值等于大小的一半，则没有间隙，因此您可以将搜索限制为另一半。冲洗并重复。 (这假设范围内没有重复的数字，鉴于您有“差距”的概念，我认为这是一个合理的限制。)

  这更像是一个理论上的、单独的建议。无法非常有效地实现纯链表上的二分搜索，因此需要一种不同类型的数据结构来利用这种方法。