將列表中的元素按升序存儲

目標是，我有多個可用元素列表，並且我希望能夠以有序方式將所有這些元素存儲到結果列表中。將列表中的元素按升序存儲

我想到的一些想法是 a）將結果保存爲一個集合（std :: set），但B樹需要不時重新平衡。 b）將所有元素存儲在列表中，並在最後對列表進行排序。

但是，我想，爲什麼不把它們以分類的方式存儲，因爲當我們將項目添加到結果列表。

這是我的功能，它以保持排序的方式完成結果。有沒有一種有效的方法來做同樣的事情？

void findItemToInsertAt(std::list<int>& dataSet, int itemToInsert, std::list<int>::iterator& location) 
{ 
    std::list<int>::iterator fromBegin = dataSet.begin(); 
    std::list<int>::iterator fromEnd = dataSet.end() ; 
    // Have two pointers namely end and begin 
    if (!dataSet.empty()) 
     --fromEnd; 

    // Set the location to the beginning, so that if the dataset is empty, it can return the appropriate value 
    location = fromBegin; 
    while (fromBegin != dataSet.end() ) 
    { 
     // If the left pointer points to lesser value, move to the next element 
     if (*fromBegin < itemToInsert) 
     { 
      ++fromBegin; 
      // If the end is greater than the item to be inserted then move to the previous element 
      if (*fromEnd > itemToInsert) 
      { 
       --fromEnd; 
      } 
      else 
      { 
       // We move only if the element to be inserted is greater than the end, so that end points to the 
       // right location 
       if (*fromEnd < itemToInsert) 
       { 
        location = ++fromEnd; 
       } 
       else 
       { 
        location = fromEnd; 
       } 
       break; 
      } 
     } 
     else 
     { 
      location = fromBegin; 
      break; 
     } 
    } 

}

而且，這裏是功能

void storeListToResults(const std::list<int>& dataset, std::list<int>& resultset) 
{ 

    std::list<int>::const_iterator curloc; 
    std::list<int>::iterator insertAt; 

    // For each item in the data set, find the location to be inserted into 
    // and insert the item. 
    for (curloc = dataset.begin(); curloc != dataset.end() ; ++curloc) 
    { 
     // Find the iterator to be inserted at 
     findItemToInsertAt(resultset,*curloc,insertAt); 
     // If we have reached the end, then the element to be inserted is at the end 
     if (insertAt == resultset.end()) 
     { 
      resultset.push_back(*curloc); 
     } 
     else if (*insertAt != *curloc) // If the elements do not exist already, then insert it. 
     { 
      resultset.insert(insertAt,*curloc); 
     } 
    } 
}

來源

2010-08-06 user373215

您的代碼看起來像是在對列表進行線性搜索，以便找到插入項目的位置。雖然std::set確實需要平衡它的樹狀結構（我認爲它是Red-Black Tree）才能保持效率，但它可能比您提出的要高效得多。

來源

2010-08-06 15:15:00 David

我正在寫兩個不同的解決方案，一個使用std :: set，另一個使用list並且適當地插入到列表中。但想知道，是否有比這更快的方式插入到列表中。 – user373215 2010-08-06 15:27:59

@nsivakr不是我能想到的。鏈接列表不能被二進制搜索;數組（或矢量）可以，但插入到它們是其他原因效率低下。把它們放入一個**數組/向量**（不是一個列表），然後對它們進行排序與使用'std :: set'的效率差不多，但是如果你真的關心內存使用開銷，那麼你可能想要選擇排序算法（特別是heapsort或quicksort）而不是樹形結構，這會佔用每個節點的額外內存。 – David 2010-08-06 15:44:15

謝謝大衛。感謝您的詳細解釋。 – user373215 2010-08-06 16:42:16

我的indivual列表進行排序，然後使用STL的list::merge創建結果列表的調用者。然後，如果列表很大，您可以付費將結果傳輸給一個向量。

來源

2010-08-06 15:12:48

但是要使用list :: merge，必須先排序項目。但就我的示例而言，源列表中的項目未排序。 – user373215 2010-08-06 15:26:50

@nsivakr是的，我注意到你評論和編輯答案的時間。 – 2010-08-06 15:29:35

回答提出的問題：

是否有一個有效的方式做？

是的。使用std::set。

來源

2010-08-06 15:24:16 pkh

將列表中的元素按升序存儲

回答

相關問題