我可以使std :: list插入带有顺序的新元素吗？或者必须使用std :: sort？

Question

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

Answer 1

您可以使用:

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

std :: list with 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 :: vector并在之后对其进行排序(注意:std :: sort不能对std :: list :: iterators进行操作,它们不提供随机访问):

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