Поиск в векторе C ++<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 или список элементов в качестве значения.

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

дерзко упомянутый к приятному сравнительному анализу оптимизации.Но на самом деле я бы не стал использовать 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.

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

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

Оптимизация:

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top