Каков наилучший способ получить доступ к элементу deque в C ++ STL - PullRequest
Новая
       38

Каков наилучший способ получить доступ к элементу deque в C ++ STL

4 голосов
/ 23 января 2012

У меня есть deque: 

deque<char> My_Deque;
My_Path.push_front('a');
My_Path.push_front('b');
My_Path.push_front('c');
My_Path.push_front('d');
My_Path.push_front('e');

Существуют такие способы его вывода.

Первый: 

deque<char>::iterator It;
for ( It = My_Deque.begin(); It != My_Deque.end(); It++ )
    cout << *It <<  " ";

Второй: 

for (i=0;i<My_Deque.size();i++) {
    cout << My_Deque[i] <<  " ";
}

Как лучше всего получить доступ к элементу deque - через итератор или как это: My_Deque[i]?Имеет ли элемент deque <...> массив указателей на каждый элемент для быстрого доступа к его данным или обеспечивает последовательный доступ к его случайному элементу (как на картинке ниже)?enter image description here

Ответы [ 4 ]

6 голосов
/ 23 января 2012

Так как вы просили "лучший способ": 

for (char c : My_Deque) { std::cout << c <<  " "; }
3 голосов
/ 23 января 2012

Задание STL обычно реализуется как динамический массив массивов фиксированного размера, поэтому индексированный доступ является совершенно эффективным.

1 голос
/ 23 января 2012

Стандарт определяет, что deque должен поддерживать произвольный доступ в постоянное время.Так что да, [i] должно быть достаточно быстрым.

Но я думаю, что использование итераторов все же может иметь преимущество.Он может (по крайней мере теоретически) быть постоянным кратным быстрее (или, может быть, медленнее!).В любом случае, каждое использование [i] будет включать в себя поиск некоторых таблиц, вычисление смещений и так далее.Я хотел бы представить, что operator++ для deque :: iterator немного больше, чем просто "найти мое смещение; добавьте к нему 1; поиск с новым смещением"

1 голос
/ 23 января 2012

Поскольку вы запросили «лучший способ»: 

std::copy(My_Deque.begin(), My_Deque.end(),
          std::ostream_iterator<char>(std::cout, " "));

По общему признанию, для форматирования отдельного объекта это не будет иметь большого значения, но использование алгоритмов на структуре сегментированных данных может сделать большую разницу!Возможна интересная оптимизация при индивидуальной обработке сегментов при обработке всего диапазона.Например, если у вас есть большое std::deque<char>, которое вы хотите записать дословно в файл, что-то вроде 

std::copy(deque.begin(), deque.end(), std::ostreambuf_iterator<char>(out));

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

...