Поиск в 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.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 с меткой времени в качестве ключа и vector или list элементов в качестве значения.

Answer 3

прямо указывал на сравнительный оптимистический сравнительный анализ. Но я бы на самом деле не использовал std::vector для этого.

Обычно при принятии решения об использовании контейнера STL я не особо рассматриваю аспект производительности, но я рассматриваю его интерфейс относительно типа операции, которую я хочу использовать.

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

Действительно, если вы хотите упорядоченную последовательность вне настройки ключа / значения, std::set проще в использовании, чем любая другая.

• Вам не нужно беспокоиться о вставке в «плохую» позицию
• У вас нет проблем с аннулированием итераторов при добавлении / удалении элемента
• У вас есть встроенные методы поиска

Конечно, вы также хотите, чтобы ваш Предикат сравнения действительно блестел (надеется, что компилятор в каждом случае указывает на реализацию оператора ()).

Но на самом деле, если вы не уверены, попробуйте сборку с std::vector и ручной вставкой / поиском (используя заголовок <algorithm>) и попробуйте другую сборку, используя std::set.

Сравните размер реализаций (количество строк кода), сравните количество ошибок, сравните скорость и затем решите.

Чаще всего «оптимизация», к которой вы стремитесь, на самом деле является пессимизацией , и в те редкие времена это не так, она настолько сложна, что не стоит.

Оптимизация

• Не
• Только эксперт: не, мы это имеем в виду

Answer 4

Бинарный поиск кажется вам лучшим вариантом, пока ваш вектор остается отсортированным. С точки зрения производительности это практически идентично выполнению поиска в двоичной древовидной структуре.

Answer 5

Вектор упорядочен по времени

Время начала или время окончания?

Что не так с наивным поиском? Помните, что вы только ищете, а не сортировать. Вы также можете использовать отсортированный контейнер (если это не идет вразрез с основным дизайном).