我可以讓std :: list按順序插入新元素嗎？或者必須使用std :: sort？

Question

如果我想使用std::list並且插入到列表中的新元素將被插入到與比較函數相關的正確位置 - 我可以這樣做嗎？ 或者我必須在每次插入後使用std :: sort？

Answer 1

你有三個選擇：

1. 排序每次插入後
2. 找到合適的索引和索引
3. 使用std::set（推薦）

例爲第三個選項，在插入：

#include <iostream> 
#include <set> 

int main() 
{ 
    int myints[] = {75,23,65,42,13}; 
    std::set<int> myset (myints,myints+5); 

    std::cout << "myset contains:"; 
    for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it) 
    std::cout << ' ' << *it; 

    std::cout << '\n'; 

    return 0; 
} 

輸出：

MYSET包含：13 23 42 65 75

Answer 2

您可以使用：

• 的std ::如果你的元素不變
• 的std ::地圖設置如果您的元素具有不可變的密鑰，但應具有可變值
• std :: list並查找插入位置

的std ::名單與標準:: LOWER_BOUND：

#include <algorithm> 
#include <list> 
#include <iostream> 

    int main() 
    { 
     std::list<int> list; 
     int values[] = { 7, 2, 5,3, 1, 6, 4}; 
     for(auto i : values) 
      list.insert(std::lower_bound(list.begin(), list.end(), i), i); 
     for(auto i : list) 
      std::cout << i; 
     std::cout << '\n'; 
    } 

另外，您可以填充一個整個的std ::向量，之後對其進行排序（注：性病::排序不能性病操作::目錄::迭代器，它們不提供隨機訪問）：

#include <algorithm> 
#include <vector> 
#include <iostream> 

int main() 
{ 
    std::vector<int> vector = { 7, 2, 5,3, 1, 6, 4}; 
    std::sort(vector.begin(), vector.end()); 
    for(auto i : vector) 
     std::cout << i; 
    std::cout << '\n'; 
} 

注：與插入位置的手工查找列表的表現是最差的O（N²）。

Answer 3

是的，你可以。嘗試如下所示，只需更改比較功能和類型（如果需要）。

#include <list> 

inline 
int compare(int& a, int&b) { 
    return a - b; 
} 

template<typename T> 
void insert_in_order(std::list<T>& my_list, T element, int (*compare)(T& a, T&b)) { 
    auto begin = my_list.begin(); 
    auto end = my_list.end(); 
    while ((begin != end) && 
     (compare(*begin,element) < 0)  ) { 
     ++begin; 
    } 
    my_list.insert(begin, element); 
} 

int main() { 
    std::list<int> my_list = { 5,3,2,1 }; 
    my_list.sort();        //list == { 1,2,3,5} 
    insert_in_order<int>(my_list, 4, &compare); //list == {1,2,3,4,5} 
}