Вектор против вставки Deque в середине
я знаю это Deque более эффективен, чем вектор когда вставки находятся в начале или в конце и вектор лучше, если мы должны сделать арифметику указателя. Но какой использовать, когда мы должны выполнить вставки в середине? и почему.?
Решение
Вы можете подумать, что deque будет иметь преимущество, потому что он хранит данные, разбитые на блоки. Однако реализовать operator[] в постоянное время требует, чтобы все эти блоки были одинакового размера. Для вставки или удаления элемента в середине все еще требуется смещение всех значений в одну или другую сторону, так же как vector, Так как vector проще и имеет лучшую локализацию для кэширования, это должно выйти вперед.
Другие решения
Критерии выбора с контейнерами стандартной библиотеки: Вы выбираете контейнер в зависимости от:
- Тип данных, которые вы хотите сохранить &
- Тип операций, которые вы хотите выполнить с данными.
Если вы хотите выполнить большое количество вставок в середине, вам гораздо лучше использовать std::list,
Если выбор только между std::deque а также std::vector тогда есть ряд факторов, которые необходимо учитывать:
- Как правило, есть еще одно косвенное обращение в случае deque для доступа к элементам, поэтому element
доступ и перемещение итераторов запросов обычно немного медленнее. - В системах, которые имеют ограничения по размеру для блоков памяти, deque может содержать больше элементов, поскольку использует более одного блока памяти. Таким образом,
max_size()может быть больше для Deques. - Запросы не оказывают поддержки для контроля емкости и момента перераспределения. В
в частности, любая вставка или удаление элементов, отличных от начала или конца
делает недействительными все указатели, ссылки и итераторы, которые ссылаются на элементы deque.
Тем не менее, перераспределение может работать лучше, чем для векторов, потому что в соответствии с их
типичная внутренняя структура, запросы не должны копировать все элементы при перераспределении. - Блоки памяти могут быть освобождены, когда они больше не используются, поэтому объем памяти
deque может уменьшиться (это не условие, наложенное стандартом, но большинство реализаций делают)
станд :: Deque мог лучше работать для больших контейнеров, потому что он обычно реализуется как связанная последовательность смежных блоков данных, в отличие от одного блока, используемого в std::vector, Таким образом, вставка в середину приведет к меньшему количеству копируемых данных из одного места в другое и, возможно, к меньшему перераспределению.
Конечно, имеет значение, зависит это от размера контейнеров и стоимости копирования хранимых элементов. В семантике перемещения C ++ 11 стоимость последнего менее важна. Но, в конце концов, единственный способ узнать это профилирование с реалистичным приложением.
Deque все равно будет более эффективным, так как он не должен перемещать половину массива каждый раз, когда вы вставляете элемент.
Конечно, это действительно имеет значение, только если вы рассматриваете большое количество элементов, и даже не рекомендуется запускать эталонный тест и смотреть, какой из них лучше работает в вашем конкретном случае. Помни что преждевременная оптимизация — корень зла.