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

StackOverflow https://stackoverflow.com/questions/1649139

题

我正在尝试找出搜索“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.end->t).

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

希望这是有道理的：我有点费劲去解释！干杯!

有帮助吗？

解决方案

如果该矢量进行排序并且包含值，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

其他提示

我只想用 find 和 find_end, ，然后仅在测试表明速度太慢时才执行更复杂的操作。

如果您确实关心查找性能，您可能会考虑使用不同的数据结构，例如 map 以时间戳为键和 vector 或者 list 元素作为值。

一个二进制搜索好像在这里你最好的选择，只要你的矢量保持有序。它本质上是相同的，性能的角度来看，在一个二进制树结构中执行查找。

阴暗地提及 进行甜蜜的优化比较。但事实上我不会使用 std::vector 为了这。

通常，当决定使用 STL 容器时，我并不会真正考虑性能方面，但我确实会考虑其与我希望使用的操作类型相关的接口。

std::set<T>::find
std::set<T>::lower_bound
std::set<T>::upper_bound
std::set<T>::equal_range

真的，如果你想要一个有序的序列，在键/值设置之外， std::set 只是比其他任何东西都更容易使用。

  • 您不必担心插入到“坏”位置
  • 添加/删除元素时不会遇到迭代器失效的问题
  • 您有内置的搜索方法

当然，您还希望您的比较谓词在每种情况下都能真正发挥作用（希望编译器内联 operator() 实现）。

但实际上，如果您不相信，请尝试使用 std::vector 和手动插入/搜索（使用 <algorithm> 标题）并尝试使用另一个构建 std::set.

比较实现的大小（代码行数），比较 bug 数量，比较速度，然后做出决定。

大多数情况下，您所追求的“优化”实际上是 悲观主义, ，在那些罕见的时候，事实并非如此，它太复杂了，不值得。

优化:

  • 不
  • 仅限专家：不，我们是认真的
  

将载体在时间上排序

的开始时间或结束时间？

什么是错的天真O（n）的搜索？记住，你只搜索，而不是排序。你可以使用一个排序的容器，以及（如果不违背基本的设计）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top