問題描述
所有，
這個問題是這個問題的延續.我認為 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(M2) 插入 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(M2) 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.
這篇關于你如何在一個排序的向量中插入值?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！