你如何在一个排序的向量中插入值?

问题描述

所有，

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

This question is a continuation of this one. I think that STL misses this functionality, but it just my IMHO.

现在，问题来了.

考虑以下代码:

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 方法.

At any given moment of time the vector can be re-sorted. The class also have the getter methods which are used in the sorter structure.

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

What would be the most efficient way to insert a new element in the vector?

我的情况是:

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

I have a grid (spreadsheet), that uses the sorted vector of a class. At any given time the vector can be re-sorted and the grid will display the sorted data accordingly.

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

Now I will need to insert a new element in the vector/grid. I can insert, then re-sort and then re-display the whole grid, but this is very inefficient especially for the big grid.

任何帮助将不胜感激.

推荐答案

问题的简单回答:

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 上的严格排序谓词.

Where Pred is a strictly-ordered predicate on type T.

为了使其工作，输入向量必须已经在这个谓词上排序.

For this to work the input vector must already be sorted on this predicate.

这样做的复杂性是 O(log N) 对于 upper_bound 搜索(找到插入的位置)但高达 O(N) 用于插入本身.