我可以让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} 
}