如何將元素添加到排序列表...？ （C++）

Question

我剛剛與std :: vector第一次接觸，現在我想改變使用普通C風格數組的壞習慣。我發現std :: list是在排序時使用的容器。但是，我不是100％如何完成以下操作：

我正在做一些計算，其結果取決於兩個指​​數（我和j）。最後，我只對100個最小的結果感興趣（不一定是100，但肯定比我的計算值總數小得多，在下面的代碼中是m * n）。

const int L = 100; 
int i_list[L]; 
int j_list[L]; 
double value_list[L]; 

for (int i=0;i<m;i++){ 
    for (int j=0;j<n;j++){ 
     double x = doSomeCalculations(i,j); 
     insertTheValueAndIndices(i,j,x,i_list,j_list,value_list); 
    } 
} 

完成後，value_list應該包含100個最小值（遞增順序）和i_list/j_list對應的索引。我有一個「insertValuesAndIndices（）」的工作版本，但我使用普通數組和插入新值的最低效方式。在寫我意識到，我其實有兩個不同的問題：

1. 計算值（m * n個）的數量遠遠大於我想保留在列表中，因此只需保持所有值的數量和最終只進行一次排序並不是真正的選擇。另一方面，我只需要在最後以正確的順序得到結果，所以也許有一種方法只對列表進行一次排序。這種分類有什麼「標準」的巧妙和有效的方法嗎？

2. 即使我可以存儲所有結果並在之後進行排序，我不知道如何使用std :: list.sort（）以正確的順序獲取索引數組。我腦海中想到的是定義一些包含結果和兩個索引的類，將這些元素放在一個列表中，然後使用比較器來檢查只有值才能進行排序。但是，也許有更直接的方法來做同樣的事情？

乾杯&預先感謝

Answer 1

感謝您的意見。由於我的文章沒有陳述一個明確定義的問題，但它更證明了我對如何解決問題的無知;），我想發佈我的結論和一個工作示例...

首先，謝謝澄清，「std :: list是排序時使用的容器」 是不正確的。正如指出的那樣通過詹姆斯Kanze，std :: vector也完成這項工作。其次，如果我只是在正確的位置「插入」新值，我實際上不必「排序」矢量。此外，還有對我如何獲得指數也進行排序的想法沒有異議，這裏是我的解決方案：

#include <cfloat> 
#include <algorithm> 
#include <vector> 
#include <iostream> 
#include <iterator> 

struct MyValue{ 
    MyValue(double v,int f,int s):value(v),first(f),second(s){} 
    double value; 
    int first; 
    int second; 
}; 
bool compareValues(const MyValue a,const MyValue b){return a.value < b.value;} 
void insertMyValue(std::vector<MyValue>* v,MyValue x,int maxSize){ 
    v->insert(std::lower_bound(v->begin(),v->end(),x,compareValues),x); 
    if (v->size()>maxSize){v->erase(v->end()-1);} 
} 
void main(){ 
    const int imax = 10; 
    const int jmax = 10; 
    const int Nmax = 30; 
    std::vector<MyValue> results; 
    results.reserve(Nmax+1); 
    // Fill the vector 
    for (int i=0;i<imax;i++){ 
     for (int j=0;j<jmax;j++){ 
      double result = i*(j+0.1); 
      insertMyValue(&results,MyValue(result,i,j),Nmax); 
     } 
    } 
    // Print it 
    for (std::vector<MyValue>::iterator it = results.begin();it<results.end();it++){ 
     cout << (*it).first << " " << (*it).second << " " << (*it).value << endl; 
    } 
} 

Answer 2

首先，你可能不希望std::list，但std::vector。 然後使用std::lower_bound來找到插入的位置，並且如果 生成的向量包含的元素數多於 ，那麼您有興趣使用std::vector<>::pop_back來除掉 多出的一個。

Answer 3

排序是一個壞主意。

取而代之的是使用std::vector<int> buffer(count);來存儲std::make_heap。

然後做：

template<class T> 
void add_element(std::vector<T>& heap, T element, size_t size) { 
    heap.push_back(element); 
    std::push_heap(heap.begin(), heap.end()); 
    while (heap.size() > size) { 
    std::pop_heap(heap.begin(), heap.end()); 
    heap.pop_back(); 
    } 
} 

，這需要在堆的一個vector形式（空vector是堆），並增加了一個元件，然後彈出比堆限制更多的任何元件。

這將適用於任何T具有operator<。還有自定義比較器版本push_heap和pop_heap。