你如何在一个排序的向量中插入值? [英] how do you insert the value in a sorted vector?
问题描述
所有，
这个问题是这个问题的延续.我认为 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) 用于插入本身.
The complexity of doing this is O(log N) for the upper_bound search (finding where to insert) but up to O(N) for the insert itself.
为了更好的复杂性，您可以使用 std::set 如果不会有任何重复或 std::multiset 如果有可能是重复的.这些将自动为您保留排序顺序，您也可以对这些指定您自己的谓词.
For a better complexity you could use std::set<T> if there are not going to be any duplicates or std::multiset<T> if there may be duplicates. These will retain a sorted order for you automatically and you can specify your own predicate on these too.
您还可以做其他各种更复杂的事情，例如管理一个 vector 和一个 set/multiset/sorted vector 新添加的项目，然后将它们合并足够了.任何类型的遍历您的集合都需要遍历两个集合.
There are various other things you could do which are more complex, e.g. manage a vector and a set / multiset / sorted vector of newly added items then merge these in when there are enough of them. Any kind of iterating through your collection will need to run through both collections.
使用第二个向量的优点是可以保持数据紧凑.这里你的新添加"项目 vector 将相对较小，因此插入时间将是 O(M) 其中 M 是这个的大小vector 并且可能比每次插入大向量的 O(N) 更可行.合并将是 O(N+M) 这比 O(NM) 更好，它会一次插入一个，所以总的来说它是 O(N+M) + O(M²) 插入 M 个元素然后合并.
Using a second vector has the advantage of keeping your data compact. Here your "newly added" items vector will be relatively small so the insertion time will be O(M) where M is the size of this vector and might be more feasible than the O(N) of inserting in the big vector every time. The merge would be O(N+M) which is better than O(NM) it would be inserting one at a time, so in total it would be O(N+M) + O(M²) to insert M elements then merge.
您可能也将插入向量保持在其容量，以便随着您的增长而不会进行任何重新分配，而只是移动元素.
You would probably keep the insertion vector at its capacity too, so as you grow that you will not be doing any reallocations, just moving of elements.
这篇关于你如何在一个排序的向量中插入值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
