Смежные хранилища элементов в std ::vector и std ::deque

#c #vector #deque

#c #вектор #deque

Вопрос:

Что означает «смежные хранилища элементов» в отношении std::vector и std::deque ? Согласно cplusplus.com , std::vector гарантируется (и std::deque не гарантируется) хранение элементов в смежных хранилищах. Но как я могу увидеть это в коде? Оба имеют итератор произвольного доступа, поэтому в обеих ситуациях мы можем добавить некоторое случайное смещение к ссылке на случайный контейнер, и все должно быть в порядке, верно?

1. Непрерывность просто означает, что связанные данные хранятся в базовой структуре буфера, которая более или менее ведет себя так же, как T data[] массив в стиле C.

2. итераторы векторов становятся недействительными только при push_back, если происходит перераспределение, итераторы deque всегда становятся недействительными при возврате (это похоже на добавление фрагментированных элементов в дерево)

Ответ №1:

Вы можете увидеть это, используя vector::data() , который возвращает указатель на ваши смежные данные ( http://www.cplusplus.com/reference/vector/vector/data / ).

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

Эта функция-член существует также для массивов и строк, поскольку они также имеют смежные элементы.

Этот элемент не существует для контейнеров, которые не гарантируют непрерывность, таких как deque, списки или стеки.

1. Примечание: основной интерес data() представляет совместимость с C.

2. @MatthieuM. Это также упрощает операции чтения / записи двоичных файлов и добавляет понимания, по крайней мере, для std::vector<char> data: input_stream.read(v.data(), v.size()); vs input_stream.read(reinterpret_cast<char*>(v.data()), v.size()) .

Ответ №2:

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

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