如果我想使用std::list
并且插入到列表中的新元素将插入到相对于比较函数的正确位置 - 我可以做到吗?或者我必须在每次插入后使用 std::sort?
您可以使用:
- std::set 如果你的元素是不可变的
- std::map 如果您的元素具有不可变键,但应该具有可变值
- std::列出并查找插入位置
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::迭代器上运行,它们不提供随机访问):
#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²)。
是的,你可以。尝试如下操作,如果需要,只需更改比较功能和类型即可。
#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}
}
您有三个选择:
- 每次插入后排序
- 找到正确的索引并在该索引处插入
- 使用 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