Deques следует выбирать над векторами, если мы постоянно добавляем спереди и сзади контейнера. Но как насчет смещения? Do vector и deque Оператор [] работает так же, или нет? Если нет, то какой из них быстрее?Vector vs Deque operator []
A std::vector<T> - это плоский массив из T элементов. std::deque<T> - массив массивов равного размера T. Сложность доступа к индексу - O (1) в обоих случаях, но std::deque<T> необходимо сделать намного больше работы, чтобы определить элемент для доступа, и есть также указание. Например, итераторам на std::deque<T> необходимо выполнить несколько проверок (хотя алгоритмы могли бы оптимизировать это, в основном, делая накладные расходы довольно небольшими, признавая сегментированную структуру. Таким образом, если вам нужно использовать оператор индекса, часто std::deque<T> может быть плохим выбором и стоимостью движущихся элементов в std::vector<T> при вставке/удалении на передней панели может быть компенсировано
Просто объяснить, грубо говоря, что std::deque<T> нужно делать в случае использования оператора индекс:. можно подумать о выполнении этих операций:
T& deque<T>::operator[](size_t n) {
n += this->first_element;
size_t subarray = n/size_of_subarrays;
size_t index = n % size_of_subarrays;
return this->subarrays[subarray][index];
}
Операторы деления/модуля вряд ли будут слишком дорогими, как size_of_subarray почти наверняка выбирается как мощность 2, то есть в основном это бит-бит.
, если я перехожу через последовательные элементы контейнера, любое предложение о том, как увеличить скорость цикла с помощью deque? будет ли использование итераторов увеличивать скорость, а не компенсировать? если бы вы могли помочь мне с примером о том, как реализовать итераторы на deques, или это то же самое, что и в векторах? – user2653125
@ user2653125: Правильный способ улучшить итерацию над deque заключается в том, чтобы воспользоваться его сегментированной структурой: вместо повторения над deque, перебирайте каждый из своих подмассивов по отдельности. К сожалению, deque не раскрывает эту структуру сегментации, а C++ еще не определяет концепцию сегментированного итератора. Основная проблема с итерацией по deque заключается в том, что приращение итератора требует проверки того, достиг ли итератор конца сегмента. Независимо от того, насколько маловероятна ветвь или вычисление дешевле, трудно предсказать, вам нужно будет измерить. –
спасибо. если из-за моего алгоритма я просто хочу добавить вперед и полностью перебрать контейнер в одном направлении, лучше ли я создать свою собственную версию связанного списка, а не вектор или deque? Будет ли это существенно меняться в производительности моего алгоритма? Или для этого есть другой лучший контейнер? – user2653125
для
декаиндексацию подходы эффективность вектора
Бьерн Страуструп "C++ язык программирования" 17.2.3
Это не совсем то же самое из-за одного дополнительная косвенность, необходимая для доступа к элементу. Это, в свою очередь, во многих случаях приводит к дополнительному попаданию памяти из-за ошибки кеша. Таким образом, он может быть на несколько порядков (на самом деле, примерно в 1000 раз) медленнее для случайного доступа. Тем не менее, это будет амортизироваться для многих последовательных обращений, поэтому на практике это обычно будет не так плохо.
... что, в свою очередь, приводит к дополнительному попаданию памяти из-за ошибки кеша в много случаев. Таким образом, он может быть на несколько порядков (на самом деле, примерно в 1000 раз) медленнее для случайного доступа. Тем не менее, это будет амортизироваться для многих последовательных обращений, поэтому на практике это обычно будет не так плохо. –
Да - доступ к основной памяти, а не к кэшу L1, примерно на 1000 раз медленнее. Вот почему у нас есть кеши в первую очередь. Но, как я уже сказал, как только вы получаете доступ к фрагменту deque, он обычно будет полностью загружен в кеш, поэтому, если вы впоследствии получите доступ к близким элементам, существует высокая вероятность попадания в кеш и, следовательно, гораздо более быстрый доступ. –
Большое вам спасибо, такая информация нам действительно нужна, чтобы узнать, что и когда и как использовать. Это очевидно как-то, но также во многих случаях не так просто связать разные аспекты – 4pie0
std::deque что-то вроде списка std::vectors, так что если вам действительно нужно [] оператор, std::vector будет быстрее принимать данные, но разница не велика, так что вы должны лучше выглядеть, как часто вы толкаете данные в спине и спереди для определения необходимости std::vector или std::deque. более
Одно дело, если вы используете цикл, который занимает некоторое индекс контейнера вы должны лучше использовать iterator как разница скорости в результате приема данных из std::vector и std::deque бы не заметно.
Это * вектор * векторов, а не список векторов. Существенная разница. –
@ KonradRudolph не излечивает реализацию. Но если это «вектор», то разница между «vector» и «deque» еще менее заметна. – ST3
Связанный (но не дубликат): [Что действительно является deque в STL?] (Http://stackoverflow.com/a/6292437/1968) –