在C++ Vector <custom_class>中搜索值的第一个/最后一个出现

Question

我正在尝试找出最好的方法来搜索"Tracklet"类型的向量(我自己构建的一个类)来查找其变量之一的给定值的第一个和最后一个出现.例如,我有以下类(本例简化):

class Tracklet {
    TimePoint *start;
    TimePoint *end;
    int angle;

    public:
        Tracklet(CvPoint*, CvPoint*, int, int);
}

class TimePoint {
    int x, y, t;

    public:
        TimePoint(int, int, int);
        TimePoint(CvPoint*, int);
        // Relevant getters and setters exist here   
};

我有一个向量" vector<Tracklet> tracklets",我需要搜索结束时间点给定值为"t"的任何tracklet.矢量按结束时间(即tracklet.end->t)排序.

我很乐意编写一个搜索算法,但我不确定采用哪种路由.我不确定二进制搜索是否合适,因为我似乎记得它不一定会找到第一个.我正在考虑一种方法,我使用二进制搜索来找到具有正确时间的元素的索引,然后迭代返回以找到第一个和前进以找到最后一个.我确信有更好的方法,因为它通过迭代浪费二进制搜索O(log n).

希望这是有道理的:我努力解释一下!干杯!

Answer 1

如果向量被排序并包含该值,std::lower_bound将为您提供具有给定值的第一个元素std::upper_bound的迭代器,并将为您提供一个元素的迭代器,该元素超过包含​​该值的最后一个元素.将值与返回的元素进行比较,以查看它是否存在于向量中.这两个函数都使用二进制搜索,因此时间为O(logN).

要进行比较tracklet.end->t,请使用:

bool compareTracklets(const Tracklet &tr1, const Tracklet &tr2) {
    return (tr1.end->t < tr2.end->t);
}

并将compareTracklets作为第四个参数传递给lower_bound或upper_bound

Answer 2

我只是使用find和find_end,然后只有在测试显示它太慢时再做一些更复杂的事情.

如果您真的关心查找性能,则可以考虑使用不同的数据结构,例如将map时间戳作为键,将a vector或list元素作为值.