如何在排序的向量中插入值？

Question

所有,

这个问题的延续这一个.我认为STL错过了这个功能,但它只是我的恕我直言.

现在,问题.

考虑以下代码:

class Foo
{
public:
    Foo();
    int paramA, paramB;
    std::string name;
};

struct Sorter
{
    bool operator()(const Foo &foo1, const Foo &foo2) const
    {
         switch( paramSorter )
         {
             case 1:
                 return foo1.paramA < foo2.paramA;
             case 2:
                 return foo1.paramB < foo2.paramB;
             default:
                 return foo1.name < foo2.name;
         }
    }

    int paramSorter;
};

int main()
{
    std::vector<Foo> foo;
    Sorter sorter;
    sorter.paramSorter = 0;
        // fill the vector
    std::sort( foo.begin(), foo.end(), sorter );
}

在任何给定的时刻,矢量都可以重新排序.该类还具有在分类器结构中使用的getter方法.

在向量中插入新元素的最有效方法是什么？

我的情况是:

我有一个网格(电子表格),它使用类的排序向量.在任何给定时间,可以重新排序向量,并且网格将相应地显示排序的数据.

现在我需要在向量/网格中插入一个新元素.我可以插入,然后重新排序然后重新显示整个网格,但这对于大网格来说效率非常低.

任何帮助,将不胜感激.

Answer 1

问题的简单答案:

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

带谓词的版本.

template< typename T, typename Pred >
typename std::vector<T>::iterator
    insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert
        ( 
           std::upper_bound( vec.begin(), vec.end(), item, pred ),
           item 
        );
}

其中Pred是T类型的严格排序谓词.

为此,输入向量必须已经在此谓词上排序.

在这样的复杂O(log N)的upper_bound搜索(找出在哪里插入),但到O(N)了插入本身.

为了更好的复杂性,您可以使用,std::set<T>如果没有任何重复或std::multiset<T>可能有重复.这些将自动为您保留排序顺序,您也可以在这些上指定自己的谓词.

还有其他一些你可以做的更复杂的事情,比如管理a vector和set/ multiset或sorted vector新添加的项目,然后在有足够的项目时将它们合并.任何类型的迭代都需要在两个集合中运行.

使用第二个向量具有保持数据紧凑的优势.在这里你的"新增"的项目vector会比较小,因此,在插入时间将是O(M)在那里M是这个向量的大小,可能会比更可行O(N)每次在大载体插入的.合并将比一次插入一个O(N+M)更好O(NM),所以总共O(N+M) + O(M²)插入M元素然后合并.

您可能也会将插入向量保持在其容量状态,因此当您增长时,您将不会进行任何重新分配,只需移动元素.

Answer 2

如果您需要始终对矢量进行排序,首先您可以考虑使用std::set还是std::multiset不简化代码.

如果你真的需要一个有序向量并且想要快速插入一个元素,但是不想强制执行排序标准以便一直满足,那么你可以先用它std::lower_bound()来找到元素所在的排序范围内的位置在对数时间插入,然后使用insert()成员函数vector在该位置插入元素.

如果性能是一个问题,请考虑基准测试std::list与std::vector.对于小项目,std::vector已知由于较高的缓存命中率而insert()更快,但操作本身在列表上计算速度更快(无需移动元素).

Answer 3

只需注意,您也可以upper_bound根据自己的需要使用.upper_bound将确保与其他条目等同的新条目将出现在序列的末尾,lower_bound以确保在序列的开头出现与其他条目等同的新条目.对于某些实现(可能是可以共享"位置"但不是所有细节的类)可能很有用!)

两者都将向您保证,矢量仍然根据<元素的结果进行排序,尽管插入lower_bound将意味着移动更多元素.

例:

insert 7 @ lower_bound of { 5, 7, 7, 9 } => { 5, *7*, 7, 7, 9 }
insert 7 @ upper_bound of { 5, 7, 7, 9 } => { 5, 7, 7, *7*, 9 }

Answer 4

假设您确实想使用向量，并且排序标准或键不会改变（因此已插入元素的顺序始终保持不变）：将元素插入到末尾，然后将其移动到前面一步时间，直到前一个元素不再更大。

它不能更快​​地完成（关于渐近复杂性或“大 O 表示法”），因为您必须移动所有更大的元素。这就是为什么 STL 不提供这个的原因 - 因为它在向量上效率低下，如果你需要它，你不应该使用它们。

编辑：另一个假设：比较元素并不比移动它们贵多少。看评论。

编辑2：由于我的第一个假设不成立（您想更改排序标准），因此废弃此答案并查看我的另一个答案： https: //stackoverflow.com/a/15843955/1413374