C++ std::lower_bound() 函数查找索引排序向量的插入点

Question

假设我有 vector<Foo>，它的索引在 vector<int> 中按 class Foo 中的关键字段 .bar 在外部排序。例如

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 中插入一些内容，并在 sortedIndex 中保持外部排序（排序键为 .bar）。例如

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 不起作用：向量 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。谢谢

Answer 1

some_compare_function 不会是 "confused"。它的第一个参数始终是 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() 函数查找索引排序向量的插入点

C++ std::lower_bound() function to find insertion point for an index-sorted vector

c++

sorting

binary-search

c++11

c++03