Каков наилучший способ вернуть подмножество списка

Question

У меня есть список задач. Задача определяется именем, датой (и временем) и продолжительностью.

Мой класс TaskManager обрабатывает std::list<Task>, отсортированные по дате исполнения. Он должен обеспечить способ получения заданий в определенный день.

Пример: у меня задание 1 должно быть выполнено в понедельник 6 часов утра, задание 2 - в понедельник 9 часов утра, задание 3 - во вторник 7 часов вечера. Если я передам «понедельник» моему методу, он должен вернуть задачи 1 и 2.

Как бы вы это реализовали?

Я думаю, что хорошим способом (с точки зрения API) было бы предоставить пару std::list<Task>::iterator. Так что у меня был бы метод TaskManager::begin(date). Считаете ли вы, что этот метод должен получить итератор путем итерации от начала списка до тех пор, пока он не найдет первое задание, которое должно быть выполнено в эту дату, или путем получения его из std::map<date, std::list<Task>::iterator> (но тогда мы должны поддерживать его в актуальном состоянии при добавлении или удалении задач)?

А потом, как я могу реализовать метод TaskManager::end(date)?

Answer 1

вместо использования std::list, рассмотрите возможность использования std::set или std::map, которые могут сохранять элементы в отсортированном порядке без дополнительных усилий. Затем вы можете найти предметы, которые должны быть на определенную дату, используя std::set::lower_bound или std::map::lower_bound.

Answer 2

Нахождение элемента в отсортированной последовательности может занять O(log n), а ваш метод - O(n).

Если для создания вашей коллекции у вас уже есть отсортированные элементы, используйте std::vector: это будет стоить O(1), чтобы вытолкнуть любой элемент в конце, и вы сможете использовать двоичный поиск, чтобы найти его в O(log n).

В противном случае (если вы вставляете элементы в случайном порядке) используйте std::map (используя ваши даты в качестве ключа) или std::set для добавления и поиска элементов в O(log n)

Answer 3

Вы можете использовать адаптер итератора.По сути, это итератор, конструктор которого принимает в качестве аргумента другой итератор, а метод его продвижения продвигает этот итератор до тех пор, пока он не найдет значение, удовлетворяющее какому-либо условию, а затем возвращает это значение или вычисленное из него значение.