我可以让 std::list 按顺序插入新元素吗？还是必须使用 std::sort？

Question

如果我想使用 std::list 并且插入到列表中的新元素将插入到与比较功能相关的正确位置 - 我可以这样做吗？或者我必须在每次插入后使用 std::sort ？

原文由 nadavgam 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以使用：

• std::set 如果你的元素是不可变的
• std::map 如果你的元素有不可变的键，但应该有可变的值
• std::list 并查找插入位置

带有 std::lower_bound 的 std::list：

 #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::vector 并在之后对其进行排序（注意：std::sort 不能对 std::list::iterator 进行操作，它们不提供随机访问）：

 #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²)。

原文由 user2249683 发布，翻译遵循 CC BY-SA 4.0 许可协议