Привет. Есть вектор событий, событие - это структура, с некоторыми

Question

Привет. Есть вектор событий, событие - это структура, с некоторыми

полями: time, client_id, etc. Этот вектор отсортирован по времени события. Как принято в С++ искать lower/upper_bound события (по времени) за O(logn)? Нужно для этого заводить отдельный вектор по времени, который будет указывать индекс и там искать? Или можно более элегантно?

#c #embedded #programming #russian

0

11.03.2022

10 ответов

19 просмотров

Artöm Bakri Al-Sarmini

Так std::{lower,upper}_bound и так логарфмическую сложность имеют

0

11.03.2022

Никита

Если ты структуру сравниваешь по времени всегда, то просто перепиши для неё знак <, если же тебе это требуется внутри одной лишь операции бин. поиска можешь передать функцию компаратор которая возвращает bool последним аргументом

0

11.03.2022

Никита

Artöm Bakri Al-Sarmini
Так std::{lower,upper}_bound и так логарфмическую ...

главное помнить, что std::lower_bound логарифмический только для структур чьи данные сплошняком лежат, в list такое не прокатит, а в set эффективна только функция мембер

0

11.03.2022

Artöm Bakri Al-Sarmini

Никита
главное помнить, что std::lower_bound логарифмичес...

Там сложная формулировка. Логарифмическая сложность по сравнениям и лог или линия по access в зависимости от категории итератора

0

11.03.2022

Станислав Трухан Автор вопроса

Artöm Bakri Al-Sarmini
Так std::{lower,upper}_bound и так логарфмическую ...

А как это в коде? vector<unique_ptr<Event>> events; // добавить события в определенном порядке, где time не убывает events.push_back(make_unique<Event>(time1, client1)); events.push_back(make_unique<Event>(time2, client2)); // здесь нужно найти интервал старых событий, например где time < t auto lower_it = events.begin(); auto upper_it = ??? // events.upper_bound(t);

0

11.03.2022

Станислав Трухан Автор вопроса

Станислав Трухан
А как это в коде? vector<unique_ptr<Event>> events...

или как я говорил, нужно заводить отдельный индекс-массив для этого и в нем искать upper_bound?

0

11.03.2022

Никита

Станислав Трухан
А как это в коде? vector<unique_ptr<Event>> events...

нет

0

11.03.2022