C++std::Below_Bound()函数,用于查找索引排序向量的插入点 [英] C++ std::lower_bound() function to find insertion point for an index-sorted vector

查看:0
本文介绍了C++std::Below_Bound()函数,用于查找索引排序向量的插入点的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

假设我有vector<Foo>,它的索引在vector<int>中通过类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中插入一些内容,并在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,那么二分搜索算法如何知道int b指的是.bar而不是.other

我还想知道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::Below_Bound()函数,用于查找索引排序向量的插入点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆