c++ - 在 C++ Vector 中搜索值的第一次/最后一次出现

Question

我正在尝试找出最佳方法来搜索“Tracklet”类型的 vector (我自己构建的一个类)，以找到其中一个变量的给定值的第一次和最后一次出现。例如，我有以下类(针对此示例进行了简化):

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 “vector<Tracklet> tracklets”，我需要搜索结束时间点具有给定值“t”的任何轨迹。 vector 按结束时间排序(即 tracklet.end->t )。

我很乐意编写搜索算法代码，但不确定采用哪条路线。我不确定二进制搜索是否合适，因为我似乎记得它不一定会找到第一个。我在想一种方法，我使用二进制搜索找到具有正确时间的元素的索引，然后迭代返回找到第一个并向前迭代找到最后一个。我确信有比这更好的方法，因为它通过迭代浪费了二进制搜索 O(log n)。

希望这是有道理的:我费了好大劲才解释清楚!干杯!

Answer 1

如果 vector 已排序并包含值，std::lower_bound 将为您提供指向具有给定值的第一个元素的迭代器，std::upper_bound 将给你一个迭代器，指向包含该值的最后一个元素之后的一个元素。将值与返回的元素进行比较，以查看它是否存在于 vector 中。这两个函数都使用二进制搜索，所以时间是 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