如何使用lower_bound将值插入到排序向量中

Question

我有一个指向A类的指针向量,我希望使用STL按int键进行排序.为此,我operator <在A类中定义了一个

bool operator< (const A &lhs, const A &rhs){
    return (lhs.key < rhs.key);
};

在我的插入功能看起来像

vector<A*>::iterator it = lower_bound(vec.begin(), vec.end(), element);
vec.insert(it, element);

我期望lower_bound返回可以放置新元素的第一个位置,但它不起作用.插入带有键0,1,2,3的对象将导致向量的顺序不正确(2,3,1,0).这是为什么 ？

也许我也可以使用比较器来实现这个目标:

比较upper_bound/lower_bound的函数

但我的代码出了什么问题？

Answer 1

从您的示例中,您使用的是指针向量:std::vector<A*>.因此,您需要为传入的指针定义比较std::lower_bound:

bool less_A_pointer (const A* lhs, const A* rhs)
{
    return (lhs->key < rhs->key);
}

auto it = std::lower_bound(vec.begin(), vec.end(), element, less_A_pointer);
//...

当然,问题是为什么你首先使用指针 - 只是存储A对象,除非你真的需要.如果您确实需要存储指针,请查看 std::shared_ptr哪个将为您处理:

std::vector<std::shared_ptr<A>> v;
std::shared_ptr<A> element(new A(...));
auto it = std::lower_bound(v.begin(), v.end(), element); //Will work properly

您也可以使用lambda而不必编写自由函数:

auto it = std::lower_bound(v.begin(), v.end(), 
                          [](const A* lhs, const A* rhs)
                          { return lhs->key < rhs->key; });