Временные затраты на векторный поиск в сравнении с поиском по массиву

Вопрос:

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

Я знаком с причинами ясности / простоты использования для использования std::vector , а не массива.

Мой вопрос: При поиске определенного элемента в этом отсортированном списке существуют ли какие-либо существенные причины производительности, по которым я должен идти по сложному маршруту с массивом, а не выбирать std::vector?

ПРИМЕЧАНИЕ: Размер вектора не нужно было бы изменять. Он будет инициализирован при запуске программы (из файла) и в него никогда не будут добавлены элементы напрямую.

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

2. @EtiennedeMartel уверен, что начиная с C 11 это не просто «большинство», а все.

3. Стоимость поиска применяется к алгоритмам geneirc, а не к самим контейнерам.

4. @Raindrop7 да, но между контейнерами есть различия, выходящие за рамки обозначения big-oh. При прочих равных условиях тот же линейный поиск будет выполняться медленнее в deque, чем в vector. Итак, вопрос совершенно законен.

5. Примечание: для быстрого поиска вы можете обнаружить, что контейнеры std::set or std::map более подходят, чем массивы или std::vector .

Ответ №1:

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

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

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

Ответ №2:

Не было бы существенной разницы между массивом и вектором с точки зрения скорости сортировки, нет. Я бы тоже выбрал vector.

Ответ №3:

Выбирайте vector, в нем нет реальных компромиссов. Кроме того, Скотт Мейерс, автор нескольких наиболее полезных книг по c , говорит: Item 13. Prefer vector and string to dynamically allocated arrays. Прочтите всю главу, вы найдете множество причин, почему следует использовать векторы.