如何在排序的向量中插入值？ [英] how do you insert the value in a sorted vector?
问题描述
ALL，
此问题是这一个。
我认为STL错过这个功能，但它只是我的IMHO。
现在，问题。
请考虑以下代码：
class Foo
{
public：
Foo （）;
...........
private：
int paramA，paramB;
std :: string name;
};
int main（）
{
std :: vector< Foo> foo;
分拣机;
sorter.paramSorter = 0;
std :: sort（foo.begin（），foo.end（），sorter）;
}
struct Sorter
{
bool operator（）（const Foo& foo1，const Foo& foo2）
{
switch（paramSorter）
{
case 0：
return foo1.name< foo2.name;
case 1：
return foo1.paramA< foo2.paramB;
case 2：
return foo1。 paramA> foo2.paramB;
}
}
private：
int paramSorter;
}
在任何给定时刻，向量都可以重新排序。
类还有在排序器结构中使用的getter方法。
在向量中插入一个新元素的最有效的方法是什么？
情况我有：
我有一个网格（电子表格），使用类。在任何给定的时间，矢量可以重新排序，网格将相应地显示排序的数据。
现在我需要在矢量/网格中插入一个新的元素。
我可以插入，然后重新排序，然后重新显示整个网格，但这是非常低效的，特别是对于大网格。
任何帮助
问题的简单答案：
template<类型名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
）;
}
带谓词的版本。
typedef<类型名T，类型名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> 这些会自动保留一个排序顺序，您也可以在这些顺序上指定自己的谓词。
有很多其他的事情你可以做得更复杂，例如。管理向量和设置 / multiset / sorted vector 的新添加的项目，然后合并这些在有足够的时候。任何类型的迭代您的集合将需要运行通过这两个集合。
使用第二个向量具有保持数据紧凑的优点。这里，您的新添加的项向量将相对较小，因此插入时间将为 O（M） code> M 是这个向量的大小，可能比在大向量中插入的 O（N）时间。合并将是 O（N + M）这比 O（NM）一个时间，所以总共会插入 M 元素 O（N + M）+ O（M 2）然后合并。
你可能会保持插入向量的容量，因为你成长，你不会做任何重分配，只是移动元素。 p>
ALL,
This question is a continuation of this one. I think that STL misses this functionality, but it just my IMHO.
Now, to the question.
Consider following code:
class Foo
{
public:
Foo();
...........
private:
int paramA, paramB;
std::string name;
};
int main()
{
std::vector<Foo> foo;
Sorter sorter;
sorter.paramSorter = 0;
std::sort( foo.begin(), foo.end(), sorter );
}
struct Sorter
{
bool operator()(const Foo &foo1, const Foo &foo2)
{
switch( paramSorter )
{
case 0:
return foo1.name < foo2.name;
case 1:
return foo1.paramA < foo2.paramB;
case 2:
return foo1. paramA > foo2.paramB;
}
}
private:
int paramSorter;
}
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?
Situation I have is:
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.
Any help would be appreciated.
The simple answer to the question:
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
);
}
Version with a predicate.
typedef< 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
);
}
Where Pred is a strictly-ordered predicate on type T. For this to work the input vector must already be sorted on this predicate.
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.
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.
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.
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屋！
