Искать в списке c ++?
Спасибо за просмотр моего вопроса заранее.
Я заканчиваю вопрос для университетского задания, который задает следующее:
Для каждого из std :: list< >, std :: map< >, std :: unordered_map< > документируйте и объясните гарантированную производительность для вставки и поиска элементов.
У меня не было проблем с выполнением большей части этого, пока я не пришел, чтобы объяснить поиск элементов в списке.
Я собирал информацию от Йосуттиса и http://www.cplusplus.com и не могу найти какую-либо информацию об этом.
Я предполагаю, потому что это невозможно?
Решение
Вы упоминаете, что у вас не было никаких проблем, кроме как с list часть, так что я собираюсь ответить только за эту часть.
Чтобы ответить на этот вопрос, нужно понять, как std::list реализовано.
Некоторый быстрый поиск вызывает:
Контейнеры списков реализованы в виде двусвязных списков.
Из того, как я это интерпретирую, Гарантированная производительность означает то же самое, что и В худшем случае сложность во время выполнения.
За поиск элементов в двусвязном списке наихудший сценарий состоит в том, что в вашем списке нет элемента, который вы пытаетесь найти. В этом случае вам придется сравнивать каждый элемент в списке с элементом, который вы ищете. Таким образом, сложность этой операции в худшем случае На), где n размер списка.
Другие решения
От http://www.cplusplus.com/reference/list/list/
Основной недостаток списков и forward_lists по сравнению с этими другими
Последовательность контейнеров в том, что они не имеют прямого доступа к элементам
их положение; Например, для доступа к шестому элементу в списке один
должен выполнять итерации с известной позиции (например, начало или конец)
в ту позицию, которая занимает линейное время на расстоянии между
эти. Они также потребляют дополнительную память, чтобы сохранить связь
информация, связанная с каждым элементом (который может быть важным
фактор для больших списков мелких элементов).
Итак, перебирая std :: list< > (поиск элемента) — это линейная сложность. Кроме того, вы не можете получить доступ к элементам по индексу.
Если вы хотите более формальное изложение того, что поддерживается, вот что говорит стандарт. О лучшем поиске, который мы можем сделать, это бинарный поиск, такой как std::lower_bound (§25.4.3.1 / 3):
Сложность: максимум лог2(
last − first) + O (1) сравнения.
Это только говорит нам количество сравнения хоть. Чтобы перемещаться через контейнер, lower_bound использования std::advance, О std :: list мы находим (§23.3.5.1 / 1):
Список — это контейнер последовательностей, который поддерживает двунаправленные итераторы […]
Итак, как же std::advance работать для коллекции, которая обеспечивает двунаправленные итераторы?
(§24.4.4 / 1):
[…] для входных, прямых и двунаправленных итераторов, которые они используют ++ для обеспечения реализации линейного времени.
Итак, чтобы найти что-либо в списке (по значению или положению), мы будем рассматривать общую линейную сложность с логарифмическим числом сравнений. Если честно, нам, наверное, лучше std::find (§25.2.5 / 2):
Сложность: максимум
last - firstприложения соответствующего предиката.
Хотя выбор между этими двумя вариантами не всегда очевиден — обход списка очевиден. std::find минимизирует обход, в то время как std::lower_bound минимизирует сравнения. Если сравнение намного дороже, чем обход, std::lower_bound вероятно, будет лучше Если сравнение довольно дешево, std::find наверное лучше.
Я рекомендую вам прочитать следующую ссылку:
Каковы гарантии сложности стандартных контейнеров?
Он содержит диаграмму сложности заказа для многих стандартных контейнеров и один из ответов содержит ссылки на спецификации сложности STL. (http://www.sgi.com/tech/stl/complexity.html)
Поскольку это проект класса, я рекомендую вам не только прочитать эти ссылки для своего ответа, но и потратить некоторое время на заголовки STL и почувствовать, как эти контейнеры реализованы в вашей архитектуре.
STL — это фантастический способ использовать знания настоящих экспертов … однако он также может быть достаточно общеизвестным канатом, если не проявлять должной осмотрительности