假设我有 vector<Foo>
,其索引在外部排序为 vector<int>
按关键字段 .bar
在类里面Foo
.例如
class Foo {
public:
int bar;
int other;
float f;
Foo(int _b, int _o, float _f): bar(_b), other(_o), f(_f) {}
};
vector<Foo> foos;
vector<int> sortedIndex;
sortedIndex
包含 foos
的排序索引.
现在,我想在 foos
中插入一些内容, 并在 .bar
中保持外部排序(排序键为 sortedIndex
) .例如
foos.push_back(Foo(10,20,30.0));
sortedIndex.insert(
lower_bound(sortedIndex.begin(),
sortedIndex.end(),
10 /* this 10 won't work*/,
some_compare_function
),
1,
foos.size()-1
);
显然,数字 10 不起作用: vector sortedIndex
包含索引,而不是值,some_compare_function
会感到困惑,因为它不知道何时使用直接值,以及何时在比较之前将索引转换为值( foo[i].bar
而不仅仅是 i
)。
有什么想法吗?我已经看到了 this question 的答案.答案表明我可以使用比较函数 bool comp(foo a, int b)
.但是,二分查找算法怎么知道int b
呢?指.bar
不是.other
,因为两者都定义为 int
?
我还想知道 C++03 和 C++11 的答案是否不同。请标记你的答案 C++03/C++11。谢谢。
最佳答案
some_compare_function
不会被“混淆”。它的第一个参数始终是 sortedIndex
的一个元素,第二个参数是要比较的值,在您的示例中是 10
。所以在 C++11 中你可以这样实现它:
sortedIndex.insert(
lower_bound(sortedIndex.begin(),
sortedIndex.end(),
10,
[&foos](int idx, int bar) {
return foos[idx].bar < bar;
}
),
foos.size()-1
);
关于C++ std::lower_bound() 函数查找索引排序 vector 的插入点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29207824/